Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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!
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$$
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.
