Skip to main content

Unit 10.3.2 Givens' rotations

We now introduce another important class of orthogonal matrices known as Givens' rotations. Actually, we have seen these before, in Subsubsection 2.2.5.1, where we simply called them rotations. It is how they are used that makes then Givens' rotations.

Given a vector \(x = \left( \begin{array}{c} \chi_1 \\ \chi_2 \end{array} \right) \in \R^2\text{,}\) there exists an orthogonal matrix \(G \) such that \(G^T x = \left( \begin{array}{c} \pm \| x \|_2 \\ 0 \end{array} \right) \text{.}\) The Householder transformation is one example of such a matrix \(G\text{.}\) An alternative is the Givens' rotation: \(G = \left( \begin{array}{c c} \gamma \amp -\sigma \\ \sigma \amp \gamma \end{array} \right)\) where \(\gamma^2 + \sigma^2 = 1 \text{.}\) (Notice that \(\gamma \) and \(\sigma \) can be thought of as the cosine and sine of an angle.) Then

\begin{equation*} \begin{array}{rcl} G^T G \amp= \amp \left( \begin{array}{c c} \gamma \amp -\sigma \\ \sigma \amp \gamma \end{array} \right)^T \left( \begin{array}{c c} \gamma \amp -\sigma \\ \sigma \amp \gamma \end{array} \right) = \left( \begin{array}{c c} \gamma \amp \sigma \\ -\sigma \amp \gamma \end{array} \right) \left( \begin{array}{c c} \gamma \amp -\sigma \\ \sigma \amp \gamma \end{array} \right) \\ \amp= \amp \left( \begin{array}{c c} \gamma^2 + \sigma^2 \amp - \gamma \sigma + \gamma \sigma \\ \gamma\sigma - \gamma\sigma \amp \gamma^2 + \sigma^2 \end{array} \right) = \left( \begin{array}{c c} 1 \amp 0 \\ 0 \amp 1 \end{array} \right), \end{array} \end{equation*}

which means that a Givens' rotation is an orthogonal matrix.

Homework 10.3.2.1.

Propose formulas for \(\gamma \) and \(\sigma \) such that

\begin{equation*} \left( \begin{array}{c c} \gamma \amp -\sigma \\ \sigma \amp \gamma \end{array} \right)^T \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c} \chi_1 \\ \chi_2 \end{array} \right) } \\ x \end{array} = \left( \begin{array}{c} \| x \|_2 \\ 0 \end{array} \right) , \end{equation*}

where \(\gamma^2 + \sigma^2 = 1 \text{.}\)

Solution

Take \(\gamma = \chi_1 / \| x \|_2 \) and \(\sigma = \chi_2 / \| x \|_2 \text{,}\) then \(\gamma^2 + \sigma^2 = ( \chi_1^2 + \chi_2^2 ) / \| x \|_2^2 = 1 \) and

\begin{equation*} \left( \begin{array}{c c} \gamma \amp -\sigma \\ \sigma \amp \gamma \end{array} \right)^T \left( \begin{array}{c} \chi_1 \\ \chi_2 \end{array} \right) = \left( \begin{array}{c c} \gamma \amp \sigma \\ -\sigma \amp \gamma \end{array} \right) \left( \begin{array}{c} \chi_1 \\ \chi_2 \end{array} \right) = \left( \begin{array}{c} ( \chi_1^2 + \chi_2^2 ) / \| x \|_2 \\ ( \chi_1 \chi_2 - \chi_1 \chi_2 ) / \| x \|_2 \end{array} \right) = \left( \begin{array}{c} \| x \|_2 \\ 0 \end{array} \right). \end{equation*}
Remark 10.3.2.1.

We only discuss real-valued Givens' rotations and how they transform real-valued vectors, since the output of our reduction to tridiagonal form, after postprocessing, yields a real-valued tridiagonal symmatric matrix.

Ponder This 10.3.2.2.

One could use \(2 \times 2 \) Householder transformations (reflectors) instead of Givens' rotations. Why is it better to use Givens' rotations in this situation.