Questions: QR Algorithm

Question 1

In the QR algorithm, why do all iterates A₀, A₁, A₂, ... share the same eigenvalues?

• A. The QR decomposition preserves eigenvalues because Q is unitary
• B. Each A_{k+1} = R_k Q_k is similar to A_k via A_{k+1} = Q_k^T A_k Q_k, and similar matrices have identical eigenvalues
• C. The iterates are all equal to A₀ scaled by different constants
• D. Eigenvalues are preserved because R_k is upper triangular

Answer: (B)

Since A_k = Q_k R_k, we have R_k = Q_k^T A_k (because Q_k is orthogonal). Therefore A_{k+1} = R_k Q_k = Q_k^T A_k Q_k — a similarity transformation. Similar matrices represent the same linear transformation in different bases and always have identical eigenvalues. Every QR iteration is a similarity transformation, so eigenvalues are invariants of the entire sequence.

Question 2

After many iterations of the QR algorithm, what form does the sequence converge toward, and what does it reveal?

• A. A diagonal matrix with eigenvectors on the diagonal
• B. A lower triangular form with eigenvalues on the sub-diagonal
• C. An upper triangular (Schur) form with eigenvalues on the main diagonal
• D. The zero matrix, because repeated factorization reduces all entries

Answer: (C)

The QR algorithm converges to an upper triangular Schur form (or block upper triangular for matrices with complex eigenvalue pairs). In this form, the eigenvalues appear on the main diagonal. The convergence is driven by the same mechanism as the power method — subspaces corresponding to dominant eigenvalues are progressively revealed — but applied simultaneously to all eigenvalues at once.

Question 3

The QR algorithm can find primarily the largest eigenvalue of a matrix, similar to the power method.

• T. True
• F. False

Answer: False

False. This is exactly the limitation the QR algorithm was designed to overcome. The power method finds only the dominant eigenvalue (largest in magnitude). The QR algorithm generalizes this: each iteration implicitly runs a power-method-like process on all invariant subspaces simultaneously, keeping them orthogonal to each other via QR factorization. The result is convergence to all eigenvalues at once — it is the algorithm behind the 'eig' function in every numerical computing environment.

Question 4

Each iterate A_k in the QR algorithm is similar to the original matrix A, meaning all iterates share the same eigenvalues.

• T. True
• F. False

Answer: True

True. A_{k+1} = Q_k^T A_k Q_k is a similarity transformation of A_k, so A_{k+1} is similar to A_k. By transitivity, every A_k is similar to A₀ = A. Since similar matrices have identical eigenvalues, all iterates share the same eigenvalues as A. This is the key structural guarantee of the algorithm: eigenvalues are invariants of the sequence, even as the off-diagonal entries diminish toward zero.

Question 5

What property makes the step A_{k+1} = R_k Q_k the right choice in the QR algorithm, and why does this guarantee the eigenvalues are preserved?

Model answer: Swapping factors to R_k Q_k ensures A_{k+1} is similar to A_k: since A_k = Q_k R_k and Q_k is orthogonal, R_k = Q_k^T A_k, so A_{k+1} = R_k Q_k = Q_k^T A_k Q_k — a similarity transformation. Similar matrices have identical eigenvalues, so every iterate preserves the eigenvalues of the original matrix A while the off-diagonal entries converge toward zero.

The insight is that similarity transformations preserve eigenvalues while changing the representation basis. By repeatedly applying QR-based similarity transformations, we drive the matrix toward a basis in which eigenvalues are revealed on the diagonal — without ever changing what those eigenvalues are.