14.2.2 The Case Of Real Eigenvalues
With these lemmas, it is possible to prove that for the QR algorithm and certain conditions, the
sequence Ak converges pointwise to an upper triangular matrix having the eigenvalues of A down
the diagonal. I will assume all the matrices are real here.
This convergence won’t always happen. Consider for example the matrix
verify quickly that the algorithm will return this matrix for each k.
The problem here is that,
although the matrix has the two eigenvalues −
they have the same absolute value. The QR
algorithm works in somewhat the same way as the power method, exploiting differences in the size
of the eigenvalues.
If A has all real eigenvalues and you are interested in finding these eigenvalues along with the
corresponding eigenvectors, you could always consider A + λI instead where λ is sufficiently large
and positive that A + λI has all positive eigenvalues. (Recall Gerschgorin’s theorem.) Then if μ is
an eigenvalue of A + λI with
so to find the eigenvalues of A you just subtract λ from the eigenvalues of A + λI. Thus
there is no loss of generality in assuming at the outset that the eigenvalues of A are all
positive. Here is the theorem. It involves a technical condition which will often hold.
The proof presented here follows  and is a special case of that presented in this
Before giving the proof, note that the product of upper triangular matrices is upper triangular.
If they both have positive entries on the main diagonal so will the product. Furthermore, the
inverse of an upper triangular matrix is upper triangular. I will use these simple facts without
much comment whenever convenient.
Theorem 14.2.5 Let A be a real matrix having eigenvalues
and suppose S−1 has an LU factorization. Then the matrices Ak in the QR algorithm described
above converge to an upper triangular matrix T′ having the eigenvalues of A, λ1,
descending on the main diagonal. The matrices Q
converge to Q′, an orthogonal matrix which
equals Q except for possibly having some columns multiplied by −
1 for Q the unitary part of the
QR factorization of S,
Proof: From Lemma 14.2.3
Let S = QR where this is just a QR factorization which is known to exist and let S−1 = LU which
is assumed to exist. Thus
That matrix in the middle, DkLD−k satisfies
Thus for j < i the expression converges to 0 because λj > λi when this happens. When i = j it
reduces to 1. Thus the matrix in the middle is of the form I + Ek where Ek → 0. Then it
where Fk → 0. Then let I + Fk = QkRk where this is another QR factorization. Then it reduces
This looks really interesting because by Lemma 14.2.4 Qk → I and Rk → I because
So it follows QQk
is an orthogonal matrix converging to Q
is upper triangular, being the product of upper triangular matrices. Unfortunately, it is not known
that the diagonal entries of this matrix are nonnegative because of the U. Let Λ be just like the
identity matrix but having some of the ones replaced with −1 in such a way that ΛU is an upper
triangular matrix having positive diagonal entries. Note Λ2 = I and also Λ commutes with a
diagonal matrix. Thus
At this point, one does some inspired massaging to write the above in the form
Now I claim the middle matrix in
is upper triangular and has all positive entries on the
diagonal. This is because it is an upper triangular matrix which is similar to the upper triangular
and so it has the same eigenvalues (diagonal entries) as RkR
. Thus the matrix
Gk ≡ Dk
is upper triangular and has all positive entries on the
diagonal. Multiply on the right by
where Q′ is essentially equal to Q but might have some of the columns multiplied by −1. This is
because Qk → I and so QkΛ → Λ. Now by Lemma 14.2.4, it follows
It remains to verify Ak converges to an upper triangular matrix. Recall that from 14.11 and
the definition below this (S = QR)
Where T is an upper triangular matrix. This is because it is the product of upper triangular
matrices R,D,R−1. Thus QTAQ = T. If you replace Q with Q′ in the above, it still
results in an upper triangular matrix T′ having the same diagonal entries as T. This is
and considering the iith entry yields
Recall from Lemma 14.2.3, Ak = Q
. Thus taking a limit and using the first
An easy case is for A symmetric. Recall Corollary 6.4.13. By this corollary, there exists an
orthogonal (real unitary) matrix Q such that
where D is diagonal having the eigenvalues on the main diagonal decreasing in size from the upper
left corner to the lower right.
Corollary 14.2.6 Let A be a real symmetric n × n matrix having eigenvalues
and let Q be defined by
where Q is orthogonal and D is a diagonal matrix having the eigenvalues on the main diagonal
decreasing in size from the upper left corner to the lower right. Let QT have an LU factorization.
Then in the QR algorithm, the matrices Q
converge to Q′ where Q′ is the same as Q except
having some columns multiplied by
. Thus the columns of Q′ are eigenvectors of A. The
matrices Ak converge to D.
Proof: This follows from Theorem 14.2.5. Here S = Q,S−1 = QT. Thus
and R = I. By Theorem 14.2.5 and Lemma 14.2.3,
because formula 14.13 is unaffected by replacing Q with Q′. ■
When using the QR algorithm, it is not necessary to check technical condition about S−1
having an LU factorization. The algorithm delivers a sequence of matrices which are similar to the
original one. If that sequence converges to an upper triangular matrix, then the algorithm worked.
Furthermore, the technical condition is sufficient but not necessary. The algorithm will work even
without the technical condition.
Example 14.2.7 Find the eigenvalues and eigenvectors of the matrix
It is a symmetric matrix but other than that, I just pulled it out of the air. By Lemma 14.2.3
it follows Ak = Q
. And so to get to the answer quickly I could have the computer raise
A to a power and then take the QR factorization of what results to get the kth iteration using the
above formula. Lets pick k = 10.
Now take QR factorization of this. The computer will do that also.
Next it follows
and this equals
By Gerschgorin’s theorem, the eigenvalues are pretty close to the diagonal entries of the above
matrix. Note I didn’t use the theorem, just Lemma 14.2.3 and Gerschgorin’s theorem
to verify the eigenvalues are close to the above numbers. The eigenvectors are close
Lets check one of these.
Now lets see how well the smallest approximate eigenvalue and eigenvector works.
For practical purposes, this has found the eigenvalues and eigenvectors.