Computing All Eigenvalues with QR Iteration

Repeated Basis Changes Preserve the Eigenvalues

The $\mathrm{QR}$ algorithm computes all eigenvalues of a square matrix through repeated changes of basis. Each step produces a $similar matrix$ , so the eigenvalues stay the same. The iteration aims for a diagonal or Schur form, where eigenvalues are read from diagonal entries or small diagonal blocks. Convergence requires suitable shift and deflation strategies.

The version below is the unshifted $\mathrm{QR}$ iteration. Production eigensolvers also use shifts, reduce the matrix to Hessenberg form, and deflate converged blocks to improve speed and numerical reliability.

One QR Iteration

For the deflation test below, first reduce the matrix by unitary similarity to $upper Hessenberg form$ , whose entries below the first subdiagonal are zero. Start the iteration with that matrix. In the 2×2 example below, this condition already holds.

Start with $A_0=A$ .
Factor the current matrix into a unitary or orthogonal factor $Q_k$ and an upper triangular factor $R_k$ :

$A_k=Q_kR_k$
Reverse the order of the factors to obtain the next iterate:

$A_{k+1}=R_kQ_k$
Repeat the factorization and reverse multiplication. A small subdiagonal entry can be set to zero when it is negligible relative to its neighboring diagonal entries. That split, called $deflation$ , isolates a converged eigenvalue or block.

$\begin{aligned} &|(A_k)_{j+1,j}| \\ &\leq \tau\left(|(A_k)_{j,j}|+|(A_k)_{j+1,j+1}|\right) \end{aligned}$

Here $\tau$ is a tolerance chosen for the numerical precision and scale of the problem. Merely observing small changes in the diagonal is not a sufficient stopping test because the matrix can still have significant entries below the diagonal.

Why the Eigenvalues Stay the Same

Because $Q_k$ is unitary, $Q_k^{*}Q_k=I$ . Substituting $R_k=Q_k^{*}A_k$ into the reverse product gives

A_{k+1}=R_kQ_k

$A_{k+1}$ is unitarily similar to $A_k$ . $Similar matrices have the same characteristic polynomial$ and therefore the same eigenvalues. Each $\mathrm{QR}$ step expresses the same linear transformation in new coordinates.

What the Iteration Converges To

The final form depends on the matrix and the $number system$ used.

Matrix	Converged form	How to read the eigenvalues
Real symmetric or complex Hermitian	Diagonal matrix	The diagonal entries are the real eigenvalues
General complex	Upper triangular Schur form	The diagonal entries are the eigenvalues
General real	Quasi-upper-triangular real Schur form	Each $1\times1$ block gives a real eigenvalue. Each $2\times2$ block gives a complex-conjugate pair

The eigenvalues can appear in any order. Repeated values and special arrangements need separate handling because a strict magnitude ordering does not cover them.

Unshifted iteration does $not always converge to the listed form$ . For example, the symmetric matrix below admits $Q=C$ and $R=I$ , so the next iterate is unchanged:

C=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad C=CI,\qquad RQ=IC=C

Its eigenvalues are 1 and −1. Their equal magnitudes show why practical algorithms need appropriate shifts and convergence checks.

Worked Symmetric Example

Consider the symmetric matrix

A_0=\begin{pmatrix}2&1\\1&2\end{pmatrix}

One $\mathrm{QR}$ factorization and reverse multiplication give

\begin{aligned} &Q_0=\frac{1}{\sqrt5}\begin{pmatrix}2&-1\\1&2\end{pmatrix}, \\ &R_0=\begin{pmatrix}\sqrt5&\frac4{\sqrt5}\\0&\frac3{\sqrt5}\end{pmatrix} \end{aligned}

The $off-diagonal magnitude$ has already fallen from $1$ to $3/5$ . Further iterations drive both off-diagonal entries toward zero:

A_k\longrightarrow\begin{pmatrix}3&0\\0&1\end{pmatrix}

The limiting diagonal contains the eigenvalues $3$ and $1$ . Every iterate is similar to $A_0$ , so these values belong to the original matrix.