How to extend an existing orthogonal set of vectors? Suppose I have $k$ vectors in $\mathbb R^n$ that are orthogonal to each other ($k \ll n$). Is there an efficient way to find another vector that is orthogonal to all these given vectors?
If we put the $k$ vectors in a $k \times n$ matrix, denoted by $A$, then the problem is identical to finding a vector in the null space of $A$. Of course one can resort to the method of solving an underdetermined linear system to find the null space of $A$, but by doing this we have got all the vectors that span the null space of $A$. For $k \ll n$, this is definitely not efficient, since I only need one vector in the null space.
I'm wondering if there exists a smarter way.
 A: You could normalize the $k$ vectors and make them the columns of a matrix $Q$.  Then $I - QQ^T$ is the projection onto the orthogonal complement of the span of the $k$ vectors.  Any nonzero column of this matrix is orthogonal to the $k$ vectors.
A: The problem with random guess-and-check is nondeterministic behavior. As $\lim k \to n$, the time take is going to get longer and longer. That is why finding something in the null space would make more sense, unless you can figure out an easy transformation that will turn the existing orthogonal vectors into the unit coordinate vectors: $\vec e_1, \vec e_2 \ldots$, and from there you can generate the remaining vectors. After you have all the vectors you want, inverse transform them back to the original coordinate system.
A: You could try to pick the first $k+1$ components of each vector and form $v_1,\ldots,v_k$ in $\mathbb{R}^{k+1}$. Then you can do the cross product of these vectors $w=v_1\times\ldots\times v_k\in \mathbb{R}^{k+1}$. Finally, you can define $v=(w,0,\dots,0)\in\mathbb{R}^n$.
If $w=0$ start to pick the components from the second and define $v=(0,w,0,\dots,0)\in\mathbb{R}^n$, and so on. However, I believe this would be useful only if $k$ is much smaller then $n$, because you need to compute a determinant.
