Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If we need to find vector in R^n which is orthogonal to given (n-1) vectors, this is basically solving linear system of equations and can be done in O(n^3) operation.

I wonder is there some simplification to do it if it is additionally known that vectors are v_i are orthonormal ?

Probably NO. But may be I am missing something ?

In my situation n=4 or n=8.

But even in R^3 I cannot guess the way I do not see how orthonormality of v_1 v_2 can help to find v_3.

====== Some clarifications, answering comments.

1) Of course, we can write "vector product" like formula i.e. just all (n-1)(n-1) minors of our n(n-1) matrix. How will you calculate this minors ? The easiest way to calculate determinat is via Gauss decomposition i.e. O(n^3).
So it better directly apply Gauss decomposition to initial matrix and solve the problem in O(n^3) operations.

This is straightforward solution which I know. This does NOT use any my additional information that vectors are orthogonal.

2) We can choose some vector w and orthogonlize it. Complexity is n^2. Seems, solution ? No, because: there is no guarantee that we did not get ZERO. So we need to take w1 ... wn - linear independent - and orthogonalize each of them - then we have guarantee that you one of them is non-zero. But in this way we again have O(n^3) complexity.

share|improve this question
    
vector product (and it's generalization for higher dimensions) –  David Lehavi Oct 27 '11 at 14:37
    
Well maybe you should be more precise --- the vector product is infamous for not generalizing seamlessly to higher dimensions... –  Federico Poloni Oct 27 '11 at 14:47
1  
Look at this en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process –  Dirk Oct 27 '11 at 14:48
    
@Federico: once you call it wedge product and take n-1 vectors (and not 2) it does. –  David Lehavi Oct 27 '11 at 16:48
    
@David Lehavi: thanks, that's more precise. Didn't mean to be blunt. :) –  Federico Poloni Oct 28 '11 at 9:13
add comment

1 Answer

up vote 14 down vote accepted

You want to find the last row of an orthogonal matrix given $n-1$ rows, right? Since the sum of squares in each column is $1$, you can find the absolute values of the entries in about $n^2$ operations. So, it remains to determine the sign pattern for non-zero entries. That can be also done quickly: add two columns with non-zero last entries. The sum should have norm 2 and this is enough to determine if the signs of the last entries were the same or different because $(a+b)^2\ne(a-b)^2$. Of course, this works only if the $n-1$ orthonormal vectors are known with reasonable precision but it requires no random choice.

Edit: All right. Here goes the formal algorithm as I would try it in a real implementation:

Let $v_i=(v_{ij})$ be the given vectors ($i=1,\dots,n-1$, $j=1,\dots,n$).

Put $v_{nj}=\sqrt{1-\sum_{i=1}^{n-1}v_{ij}^2}$ (return $0$ if the expression under the root is slightly negative and write an error message if it is noticeably negative).

Choose $J$ such that $v_{nJ}=\max_j v_{nj}$.

For $j\ne J$ compute $S=\sum_{i=1}^{n-1} v_{ij}v_{iJ}$. If $S\le 0$, leave $v_{nj}$ as is, otherwise change its sign to $-$. After that is done, for control, compute $T=v_{nj}v_{nJ}$ and check that $S+T=0$ with decent precision. If not, write an error message.

Take two or three scalar products of thus obtained $v_n$ with previous vectors (say, $v_1$ and $v_{n/2}$) and check the norm of $v_n$. If those tests pass with decent precision, consider the task done.

I know, I'm sort of paranoid about possible errors in my programming but it you'd better detect the situation when you try this on a system of vectors that is not quite orthonormal :).

share|improve this answer
    
I'm afraid I don't understand the part where you determine the signs. It seems that a global sign ambiguity is unavoidable, unless you employ some orientation-dependent method, but I am unable to see such an ambiguity here. –  S. Carnahan Oct 28 '11 at 2:30
    
You cannot tell the individual signs, only if the signs in a given pair are the same or opposite. Example (length 2): (3/5,?), (4/5,?). Find absolute values: 4/5 and 3/5. Same signs trial: (7/5,7/5) - wrong norm. Opposite sign trial (7/5,1/5) - correct norm. Thus the signs are opposite. Now, if we know that entries 1 and 2 have the same sign, 2 and 3 - opposite, 3 and 4 -the same, etc., we know that the sign pattern is either ++--... or --++... but, of course, we cannot tell which one and have to make an arbitrary choice. –  fedja Oct 28 '11 at 2:39
    
Oh, I see. Very clever. –  S. Carnahan Oct 28 '11 at 2:45
    
I do not quite get how You choose signs. But the point is norms are easyly calculable is indeed good ! Thank You ! –  Alexander Chervov Oct 28 '11 at 6:15
    
OK, I'll edit to include the full algorithm (but a bit later :)) –  fedja Oct 28 '11 at 13:23
show 3 more comments

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.