Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

3 Answers 3

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$$

share|improve this answer
    
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.)

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.