Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T02:00:03Z http://mathoverflow.net/feeds/question/87688 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87688/linear-algebra-find-an-n-dimensional-vector-orthogonal-to-a-given-vector Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector wavepacket 2012-02-06T17:00:55Z 2012-02-06T18:44:28Z <p>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.</p> <p>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).</p> <p>I should add that writing a generalized cross product algorithm is not appealing. I'd prefer another way.</p> http://mathoverflow.net/questions/87688/linear-algebra-find-an-n-dimensional-vector-orthogonal-to-a-given-vector/87691#87691 Answer by kapil for Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector kapil 2012-02-06T17:26:01Z 2012-02-06T17:26:01Z <p>Suppose the vector is \$(x_1,x_2,\dots)\$. The following algorithm should work:</p> <ol> <li><p>If \$x_1=0\$ then take \$(1,0,0,\dots)\$.</p></li> <li><p>If \$x_1\$ is non-zero and \$x_2=0\$ then take \$(0,1,0,0,\dots)\$.</p></li> <li><p>If \$x_1\$ and \$x_2\$ are non-zero then take \$(-x_2,x_1,0,0,\dots)\$</p></li> </ol> http://mathoverflow.net/questions/87688/linear-algebra-find-an-n-dimensional-vector-orthogonal-to-a-given-vector/87702#87702 Answer by Ostap Chervak for Linear Algebra - Find an N-Dimensional Vector Orthogonal to A Given Vector Ostap Chervak 2012-02-06T18:44:28Z 2012-02-06T18:44:28Z <p>Actually you might use Gram Schmidt here.</p> <p>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\$ </p> <p>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).</p> <p>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.</p>