Any real matrix, symmetric or not, can be decomposed into either
of the forms:

A |
= | (3.55) | |

A |
= | (3.56) |

where

It is easy to see how such a decomposition can be eventuated by
applying, for example, Householder rotations or Givens rotations
to matrix
**A**, in order to annihilate everything below
the diagonal. Observe that these will not be full similarity
transformations, in other words they are not going to be
.
Remember
that we have acted with
**P** on
from the right in order to do to rows, what application of
**P**^{T} to
**A** from the left did to the columns.
So if we just leave
alone, we'll
be left with a new matrix
,
with, say, *k*-th
column zeroed under the diagonal.
An accumulation of those
**P**_{i}^{T} is some combined rotation
transformation
**Q**^{T}, such that

Multiplying by

quod erat demonstrandum.

Now, once we have done all that hard work and found both
**Q** and
**R**, by merely changing the
order, i.e., replacing
with
we eventuate a
similarity transformation on
**A**:

This is called the
**QR** transformation
of matrix
**A** and it has the following properties:

- 1.
- it preserves symmetry of
**A** - 2.
- it preserves triadiagonal form of
**A** - 3.
- it preserves Hessenberg form of
**A**

The
**QR** algorithm now works as follows.
Once you have a tridiagonal matrix
**A**, you

- 1.
- find its decomposition
- 2.
- generate
- 3.
- find the
decomposition of
**A**_{1} - 4.
- generate
- 5.
- find the
decomposition
of
**A**_{2} - 6.
- generate
- 7.

**theorem**-
- 1.
- If a general real, not necessarily symmetric
matrix
**A**has eigenvalues of different absolute value then the sequence**A**_{i}, as defined by the**QR**transformations of**A**, converges to an upper triangular form, with eigenvalues of**A**appearing on the diagonal in increasing order of their absolute magnitude. - 2.
- If
**A**has an eigenvalue of multiplicity*p*then**A**_{i}still converges to an upper triangular form with the exception for a diagonal block matrix of order*p*whose eigenvalues are .

Which is why the combination of the Householder triadiagonalization followed by theQRtransformations is such an efficient method for finding eigenvalues of a symmetric matrix.

If there is a degenerate eigenvalue, i.e., a value
of
multiplicity *p*, then at the end of this procedure
there will be *p*-1 non-vanishing elements on the super and sub-diagonal,
that correspond to that value. Those elements then determine a submatrix
that can be cut out of the original matrix
**A** and
diagonalized separately, for example, by evaluating a characteristic
polynomial, or by Jacobi iterations.

There is nothing sacred about
**QR** versus
**QL**, so everything that's been said about
**QR** works just as well for
**QL**. But when you write a program, of course,
you must choose one or the other. Since academics have a long history
of leaning towards the left, we're going to choose
**QL** in our example code too.