The QR and QL Algorithms

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

$$\boldsymbol{Q}\cdot\boldsymbol{R}, \>\hbox{or}$$ A = (3.55)

$$\boldsymbol{Q}\cdot\boldsymbol{L}$$ A = (3.56)

where R is the upper triangular matrix (the right part) that includes the diagonal, L is the lower triangular matrix (the left part) that includes the diagonal, and Q is a rotation matrix.

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 $\boldsymbol{P}^T\cdot\boldsymbol{A}\cdot\boldsymbol{P}$. Remember that we have acted with P on $\boldsymbol{P}^T\cdot\boldsymbol{A}$ 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 $\boldsymbol{P}^T\cdot\boldsymbol{A}$ alone, we'll be left with a new matrix $\boldsymbol{\tilde A}$, 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

$$\boldsymbol{Q}^T\cdot\boldsymbol{A} = \boldsymbol{R}$$

Multiplying by Q from the left yields:

$$\boldsymbol{A} = \boldsymbol{Q}\cdot\boldsymbol{R}$$

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 $\boldsymbol{Q}\cdot\boldsymbol{R}$with $\boldsymbol{R}\cdot\boldsymbol{Q}$ we eventuate a similarity transformation on A:

$$\boldsymbol{R}\cdot\boldsymbol{Q} = \boldsymbol{Q}^T\cdot\boldsymbol{A}\cdot\boldsymbol{Q} = \boldsymbol{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

A Hessenberg matrix is a matrix with everything under the diagonal and under the one line that is under the diagonal (like in a tridiagonal matrix) set to zero.

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

1.

find its $\boldsymbol{Q}\cdot\boldsymbol{R}$ decomposition

2.

generate $\boldsymbol{A}_1 = \boldsymbol{R}\cdot\boldsymbol{Q}$

3.

find the $\boldsymbol{Q}_1\cdot\boldsymbol{R}_1$ decomposition of A₁

4.

generate $\boldsymbol{A}_2 = \boldsymbol{R}_1\cdot\boldsymbol{Q}_1$

5.

find the $\boldsymbol{Q}_2\cdot\boldsymbol{R}_2$ decomposition of A₂

6.

generate $\boldsymbol{A}_3 = \boldsymbol{R}_2\cdot\boldsymbol{Q}_2$

7.

$\ldots$

and so on, until the off-diagonal elements vanish. Now, will they vanish? Will this whole process really end up in diagonalization of matrix A?

theorem

$\,$

1.

If a general real, not necessarily symmetric matrix A has eigenvalues of different absolute value $\vert\lambda_i\vert$ 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 $\vert\lambda_i\vert$ 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 $\lambda_i$.

The workload for this algorithm is ${\cal O}(n^3)$ per iteration for a general matrix, but only ${\cal O}(n)$ per iteration for a tridiagonal matrix, and ${\cal O}(n^2)$ for a Hessenberg matrix.

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

If there is a degenerate eigenvalue, i.e., a value $\vert\lambda_i\vert$ 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.