In this algorithm we begin by applying a Jacobi rotation,
from the left hand side only,
whose purpose is to annihilate
*A*_{n-1, n}, i.e., the
last superdiagonal element.

This rotation will usually
screw the tridiagonal form, so the tridiagonal form must be restored
either by using a Housholder or a Givens transformation. It turns
out that a single Givens transformation won't do though: it must be
followed by a serious of those, so as to comb away the non-tridiagonal
terms. A single iteration
will thus have a form:

(3.57) |

where

Now, the question is if this transformation
**Q**is going to be a correct
**Q** for a
**QL**iteration. There is a tricky lemma, which proves that this is indeed
the case:

**lemma**-

If**A**is a symmetric nonsingular matrix and , where**Q**is orthogonal and**B**is tridiagonal, not necessarily symmetric, with positive off-diagonal terms, then**Q**and**B**are fully determined by the last row of**Q**^{T}. **proof**-

Let**q**_{1}through**q**_{n}be the rows of matrix**Q**^{T}:

Since**Q**is orthogonal, can be multiplied by**Q**^{T}from the right yielding:

This can be written down in some detail as

The row of this equation can be written as

The rows**q**_{i}of matrix**Q**are orthonormal to each other, so if we multiply the above equation from the right by**q**_{n}^{T}, we get:

Once we know we can evaluate :

Using orthonormality of**q**_{i}:

and

And, therefore

We can now climb up towards and reconstructing the whole**B**and**Q**in this way.Quod erat demonstrandum.

The lemma is used by observing that equation:

which defines the iterative procedure for the

Once we have
**Q**^{T}_{s} we form the next iterate
**A**_{s+1}by:

In this method not only are shifts implicit. The
**QL**algorithm itself is masked. We rely on the lemma to demonstrate that
the computation, which at first glance looks quite different,
is equivalent to a
**QL** algorithm.