## Unit10.3.3Simple tridiagonal QR algorithm

Now, consider the $4 \times 4$ tridiagonal matrix

\begin{equation*} \left( \begin{array}{c c c c} \alpha_{0,0} \amp \alpha_{0,1} \amp 0 \amp 0 \\ \alpha_{1,0} \amp \alpha_{1,1} \amp \alpha_{1,2} \amp 0 \\ 0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\ 0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\ \end{array} \right). \end{equation*}

From $\left( \begin{array}{c} \alpha_{0,0} \\ \alpha_{1,0} \end{array} \right),$ one can compute $\gamma_{1,0}$ and $\sigma_{1,0}$ so that

\begin{equation*} \left( \begin{array}{c c} \gamma_{1,0} \amp -\sigma_{1,0} \\ \sigma_{1,0} \amp \gamma_{1,0} \end{array} \right)^T \left( \begin{array}{c} \alpha_{0,0} \\ \alpha_{1,0} \end{array} \right) = \left( \begin{array}{c} \widehat{\alpha}_{0,0} \\ 0 \end{array} \right) . \end{equation*}

Then

\begin{equation*} \left( \begin{array}{| c c | c c} \hline {\widehat{\alpha}_{0,0} } \amp \widehat{\alpha}_{0,1} \amp \widehat{\alpha}_{0,2} \amp 0 \\ 0 \amp \widehat{\alpha}_{1,1} \amp \widehat{\alpha}_{1,2} \amp 0 \\ \hline 0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\ 0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \end{array} \right) = \left( \begin{array}{|c c | c c} \hline \gamma_{1,0} \amp \sigma_{1,0} \amp 0 \amp 0 \\ - \sigma_{1,0} \amp \gamma_{1,0} \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \end{array} \right) \left( \begin{array}{| c c | c | c}\hline \alpha_{0,0} \amp \alpha_{0,1} \amp 0 \amp 0 \\ \alpha_{1,0} \amp \alpha_{1,1} \amp \alpha_{1,2} \amp 0 \\ \hline 0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\ 0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \end{array} \right)\text{.} \end{equation*}

Next, from $\left( \begin{array}{c} \widehat{\alpha}_{1,1} \\ \alpha_{2,1} \end{array} \right) \text{,}$ one can compute $\gamma_{2,1}$ and $\sigma_{2,1}$ so that

\begin{equation*} \left( \begin{array}{c c} \gamma_{2,1} \amp -\sigma_{2,1} \\ \sigma_{2,1} \amp \gamma_{2,1} \end{array} \right)^T \left( \begin{array}{c} \widehat{\alpha}_{1,1} \\ \alpha_{2,1} \end{array} \right) = \left( \begin{array}{c} \widehat{\widehat{\alpha}}_{1,1} \\ 0 \end{array} \right) . \end{equation*}

Then

\begin{equation*} \left( \begin{array}{c | c c | c } \widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp \widehat{\alpha}_{0,2} \amp 0 \\ \hline 0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp \widehat{\widehat{\alpha}}_{1,2} \amp \widehat{\widehat{\alpha}}_{1,3} \\ 0 \amp 0 \amp \widehat{\alpha}_{2,2} \amp \widehat{\alpha}_{2,3} \\ \hline 0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\ \end{array} \right) = \left( \begin{array}{c | c c | c} 1 \amp 0 \amp 0 \amp 0 \\ \hline 0 \amp \gamma_{2,1} \amp \sigma_{2,1} \amp 0 \\ 0 \amp - \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline 0 \amp 0 \amp 0 \amp 1 \end{array} \right) \left( \begin{array}{c | c c | c } \widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp \widehat{\alpha}_{0,2} \amp 0 \\ \hline 0 \amp \widehat{\alpha}_{1,1} \amp \widehat{\alpha}_{1,2} \amp 0 \\ 0 \amp \alpha_{2,1} \amp \alpha_{2,2} \amp \alpha_{2,3} \\ \hline 0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\ \end{array} \right) \end{equation*}

Finally, from $\left( \begin{array}{c} \widehat{\alpha}_{2,2} \\ \alpha_{3,2} \end{array} \right),$ one can compute $\gamma_{3,2}$ and $\sigma_{3,2}$ so that $\left( \begin{array}{c c} \gamma_{3,2} \amp -\sigma_{3,2} \\ \sigma_{3,2} \amp \gamma_{3,2} \end{array} \right)^T \left( \begin{array}{c} \widehat{\alpha}_{2,2} \\ \alpha_{3,2} \end{array} \right) = \left( \begin{array}{c} \widehat{\widehat{\alpha}}_{2,2} \\ 0 \end{array} \right) \text{.}$ Then

\begin{equation*} \left( \begin{array}{c c | c c |} \widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp \widehat{\alpha}_{0,2} \amp 0 \\ 0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp \widehat{\widehat{\alpha}}_{1,2} \amp \widehat{\widehat{\alpha}}_{1,3} \\ \hline 0 \amp 0 \amp \widehat{\widehat{\alpha}}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\ 0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3} \\ \hline \end{array} \right) = \left( \begin{array}{c c | c c |} 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp \gamma_{3,2} \amp \sigma_{3,2} \\ 0 \amp 0 \amp - \sigma_{3,2} \amp \gamma_{3,2} \\ \hline \end{array} \right) \left( \begin{array}{c c | c c |} \widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp \widehat{\alpha}_{0,2} \amp 0 \\ 0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp \widehat{\widehat{\alpha}}_{1,2} \amp \widehat{\widehat{\alpha}}_{1,3} \\ \hline 0 \amp 0 \amp \widehat{\alpha}_{2,2} \amp \widehat{\alpha}_{2,3} \\ 0 \amp 0 \amp \alpha_{3,2} \amp \alpha_{3,3} \\ \hline \end{array} \right) \end{equation*}

The matrix $Q$ is the orthogonal matrix that results from multiplying the different Givens' rotations together:

$$Q = \left( \begin{array}{| c c | c c} \hline \gamma_{1,0} \amp - \sigma_{1,0} \amp 0 \amp 0 \\ \sigma_{1,0} \amp \gamma_{1,0} \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \end{array} \right) \left( \begin{array}{c | c c | c} 1 \amp 0 \amp 0 \amp 0 \\ \hline 0 \amp\gamma_{2,1} \amp - \sigma_{2,1} \amp 0 \\ 0 \amp \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline 0 \amp 0 \amp 0 \amp 1 \end{array} \right) \left( \begin{array}{c c | c c |} 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\ 0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline \end{array} \right).\label{chapter10-eqn-Q1}\tag{10.3.1}$$

However, it needs not be explicitly formed, as we exploit next.

The next question is how to compute $R Q$ given the QR factorization of the tridiagonal matrix. We notice that

\begin{equation*} \begin{array}{r} \underbrace{ \left( \begin{array}{| c c | c c} \hline \widehat{\alpha}_{0,0} \amp \widehat{\alpha}_{0,1} \amp \widehat{\alpha}_{0,2} \amp 0 \\ 0 \amp \widehat{\widehat{\alpha}}_{1,1} \amp \widehat{\widehat{\alpha}}_{1,2} \amp \widehat{\widehat{\alpha}}_{1,3} \\ \hline 0 \amp 0 \amp \widehat{\widehat{\alpha}}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\ 0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3} \end{array} \right) \left( \begin{array}{| c c | c c} \hline \gamma_{1,0} \amp - \sigma_{1,0} \amp 0 \amp 0 \\ \sigma_{1,0} \amp \gamma_{1,0} \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \end{array} \right) } \left( \begin{array}{c | c c | c} 1 \amp 0 \amp 0 \amp 0 \\ \hline 0 \amp\gamma_{2,1} \amp - \sigma_{2,1} \amp 0 \\ 0 \amp \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline 0 \amp 0 \amp 0 \amp 1 \end{array} \right) \left( \begin{array}{c c | c c |} 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\ 0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline \end{array} \right) \\ \underbrace{ \left( \begin{array}{| c c | c c} \hline \tilde{\alpha}_{0,0} \amp \tilde{\alpha}_{0,1} \amp \color{gray}{\widehat{\alpha}_{0,2}} \amp 0 \\ \tilde{\alpha}_{1,0} \amp \tilde{\widehat{\alpha}}_{1,1} \amp \widehat{\widehat{\alpha}}_{1,2} \amp \widehat{\widehat{\alpha}}_{1,3} \\ \hline 0 \amp 0 \amp \widehat{\widehat{\alpha}}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\ 0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3} \end{array} \right) \hspace{0.75in} \phantom{ \left( \begin{array}{c | c c | c} 1 \amp 0 \amp 0 \amp 0 \\ \hline 0 \amp\gamma_{2,1} \amp - \sigma_{2,1} \amp 0 \\ 0 \amp \sigma_{2,1} \amp \gamma_{2,1} \amp 0 \\ \hline 0 \amp 0 \amp 0 \amp 1 \end{array} \right) } } \phantom{ \left( \begin{array}{c c | c c |} 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\ 0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline \end{array} \right) } \\ \underbrace{ \left( \begin{array}{c | c c | c} \tilde{\alpha}_{0,0} \amp \tilde{\tilde{\alpha}}_{0,1} \amp \color{gray}{\tilde{\alpha}_{0,2}} \amp 0 \\ \hline \tilde{\alpha}_{1,0} \amp \tilde{\tilde{\alpha}}_{1,1} \amp \tilde{\alpha}_{1,2} \amp \widehat{\widehat{\alpha}}_{1,3} \\ 0 \amp \tilde{\alpha}_{2,1} \amp \tilde{\alpha}_{2,2} \amp \widehat{\widehat{\alpha}}_{2,3} \\ \hline 0 \amp 0 \amp 0 \amp \widehat{\alpha}_{3,3} \end{array} \right) \hspace{1.1in} \phantom{ \left( \begin{array}{c c | c c |} 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \\ \hline 0 \amp 0 \amp \gamma_{3,2} \amp - \sigma_{3,2} \\ 0 \amp 0 \amp \sigma_{3,2} \amp \gamma_{3,2} \\ \hline \end{array} \right) } } \\ \left( \begin{array}{c c | c c |} \tilde{\alpha}_{0,0} \amp \tilde{\tilde{\alpha}}_{0,1} \amp \color{gray}{\tilde{\alpha}_{0,2}} \amp 0 \\ \tilde{\alpha}_{1,0} \amp \tilde{\tilde{\alpha}}_{1,1} \amp \tilde{\tilde{\alpha}}_{1,2} \amp \color{gray} {\tilde{\alpha}_{1,3}}\\ \hline 0 \amp \tilde{\alpha}_{2,1} \amp \tilde{\tilde{\alpha}}_{2,2} \amp \tilde{\alpha}_{2,3} \\ 0 \amp 0 \amp \tilde{\alpha}_{3,2} \amp \tilde{\alpha}_{3,3} \\ \hline \end{array} \right). \hspace{1.1in} ~ \end{array} \end{equation*}

A symmetry argument can be used to motivate that $\tilde{\alpha}_{0,2} = \tilde{\alpha}_{1,3}= 0$ (which is why they appear in gray, if you look carefully). This also explains why none of the elements above the first superdiagonal become nonzero.

###### Remark10.3.3.1.

An important observation is that if $A$ is tridiagonal, then $A \rightarrow Q R$ (QR factorization) followed by $A := R Q$ again yields a tridiagonal matrix. In other words, any QR algorithm previously discussed (simple, shifted, with deflation) when started with a tridiagonal matrix will generate a succession of tridiagonal matrices.