# Compute orthogonal complement using BLAS / LAPACK

Is there a fast method to compute an orthogonal complement of an arbitrary matrix $$U\in\mathbb{R}^{m \times n}$$ in BLAS / LAPACK?

Specifically, I want any matrix $$V\in \mathbb{R}^{m \times (m - \text{rank}(M))}$$ such that $$\text{rank}(U|V) = m.$$

The singular value decomposition methods in LAPACK can do this if called correctly, but if $$U\in\mathbb{R}^{m \times (m-1)}$$ is full rank, this will take $$O(m^3)$$, when it should only take $$O(m^2)$$ (e.g., via Gram-Schmidt orthogonalization of a random vector).

Orthogonality of $$V$$ is a plus but not required.

• Are you assuming $U$ has orthogonal columns? Otherwise I don't think a Gram-Schmidt-type algorithm would be guaranteed to work. Commented Nov 2, 2022 at 7:40
• @Federico, good point. I didn't really mean to assume that. And I guess the only practical situation where I'd know I have orthogonal columns would be after just having run an $O(m^3)$ algorithm like "non-full" SVD or QR Commented Nov 2, 2022 at 8:39
• I mean, I don't think running a Gram-Schmidt-like process ensures that you get a valid solution, unless $U$ was already orthogonal to start with. So I'm not sure that there is a $O(m^2)$ solution as you claim in the case $n=m-1$. Commented Nov 2, 2022 at 10:05
• And then the next question is: can you assume $U$ to have full column rank? Otherwise, checking it requires $O(mn^2)$ to start with. Commented Nov 2, 2022 at 10:06
• (And let me also note that in practice in this case taking a random $V$ works with probability 1!) Commented Nov 2, 2022 at 10:07