# Finding a vector orthogonal to a subspace

Suppose you were given vectors $a_1,\dots,a_n \in \mathbb{R}^m$ then how would you compute some vector orthogonal to the given list of vectors? Note that you are allowed to return the zero vector only if the vectors span $\mathbb{R}^m$.

I thought about it for a while and the best I could do was to form the matrix with these vectors as rows and pick a vector from the nullspace. Is there an easier/faster way? Perhaps something geometric like Gram-Schmidt could be possible.

Thanks!

-
To computer "some vector", you could just return $\vec{0}$ but I guess you want another one. –  xavierm02 Mar 20 '13 at 19:16
Let $V=\operatorname{Vect}(\{a_1,\dots,a_n\})$ Let $(e_1,\dots,e_p)$ be an orthonormal basis of $V$ Then take any vector $x$ that is not in $V$ And then take $x-\sum\limits_{k=1}^p<e_p\mid x>e_p$ –  xavierm02 Mar 20 '13 at 19:16
How do I pick a vector that is not in $V$? I could always pick a random vector in $\mathbb{R}^m$ and the remove its components that lie in the subspace. But is there a deterministic way of doing this? –  anon Mar 21 '13 at 10:24
What is wrong with your finding x such that Ax = 0 idea? I see it as completely correct way of going about this. –  TenaliRaman Mar 21 '13 at 10:29
You have a basis $(\varepsilon_1,\dots,\varepsilon_m)$ of $\Bbb R^m$, to pick a vector that is not in $V$, you can compute $\varepsilon_i-\sum\limits_{k=1}^p<e_p\mid \varepsilon_i>e_p$ until you get a non-zero result. –  xavierm02 Mar 21 '13 at 12:18

Here is the deterministic algorithm.

Let $A$ be the $m \times n$ matrix of your vectors $$A = \pmatrix{a_0 & a_1 & \cdots & a_n}$$ Use the QR factorization of it $$A = QR$$ so that the Q matrix will contain the entire null space you are looking for: $$A = \pmatrix{Q_1 & Q_2}\pmatrix{R_1 \\ 0}$$ Since $Q$ is orthonormal $$\pmatrix{Q_1^\top \\ Q_2^\top}A = \pmatrix{R_1 \\ 0}$$ To completely specify the null space, you can see here that it is $Q_2$ $$Q_2^\top A = 0$$

-
Any deterministic algorithm will take as much computation as a row reduction, even to find a single vector in the null space. –  adam W Mar 21 '13 at 16:33

This is a very good occasion to apply the fundamental theorem of linear algebra regarding the four fundamental subspaces of a matrix. (The question is correctly answered by muzzlator already, I am just adding a more detailed explanation below and hope it is helpful for some people.)

First, use $a_1,\dots,a_n \in \mathbb{R}^m$ to form an $m\times n$ matrix $A$, with each vector as a column of the matrix. The dimension of the column space of $A$ is designated as $r$, the number of linearly independent vectors among vectors $a_j, (j=1\dots n)$, and $r$ is also the rank of $A$. Then the problem of finding some vector orthogonal to $a_1,\dots, a_n$ is equivalent to finding the solution in the "left nullspace" of $A$, designated as $N(A^T)$, by solving the following equation:

$$A^T x = 0.$$

$A^T$ is $n\times m$, and the dimension of $N(A^T) = m-r$. (Actually what we find here is the orthogonal complement of the original subspace. This is much better than finding just some orthogonal vectors.) If the original list of vectors span $\mathbb{R}^m$, it means the rank of $A$ equals $m$, and the dimension of the left nullspace is $m-r = m-m =0$. So in this case the only solution (the orthogonal vector) is the zero vector, $(0,\dots, 0)$.

Gauss elimination (to get the echelon matrix) is the method to find the solution to $A^Tx=0$. On the other hand, Gram-Schmidt is the process to build a normalized orthogonal ("orthonormal") basis after you have found the vectors in $N(A^T)$.

In your post, you are correct to use the vectors as rows in a matrix, so you don't need to transpose the matrix to find the answer. (Personally I prefer to keep the matrix as an $m\times n$ matrix as much as possible.)

-

There should indeed be a faster way. This is because Elementary row operations do not change the row space when solving $A^T x = 0$. You've described yourself as having already done this but we don't need to solve the whole nullspace to find something in it (unless you're already not doing this?).

Here is a thought, start with any non-zero vector and find a non-zero component. Eliminate that component in every other vector (theoretically). Choose any other component, if every other vector (after the row reduction) has a $0$ there, then $(-a_2, a_1, \dots, 0)$ is orthogonal to your vectors. Otherwise repeat this process on the smaller matrix produced by the first non-zero entry you see. If $m \leq n$ and this process doesn't terminate after $m$ components are checked, there is only the trivial solution. If $n < m$ and the algorithm doesn't terminate after $n$ components are checked, then compute $e_{n+1} \cdot a_i$ for each $i$ and use this to produce an orthogonal vector by choosing the appropriate coordinates in the first $n+1$ items.

This means a total of $\frac{\min\{m,n\}^2}{2} + m \max\{n-m, 0\}$ operations are more or less are all you need at worst.

-
Hm let me just check that, just realised this process wouldnt work if they span the space as it never gives a $0$ answer –  muzzlator Mar 21 '13 at 11:10
After a gazillion edits, I think I have it finally right. As expected, if $m >> n$, the problem is a lot easier. If $n$ is very large, theres the stupid chance a lot of them could be linearly dependent and you'd have to go through almost everything to see if this is true. –  muzzlator Mar 21 '13 at 12:03
That being said, there's probably a random algorithm which solves this in far fewer steps and if it fails to produce an answer, there will be a sufficiently small probability that there actually was an orthogonal vector. –  muzzlator Mar 21 '13 at 12:09