Page 192 - Matrices theory and applications

The assertions made above have never been proved in full generality,
to our knowledge. We shall give below a rather satisfactory result in the
complex case.
10.2.2 The Case of a Singular Matrix 10.2. The QR Method 175
When A is not invertible, the QR factorization is not unique, raising a
difficulty in the definition of the algorithm. The computation of the deter-
minant would detect immediately the case of noninvertibility, but would
not provide any solution. However, if the matrix has been first reduced to
the Hessenberg form, then a single QR iteration detects the case and does
provide a solution. Indeed, if A is Hessenberg but not invertible, and if
A = QR,then Q is Hessenberg and R is not invertible. If a 21 =0, the
matrix A is block-triangular and we are reduced to the case of a matrix of
size (n − 1) × (n − 1) by deleting the first row and the first column. Oth-
erwise, there exists j ≥ 2such that r jj =0. The matrix A 1 = RQ is then
block-triangular, because it is Hessenberg and (A 1 ) j,j−1 = r jj q j,j−1 =0.
We are thus reduced to the computation of the spectra of two matrices of
sizes j × j and (n − j) × (n − j), the diagonal blocks of A 1 . After finitely
many such steps (not larger than the multiplicity of the null eigenvalue),
there remain only Hessenberg invertible matrices to deal with. We shall
assume therefore from now one that A ∈ GL n (K).

10.2.3 Complexity of an Iteration
An iteration of the QR method requires the factorization A j = Q j R j and
3
the computation of A j+1 = R j Q j . Each part costs O(n )operations if it
is done on a generic matrix (using the naive way of multiplying matrices).
Since the reduction to the Hessenberg form has a comparable cost, we loose
nothing by reducing A to this form. Actually, we make considerable gains
2
in two aspects. First, the cost of the QR iterations is reduced to O(n ).
Second, the cluster values of the sequence (A j ) j must have the Hessenberg
form too.
Let us examine first the Householder method of QR factorization for a
generic matrix A. In practice, one computes only the factor R and matri-
ces of unitary symmetries whose product is Q. One then multiplies these

unitary matrices by R on the left to obtain A = RQ.
n
Let a 1 ∈ CC be the first column vector of A. We begin by determining a
n
unit vector v 1 ∈ CC such that the hyperplane symmetry H 1 := I n − 2v 1 v ∗
1