Editing Givens rotation (section)

== Triangularization ==
Given the following {{gaps|3|×|3}} Matrix:

:<math> A_1 =
       \begin{bmatrix}   6    &    5    &    0   \\
                         5    &    1    &    4     \\
                         0    &    4    &    3     \\
       \end{bmatrix},</math>

two iterations of the Givens rotation (note that the Givens rotation algorithm used here differs slightly from above) yield an upper [[triangular matrix]] in order to compute the [[QR decomposition]].

In order to form the desired matrix, zeroing elements {{gaps|(2,|1)}} and {{gaps|(3,|2)}} is required; element {{gaps|(2,|1)}} is zeroed first, using a rotation matrix of:
:<math>G_{1} =
       \begin{bmatrix}   c    &    -s    &    0   \\
                         s   &    c    &    0     \\
                         0    &    0    &    1     \\
       \end{bmatrix}.</math>

The following matrix multiplication results:
:<math>
\begin{align}
G_1 A_1 &{}= A_2 \\
&{} = \begin{bmatrix}   c    &    -s    &    0   \\
                         s   &    c    &    0     \\
                         0    &    0    &    1     \\
       \end{bmatrix}
       \begin{bmatrix}   6    &    5    &    0   \\
                         5    &    1    &    4     \\
                         0    &    4    &    3     \\
       \end{bmatrix},
\end{align}
</math>

where
:<math>\begin{align}
 r &{}= \sqrt{6^2 + 5^2} \approx 7.8102 \\
 c &{}= 6 / r \approx 0.7682 \\
 s &{}= -5 / r \approx -0.6402.
\end{align}
</math>

Using these values for {{mvar|c}} and {{mvar|s}} and performing the matrix multiplication above yields {{mvar|A<sub>2</sub>}}:
:<math>A_2 \approx \begin{bmatrix}   7.8102    &     4.4813    &    2.5607   \\
                                 0    &    -2.4327    &    3.0729   \\
                                 0    &          4    &         3   \\
       \end{bmatrix}</math>

Zeroing element {{gaps|(3,|2)}} finishes off the process. Using the same idea as before, the rotation matrix is:
:<math>G_{2} =
       \begin{bmatrix}   1    &    0    &    0   \\
                         0   &    c    &    -s     \\
                         0    &    s   &    c     \\
       \end{bmatrix}</math>

Afterwards, the following matrix multiplication is:
:<math>
\begin{align}
G_2 A_2 &{}= A_3 \\
&{}\approx \begin{bmatrix}   1    &    0    &    0   \\
                         0   &    c    &    -s     \\
                         0    &    s   &    c     \\
       \end{bmatrix}
       \begin{bmatrix}   7.8102    &    4.4813    &    2.5607   \\
                         0   &    -2.4327    &    3.0729     \\
                         0    &    4    &    3     \\
       \end{bmatrix},
\end{align}
</math>

where
:<math>\begin{align}
 r &{}\approx \sqrt{(-2.4327)^2 + 4^2} \approx 4.6817 \\
 c &{}\approx -2.4327 / r \approx -0.5196 \\
 s &{}\approx -4 / r \approx -0.8544.
\end{align}
</math>
Using these values for {{mvar|c}} and {{mvar|s}} and performing the multiplications results in {{mvar|A<sub>3</sub>}}:
:<math>A_3 \approx
       \begin{bmatrix}   7.8102    &    4.4813    &    2.5607   \\
                         0   &    4.6817    &    0.9665     \\
                         0    &    0    &    -4.1843     \\
       \end{bmatrix}.
</math>

This new matrix {{mvar|A<sub>3</sub>}} is the upper triangular matrix needed to perform an iteration of the [[QR decomposition]].  {{mvar|Q}} is now formed using the transpose of the rotation matrices in the following manner:

:<math>Q = G_{1}^T\, G_{2}^T.
</math>

Performing this matrix multiplication yields:
:<math>Q \approx
       \begin{bmatrix}   0.7682    &   0.3327    &    0.5470   \\
                         0.6402   &     -0.3992    &    -0.6564     \\
                         0    &    0.8544    &     -0.5196     \\
       \end{bmatrix}.</math>

This completes two iterations of the Givens Rotation and calculating the [[QR decomposition]] can now be done.

===QR iteration variant===
If performing the above calculations as a step in the [[QR algorithm]] for finding the eigenvalues of a matrix, then one next wants to compute the matrix <math> RQ </math>, but one should not do so by first multiplying <math> G_{1}^T </math> and <math> G_{2}^T </math> to form <math> Q </math>, instead rather by multiplying each <math> G_k^T </math> by <math> R G_1^T \dots G_{k-1}^T </math> (on the right). The reason for this is that each multiplication by a Givens matrix on the right changes only two columns of <math> R </math>, thus requiring a mere <math> O(n) </math> arithmetic operations, which for <math> n-1 </math> Givens rotations sums up to <math> O(n^2) </math> arithmetic operations; multiplying by the general <math> n \times n </math> matrix <math>Q</math> would require <math> O(n^3) </math> arithmetic operations. Likewise, storing the full <math>Q</math> matrix amounts to <math>n^2</math> elements, but each Givens matrix is fully specified by its pair <math>(c,s)</math> and <math> n-1 </math> of them can thus be stored in <math> 2n-2 </math> elements.

In the example,
<math display="block">
  \begin{aligned}
    R Q = A_3 (G_1^T G_2^T) ={}& (A_3 G_1^T) G_2^T
    \\ \approx{}&
    \begin{bmatrix}
      8.8687& -1.5575& 2.5607\\ 
      2.9972&  3.5965& 0.9665\\ 
      0&       0&     -4.1843
    \end{bmatrix} G_2^T
    \approx
    \begin{bmatrix}
      8.8687& 2.9972& 0.0\\ 
      2.9972&-1.0430&-3.5750\\
      0&     -3.5750& 2.1742
    \end{bmatrix}
  \end{aligned}
</math>