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.