Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector - MathOverflow

Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector

2012-02-06T17:00:55Z

I'm writing an eigensolver and I'm trying to generate a guess for the next iteration in the solve that is orthogonal to to all known eigenvectors calculated thus far. This means that if I have only one eigenvector, that is say 2 million entries long, I need to generate a vector orthogonal to it. I don't think Gram Schmidt works here because I don't have a set of vectors to orthogonalize. What I have is a single vector, in the first eigensolve, and I need to generate another that is orthogonal.

So, in summary: given one vector, create from nothing another vector which is orthogonal to it. The method must support N-Dimensional vectors (where N could be millions).

I should add that writing a generalized cross product algorithm is not appealing. I'd prefer another way.

Answer by kapil for Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector

2012-02-06T17:26:01Z

Suppose the vector is $(x_1,x_2,\dots)$. The following algorithm should work:

If $x_1=0$ then take $(1,0,0,\dots)$.
If $x_1$ is non-zero and $x_2=0$ then take $(0,1,0,0,\dots)$.
If $x_1$ and $x_2$ are non-zero then take $(-x_2,x_1,0,0,\dots)$

Answer by Ostap Chervak for Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector

2012-02-06T18:44:28Z

Actually you might use Gram Schmidt here.

Given a set of ortogonal vectors $x_1,x_2,\ldots,x_k$ you can use Gram-Shmidt algorithm for set of vectors ${x_1,x_2,...,x_k,e_i}$ adding basis vector to system of ortogonalysed vectors (note that you need use Gram Schmidt procedure only to find last vector since first k vectors are already orthogonal). Then (since vectors $e_1,e_2,\ldots,e_{k+1}$ are linearly independent) for some i between 1 and k+1 Gram Schmidt will give you non-zero vector which is ortogonal to given vectors $x_1,x_2,\ldots,x_k$

So to find a guess you simply need to use Gram Schmidt procedure several times (no more than k+1 for the first guess and no more then two times for next guesses).

To simplify this procedure you can do this only with first $k+1$ coordinates of vectors, so you will find a vector of form $(y_1,y_2,\ldots,y_{k+1},0,0,\ldots)$. Answers of Kapil and Klaus are actually equivalent to using this route.