The proof [1] of the title will not be present here. It is used as a conclusion in this article to solve practical computer graphics and robotics problem.
Basic Concepts
Single Rotation
A rotation matrix \(R\) in n-dimensional space: \(\{ R \in \mathbb{R}^{n \times n} | RR ^\top = I, \text{det}(R) = 1\}\). A single rotation matrix is a rotation matrix \(R\) with only one pair of complex eigenvalues.
A single rotation has only one rotation plane \(B\) and rotation angle \(\theta\). The exponential form of a single rotation is \(R = e ^{B \theta}\).
Householder Transform
Householder transform is a famous orthogonal transform in basic linear algebra. For example, QR decomposition use Householder transform to trianglize a matrix.
\[ P = I - 2 v v ^\top \tag{1-1} \]Here \(P\) is the Householder matrix, \(I\) is the identity matrix, \(v\) is an n-dimensional unit vector used for reflection.
There are some properties of \(P\):
- Involutory: \(PP = I\)
- Orthogonal: \(P^\top P = I\)
- Eigenvalues: \( \lambda_i = \begin{cases} -1 & \text{i = 1}\\ 1 & i = 2, \cdots , n\\ \end{cases}\)
- Eigenvectors: \( \begin{cases} e_i = v & i = 1\\ e_i \perp v & i = 2, \cdots , n\\ \end{cases} \)
- Determinant: \(\text{det}(P) = -1\)
\(\forall x \in \mathbb{R}^{n}, x = c_1 e_1 + c_2 e_2 + \cdots c_n e_n\). Then,
\[ \begin{align} Px &= \lambda_1 c_1 e_1 + \lambda_2 c_2 e_2 + \cdots \lambda_n c_n e_n \\ &= -c_1 e_1 + c_2 e_2 + \cdots c_n e_n \tag{1-2} \end{align} \]Formula (1-2) shows that matrix \(P\) reflect a vector \(x\) along vector \(v\).
With the definition of reflection, the title of this article can be expressed as follow:
A single rotation \(R\) in plane \(B\) with rotation angle \(\theta\) can be composed by two reflections \(P_1 = I - 2 u u ^\top, P_2 = I - 2 v v ^\top\), with \(u\) and \(v\) lie in plane \(B\) and form a angle of \(\frac{\theta}{2}\).
Composition of a Single Rotation
An n-dimensional single rotation \(R = e ^{B \theta}\) can be composed by two matrix \(P_1 = I - 2u u ^\top, P_2= I - 2v v ^\top\)
\[ \begin{align} R &= P_1 P_2 \\ \cos \frac{\theta}{2} &= u ^\top v \\ B &= \text{span}\{u, v\} \end{align} \]Decomposition of a Single Rotation
The decomposition from a single rotation to two reflections are not unique. Any two reflections \(P_1, P_2\) with reflect vector \(u, v\) in rotation plane \(B\) form a angle \(\theta\) can compose a single rotation.
\[ \begin{align} R &= P_1 P_2 \\ &= (I - 2u u ^\top) (I - 2v v ^\top) \\ &= I - 2u u ^\top - 2v v ^\top + 4(u ^\top v) u v ^\top\\ \end{align} \] \[ \frac{R - I}{2} = 2(u ^\top v) u v ^\top - (u u ^\top + v v ^\top) \tag{2-1} \]Find the Rotation Angle
Because \(\text{tr}(v v ^\top) = \text{tr}(u u ^\top) = 1\), \(\text{tr}(u v ^\top) = u ^\top v\)
\[ \text{tr}\left(\frac{R - I}{2}\right) = \frac{1}{2} \left(\text{tr}(R) - n\right) = 2 (u ^\top v)^2 - 2 \] \[ \begin{align} \cos ^2 \frac{\theta}{2} &= \frac{1}{4} \left(\text{tr}(R) - n\right) + 1 \\ \sin ^2 \frac{\theta}{2} &= -\frac{1}{4} \left(\text{tr}(R) - n\right) \end{align} \]Because
\[ \cos \theta = \cos ^2 \frac{\theta}{2} - \sin ^2 \frac{\theta}{2} \] \[ \cos \theta = \frac{\text{tr}(R) - n}{2} + 1 \tag{2-2} \]It provides a way to calculate rotation angle of a n-dimensional single rotation. Specifically, when \(n = 3\), it degenerates to the famous Rodrigous formula.
Find the Rotation Plane
By subtracting (2-1) with its transposition,
\[ \frac{R ^\top - I}{2} = 2(u ^\top v) v u ^\top - (u u ^\top + v v ^\top) \] \[ \frac{1}{4 (u ^\top v)} (R - R ^\top) = u v ^\top - v u ^\top \tag{2-3} \]Denote \(A = u v ^\top - v u ^\top\), \(A ^\top = -A\) and is therefore a skew symmetric matrix.
Lemma 1. For vectors \(u \in \mathbb{R}^{n}, v \in \mathbb{R}^{n}\). \(u v ^\top - v u ^\top = A\) forms a directional plane \(B\). And for any \(x \in \mathbb{R}^{n}\), applying \(A\) on \(x\) finds a vector \(y\) in plane \(B\) that \(y \perp x\).
Proof: we use \(y\) and \(u\) to form another plane \(B'\) to see whether plane \(B\) and \(B'\) are the same directional plane with different magnitude.
\[ A x = y = u v ^\top x - v u ^\top x \] \[ \begin{align} y u ^\top &= u v ^\top x u ^\top - v u ^\top x u ^\top = (v ^\top x) u u ^\top - (u ^\top x) v u ^\top \\ u y ^\top &= u x^\top v u ^\top - u x^\top u v ^\top = (x ^\top v) u u ^\top - (x ^\top u) u v ^\top \end{align} \] \[ y u ^\top + u y ^\top = (u ^\top x) (u v ^\top - v u ^\top) = k A \]If \(u\) is not perpendicular to \(x\), \(u ^\top x = k \neq 0\). Therefore the planes generated by \(y u ^\top + u y ^\top\) and \(u v ^\top - v u ^\top\) are the same directional plane with different magnitude. So, vector \(y\) lies in plane \(B\).
Besides:
\[ x ^\top y = x ^\top A x \]Transpose both sides.
\[ \begin{align} x ^\top y &= (x ^\top A x)^\top \\ &= -x ^\top A x \\ \end{align} \] \[ x ^\top y = -(x ^\top y) = 0 \implies x \perp y \]With Lemma1, we can find two vectors in plane \(B\) by applying \(A\) to two vectors that is not perpendicular to plane \(B\). An identity matrix \(I\) is consisted of \(n\) orthogonal vectors. By apply \(A\) to \(I\), \(A I = A\). Therefore all column vectors of \(A\) lie in the plane \(B\). According to (2-3), \(R - R^\top = 4 u^\top v A = kA\). Thus, pick up two columns of none zero vector of matrix \(R - R^\top\), one can define the rotation plane of single rotation \(R\) when \(R \neq I\).
Find the Direction of Rotation Plane
One rotation angle \(\theta\) and two vectors \(x\) and \(y\) are still not enough to define a single rotation. The ambiguity is the rotation can be either from \(x\) to \(y\) or from \(y\) to \(x\). The rotation direction can be defined as follow:
Lemma2. Given rotation \(R\) in plane \(B\) and vector \(x \in B\). Denote \(y = (R - R^\top)x\). According to Lemma1, \(y\) is also in plane \(B\) and \(y \perp x\), then the direction of rotation is from \(x\) to \(y\) with rotation angle \(\theta \in [0, \pi)\).
Lemma2. will not be proved here. Instead, the following image explains how it works:
Because \(x\) is a vector in plane \(B\), the N-Dimensional single rotations is equivalent to a rotation in a 2D plane. The direction of vector \(y\) is the direction of vector \(x\) with \(90^ \circ\) clockwise rotation if \(\theta \in [0, \pi)\). i.e.
\[ (R - R^\top) x = k \exp \left( \frac{\pi}{2 \theta} \ln(R) \right) x \]where \(k > 0, k \in \mathbb{R}\).
In summary, to fully define the single rotation plane, one can use the column vector with largest norm in matrix \((R - R^\top)\) as vector \(x\), and vector \(y = (R - R^\top)x\).
The Next Step
A general rotation in higher dimensional space (\(n > 3\)) may be consists of multiple single rotations. A method for decomposing a general rotation to several orthogonal single rotations was proposed [3]. By combining those methods, developers may be able to solve higher dimensional geometry problem just as in 3D world. Maybe do ray tracing or SLAM in 4D world.
References
- Mathoma, Geometric algebra in 2D - Two Reflection is a Rotation, YouTube
- Wikipedia, Householder transformation
- Richard, Aurélie, et al. "Decomposition of nD-rotations: classification, properties and algorithm." Graphical models 73.6 (2011): 346-353.
- Muphrid, "Geometric interpretation to Skew symmetric coefficient matrix." Math stack exchange.