Similar matrices with changing entries
An eigenvalue algorithm can change a matrix without changing its eigenvalues. In unshifted QR iteration, one factors the current matrix and multiplies the factors in reverse order.
Definition 5.5.1
(Unshifted QR iteration)
Starting from , factor and recombine:
Here is orthogonal and is upper triangular. For nonsingular matrices we choose the unique QR factorization with positive diagonal in .
The last equality shows that is orthogonally similar to , so symmetry and the eigenvalues are preserved. The hope is that the matrices become nearly diagonal, making their diagonal entries useful eigenvalue approximations.
We will prove that behavior for a specific two-dimensional setting, not for every matrix.
Theorem 5.5.2
(Convergence of QR iteration for a symmetric 2-by-2 matrix)
Let be real symmetric positive definite with orthonormal eigenvectors and eigenvalues . Assume the first coordinate vector has a nonzero component along :
Then converges to , with off-diagonal magnitude and diagonal errors . If , the off-diagonal entry is already zero.
Why QR iteration follows powers of the original matrix
Set and . Repeated similarity gives .
Lemma 5.5.3
(Iterates give the QR factorization of powers)
For every ,
and this is the positive-diagonal QR factorization of .
Proof
(Induction on the power)
Start with the identity at (the empty product is ). Then , so multiplying the induction hypothesis by gives . The product of the is upper triangular with positive diagonal, so (1) is the positive-diagonal QR factorization of .
With (1) available, the convergence theorem reduces to power iteration on .
Proof
(Reading the iterates off the first column)
The first column of the factorization (1) is . Expanding in the eigenbasis,
The tangent of the angle between its line and the line of is exactly . Its orthogonal unit companion approaches the line of . In this moving orthonormal basis, the magnitude of the off-diagonal element is ; the first diagonal error is , and the second has the opposite error. Thus the off-diagonal is and the diagonal errors are .
Proof X-ray
One algorithm, two viewpoints
QR iteration repeatedly changes coordinates: is written in an orthonormal basis that depends on . Equation (1) says that this basis comes from the QR factorization of , whose first column is ordinary power iteration on ; the second column is then fixed by orthogonality, so one column suffices in two dimensions. The positive diagonals of the fix the signs, so the first basis vector is . The hypothesis keeps the angle away from a right angle, and makes its tangent decay. Positive definiteness is used only to make the order of the eigenvalues agree with the order of their magnitudes.
Example and stopping information
Worked example 5.5.4
(The first iterate by hand)
For the eigenvalues are and , and , so . For the first step, the columns of are and . Gram-Schmidt gives and ; then and the remainder has length , so the second column of is . Therefore
This agrees with the formulas of the proof: gives and , so the off-diagonal entry is and the first diagonal entry is .
Corollary 5.5.5
(Spectral interval from a diagonal entry)
For a symmetric iterate , some eigenvalue of lies in , and some eigenvalue lies in .
Proof
(Residual of a coordinate vector)
The residual of the unit vector with approximate eigenvalue is , of norm . For a symmetric matrix, a unit vector with residual norm for the value forces an eigenvalue within of : expanding the vector in an orthonormal eigenbasis, the squared residual is . The matrices and have the same eigenvalues. The same argument applies to and .
This is an exact-arithmetic residual certificate.
Worked example 5.5.6
(Later iterates and spectral intervals)
Continue with . With the formulas give , and , since the trace is :
| 0 | 2 | 1 | 2 |
| 1 | 2.8 | 0.6 | 1.2 |
| 2 | 2.97561 | 0.21951 | 1.02439 |
| 3 | 2.99726 | 0.07397 | 1.00274 |
At the two intervals and coincide, both equal to , so they cannot be used to separate the eigenvalues. At they are and , and at they are and : the interval radius shrinks by a factor approaching at each step, as the rate predicts.
Common mistake
(Counting two overlapping intervals as two eigenvalues)
Each interval certifies that some eigenvalue lies in it. If the two diagonal intervals overlap, as they do at above, the certificate does not say that they identify different eigenvalues; both may refer to the same one.
Worked example 5.5.7
(A matrix already diagonal in the right order)
For , , so and . The positive-diagonal factorization is , , so , and every iterate equals . The off-diagonal entry is zero from the start, as the theorem states for .
What the hypotheses prevent
Counterexample mode
A symmetric matrix that QR iteration never changes
It is tempting to expect every real symmetric matrix to be driven to diagonal form. Take . It is symmetric and orthogonal, with eigenvalues and . Its positive-diagonal QR factorization is , so every QR iterate equals and its off-diagonal entry never vanishes. Here alternates between and , so its line does not converge. This indefinite example falls outside the positive-definite theorem; equal eigenvalue magnitudes defeat its power-iteration argument. Every iterate has the correct spectrum, yet the matrix does not move: orthogonal similarity alone does not force the off-diagonal entries to decrease.
Common mistake
(Expecting the larger eigenvalue to come first)
Even for positive definite , the initial component matters for the stated ordering: if , then , so and the hypothesis fails. The iteration remains diagonal in that order. It has converged as a diagonal matrix, but not to .
Practical QR eigensolvers use additional ideas such as shifts and deflation; their convergence and floating-point analysis require separate arguments.
Practice with solutions
Quick check
(Why does have the same eigenvalues as ?)
Write in terms of .
Solution · Answer
with orthogonal, so is similar to , and similar matrices have the same characteristic polynomial.
Quick check
(Under the positive definite theorem, what determines the geometric rate of the first basis direction?)
Look at the tangent of the angle .
Solution · Answer
The geometric rate is ; the initial coefficient ratio controls the multiplicative constant. The diagonal errors have rate per step.
Quick check
(For a symmetric iterate with diagonal entry and off-diagonal entry , give a spectral interval certified by the first column.)
Use the residual .
Solution · Answer
At least one eigenvalue lies in .
Quick check
(What happens for , and which theorem hypothesis fails for ordering the larger eigenvalue first?)
Which eigenvector does equal?
Solution · Answer
Every iterate is the same diagonal matrix; has zero component in the eigendirection, so fails.