The QR algorithm is an iterative method for computing the eigenvalues of a matrix.

At each step, we factor the current matrix, reverse the factors, and obtain a new matrix that is similar to the previous one.

  • Since \(Q_k\) is orthogonal, \(Q_k^{-1} = Q_k^T\).
  • Start with \(A_1 = Q_1 R_1\).
  • Form the next iterate by reversing the factors:
\[A_2 = R_1 Q_1 = Q_1^T A_1 Q_1 = Q_2 R_2\] \[A_3 = R_2 Q_2 = Q_2^T A_2 Q_2 = Q_2^T Q_1^T A_1 Q_1 Q_2 = Q_3 R_3\] \[\dots\] \[A_k = Q_{k-1}^T A_{k-1} Q_{k-1}\]

  • Therefore, every \(A_k\) is similar to \(A_1\), so they all have the same eigenvalues.

  • \(A_k\) converges to an upper triangular matrix, whose diagonal entries are the eigenvalues of \(A_1\).

Why do the matrices converge to triangular form?

  • Define:
\[P_k = Q_1 Q_2 \dots Q_k \quad \text{(orthogonal)}\] \[U_k = R_k R_{k-1} \dots R_1 \quad \text{(upper triangular)}\] \[A_1^k = P_k U_k\]
  • In particular, \(A_1 = Q_1 R_1\) and \(A_2 = R_1 Q_1\), so
\[A_1 Q_1 = Q_1 A_2\]
  • Repeating the same idea gives
\[A_1^2 = P_2 U_2\] \[A_1^3 = P_3 U_3\]
  • The columns of \(P_k\) are the orthonormalized columns of \(A_1^k\), so they approach the eigenvector directions as the power iteration effect dominates.
  • In that sense, the QR algorithm is repeatedly changing to a basis that becomes closer to the eigenvector basis.
  • For a symmetric matrix, this tends to a diagonal matrix; for a general matrix, the limit is typically triangular.

The animation below illustrates the process.