Finding an Orthonormal Matrix to Rotate an n-Dimensional Vector
Date: 08/05/2009 at 05:01:07 From: Reza Subject: Finding an orthonormal matrix to rotate an n-D vector Suppose we have two n-dimensional vectors v1 and v2 with the same length, i.e., |v1| = |v2|. How can we build an orthonormal matrix M so that M * v1 = v2? Is there only one such matrix? I've read about rotation matrices and know that rotation may not be well defined in higher dimensions. But I'm wondering if there is another way to define the problem. Is there a solution in linear algebra papers or texts? Is it a classic?
Date: 08/05/2009 at 09:36:13 From: Doctor George Subject: Re: Finding an orthonormal matrix to rotate an n-D vector Hi Reza, Thanks for writing to Doctor Math. This is a standard problem in computer graphics. It turns out that there are an infinite number of solutions. First, let's define some symbols. 1. Let v3 = v1 X v2. 2. Let Q2 be an orthogonal matrix that performs a rotation about v1 by an arbitrary angle so that Q2 * v1 = v1. This means that v1 is an eigenvector of Q2. 3. Let Q1 be an orthogonal matrix that performs a rotation about v3 by the smallest angle between v1 and v2 so that Q1 * v1 = v2. We can see that Q1 * (Q2 * v1) = v2. Now define M = Q1 * Q2 so that M * v1 = v2 Since there are an infinite number of options for Q2, there are an infinite number of options for M. The simplest option is when Q2 = I. Now you just need to know how to construct an orthogonal matrix for a rotation about an axis by a specified angle. For this, you need Rodrigues' Rotation Formula. Here are two articles that explain it: Wikipedia http://en.wikipedia.org/wiki/Rodrigues%27_rotation_formula MathWorld http://mathworld.wolfram.com/RodriguesRotationFormula.html Does that make sense? Write again if you need more help. - Doctor George, The Math Forum http://mathforum.org/dr.math/
Date: 08/05/2009 at 10:00:03 From: Reza Subject: Finding an orthonormal matrix to rotate an n-D vector Thank you for your kind help. The references are also very useful. Thanks. But I still want to know if there is an extension to more than 3 dimensions. Can the vectors v1 and v2 be in R^n (n > 3)? For such cases, rotation may not make sense. But still an n x n matrix M can be found so that its orthonormality might be satisfied. Is there an extension of Rodrigues's algorithm to more than 3 dimensions?
Date: 08/05/2009 at 11:46:48 From: Doctor George Subject: Re: Finding an orthonormal matrix to rotate an n-D vector Hi Reza, Sorry for missing the n > 3 part of your question. I don't think there is a direct extension of Rodrigues' Formula, but I am sure that the problem is solvable in higher dimensions, as well. Think about the 3D case again. The matrix M can be broken down into a sequence of rotations in the xy, yz, and zx planes. In the n dimensional case, we need to extend this idea and find a sequence of rotations in each 2D subspace. These are called Givens rotations or Jacobi rotations. Wikipedia http://en.wikipedia.org/wiki/Givens_rotation http://en.wikipedia.org/wiki/Jacobi_rotation It takes some programming to do this. I'll also open the question to the other math doctors to see if they have other suggestions. - Doctor George, The Math Forum http://mathforum.org/dr.math/
Date: 08/06/2009 at 03:07:06 From: Doctor Jacques Subject: Re: Finding an orthonormal matrix to rotate an n-D vector Hi Reza, You can also use reflections: these are orthogonal transformations. If u is a unit vector, a reflection R with respect to the hyperplane perpendicular to u is given by: R(x) = x - 2u<u,x> Here, <u,x> is the scalar product. In matrix form, using column vectors for x and u, we have <u,x> = u'x, where u' is the transpose of u; and this becomes: R(x) = x - 2*u*u'*x = (I - 2uu')x This shows that the reflection is described by the matrix I - 2uu'. This is known as a Householder reflection, the details of which you can read here, along with a description of the more general case of complex vectors: Wikipedia http://en.wikipedia.org/wiki/Householder_transformation As a reflection is an isometry, this matrix is orthogonal, i.e., RR' = I (this can also be checked directly). If you want the reflection to map v1 to v2, you only need to take u as the unit vector proportional to (v1 - v2). Although this matrix will be orthogonal, it will not be a rotation, because its determinant will be -1. A rotation corresponds to an orthogonal matrix with determinant +1. If you insist on having a proper rotation, you can simply combine the reflection above with another reflection that leaves both vectors fixed: the product of two reflections is a rotation. For the latter reflection, you need to pick a unit vector t perpendicular to both v1 and v2; this corresponds to a reflection with respect to a hyperplane containing v1 and v2. In three dimensions, you can find this vector by computing the cross product v1 x v2, and normalizing to have |t| = 1. In higher dimensions (n > 3), you must satisfy these relations: <t,v1> = 0 <t,v2> = 2 This is a homogeneous system of 2 equations in n unknowns. If n >= 3, it always has at least one non-zero solution. If n > 3, you have many more solutions. You can multiply that solution by a constant factor to have a unit vector. If S is the matrix corresponding to this reflection, we have ... S = I - tt' ... and the matrix RS will describe a rotation sending v1 to v2. Note that this rotation actually exchanges v1 and v2. If you use this technique in 3D space, this rotation is not what you would naively expect: it is a rotation of 180 degrees.
Date: 08/06/2009 at 14:21:16 From: Reza Subject: Thank you (Finding an orthonormal matrix to rotate an n-D vector) Thank you, all. I am grateful for your help.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.