Find vector in R^n which is orthogonal to given (n-1) vectors v_i under condition v_i are orthonormal.

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.

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.

• 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
• – 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

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 :).

• 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