Basics of Algebra, Topology, and Differential Calculus by Jean Gallier - HTML preview

Chapter 10

QR-Decomposition for Arbitrary

Matrices

10.1

Orthogonal Reflections

Hyperplane reflections are represented by matrices called Householder matrices. These ma-

trices play an important role in numerical methods, for instance for solving systems of linear

equations, solving least squares problems, for computing eigenvalues, and for transforming a

symmetric matrix into a tridiagonal matrix. We prove a simple geometric lemma that imme-

diately yields the QR-decomposition of arbitrary matrices in terms of Householder matrices.

Orthogonal symmetries are a very important example of isometries. First let us review

the definition of projections. Given a vector space E, let F and G be subspaces of E that

form a direct sum E = F ⊕ G. Since every u ∈ E can be written uniquely as u = v + w,

where v ∈ F and w ∈ G, we can define the two projections pF : E → F and pG : E → G such

that pF (u) = v and pG(u) = w. It is immediately verified that pG and pF are linear maps,

and that p2 = p

= p

F

F , p2

G

G, pF ◦ pG = pG ◦ pF = 0, and pF + pG = id.

Definition 10.1. Given a vector space E, for any two subspaces F and G that form a direct

sum E = F ⊕ G, the symmetry (or reflection) with respect to F and parallel to G is the

linear map s : E → E defined such that

s(u) = 2pF (u) − u,

for every u ∈ E.

Because pF + pG = id, note that we also have

s(u) = pF (u) − pG(u)

and

s(u) = u − 2pG(u),

281

282

CHAPTER 10. QR-DECOMPOSITION FOR ARBITRARY MATRICES

s2 = id, s is the identity on F , and s = −id on G. We now assume that E is a Euclidean

space of finite dimension.

Definition 10.2. Let E be a Euclidean space of finite dimension n. For any two subspaces

F and G, if F and G form a direct sum E = F ⊕ G and F and G are orthogonal, i.e.,

F = G⊥, the orthogonal symmetry (or reflection) with respect to F and parallel to G is the

linear map s : E → E defined such that

s(u) = 2pF (u) − u,

for every u ∈ E. When F is a hyperplane, we call s a hyperplane symmetry with respect to

F (or reflection about F ), and when G is a plane (and thus dim(F ) = n − 2), we call s a

flip about F .

For any two vectors u, v ∈ E, it is easily verified using the bilinearity of the inner product

that

u + v 2 − u − v 2 = 4(u · v).

Then, since

u = pF (u) + pG(u)

and

s(u) = pF (u) − pG(u),

since F and G are orthogonal, it follows that

pF (u) · pG(v) = 0,

and thus,

s(u) = u ,

so that s is an isometry.

Using Proposition 9.8, it is possible to find an orthonormal basis (e1, . . . , en) of E consist-

ing of an orthonormal basis of F and an orthonormal basis of G. Assume that F has dimen-

sion p, so that G has dimension n − p. With respect to the orthonormal basis (e1, . . . , en),

the symmetry s has a matrix of the form

Ip

0

.

0

−In−p

Thus, det(s) = (−1)n−p, and s is a rotation iff n − p is even. In particular, when F is

a hyperplane H, we have p = n − 1 and n − p = 1, so that s is an improper orthogonal

transformation. When F = {0}, we have s = −id, which is called the symmetry with respect

to the origin. The symmetry with respect to the origin is a rotation iff n is even, and an

improper orthogonal transformation iff n is odd. When n is odd, we observe that every

improper orthogonal transformation is the composition of a rotation with the symmetry

10.1. ORTHOGONAL REFLECTIONS

283

with respect to the origin. When G is a plane, p = n − 2, and det(s) = (−1)2 = 1, so that a

flip about F is a rotation. In particular, when n = 3, F is a line, and a flip about the line

F is indeed a rotation of measure π.

Remark: Given any two orthogonal subspaces F, G forming a direct sum E = F ⊕ G, let

f be the symmetry with respect to F and parallel to G, and let g be the symmetry with

respect to G and parallel to F . We leave as an exercise to show that

f ◦ g = g ◦ f = −id.

When F = H is a hyperplane, we can give an explicit formula for s(u) in terms of any

nonnull vector w orthogonal to H. Indeed, from

u = pH(u) + pG(u),

since pG(u) ∈ G and G is spanned by w, which is orthogonal to H, we have

pG(u) = λw

for some λ ∈ R, and we get

u · w = λ w 2,

and thus

(u · w)

pG(u) =

w.

w 2

Since

s(u) = u − 2pG(u),

we get

(u · w)

s(u) = u − 2

w.

w 2

Such reflections are represented by matrices called Householder matrices, and they play

an important role in numerical matrix analysis (see Kincaid and Cheney [61] or Ciarlet

[22]). Householder matrices are symmetric and orthogonal. It is easily checked that over an

orthonormal basis (e1, . . . , en), a hyperplane reflection about a hyperplane H orthogonal to

a nonnull vector w is represented by the matrix

W W

W W

H = In − 2

= I

,

W 2

n − 2 W W

where W is the column vector of the coordinates of w over the basis (e1, . . . , en), and In is

the identity n × n matrix. Since

(u · w)

pG(u) =

w,

w 2

284

CHAPTER 10. QR-DECOMPOSITION FOR ARBITRARY MATRICES

the matrix representing pG is

W W ,

W W

and since pH + pG = id, the matrix representing pH is

W W

In −

.

W W

These formulae can be used to derive a formula for a rotation of

3

R , given the direction w

of its axis of rotation and given the angle θ of rotation.

The following fact is the key to the proof that every isometry can be decomposed as a

product of reflections.

Proposition 10.1. Let E be any nontrivial Euclidean space. For any two vectors u, v ∈ E,

if u = v , then there is a hyperplane H such that the reflection s about H maps u to v,

and if u = v, then this reflection is unique.

Proof. If u = v, then any hyperplane containing u does the job. Otherwise, we must have

H = {v − u}⊥, and by the above formula,

(u · (v − u))

2 u 2 − 2u · v

s(u) = u − 2

(v − u) = u +

(v − u),

(v − u) 2

(v − u) 2

and since

(v − u) 2 = u 2 + v 2 − 2u · v

and u = v , we have

(v − u) 2 = 2 u 2 − 2u · v,

and thus, s(u) = v.

If E is a complex vector space and the inner product is Hermitian, Proposition 10.1

is false. The problem is that the vector v − u does not work unless the inner product

u · v is real! The proposition can be salvaged enough to yield the QR-decomposition in terms

of Householder transformations; see Gallier [42].

We now show that hyperplane reflections can be used to obtain another proof of the

QR-decomposition.

10.2

QR-Decomposition Using Householder Matrices

First, we state the result geometrically. When translated in terms of Householder matrices,

we obtain the fact advertised earlier that every matrix (not necessarily invertible) has a

QR-decomposition.

10.2. QR-DECOMPOSITION USING HOUSEHOLDER MATRICES

285

Proposition 10.2. Let E be a nontrivial Euclidean space of dimension n. For any orthonor-

mal basis (e1, . . ., en) and for any n-tuple of vectors (v1, . . ., vn), there is a sequence of n

isometries h1, . . . , hn such that hi is a hyperplane reflection or the identity, and if (r1, . . . , rn)

are the vectors given by

rj = hn ◦ · · · ◦ h2 ◦ h1(vj),

then every rj is a linear combination of the vectors (e1, . . . , ej), 1 ≤ j ≤ n. Equivalently, the

matrix R whose columns are the components of the rj over the basis (e1, . . . , en) is an upper

triangular matrix. Furthermore, the hi can be chosen so that the diagonal entries of R are

nonnegative.

Proof. We proceed by induction on n. For n = 1, we have v1 = λe1 for some λ ∈ R. If

λ ≥ 0, we let h1 = id, else if λ < 0, we let h1 = −id, the reflection about the origin.

For n ≥ 2, we first have to find h1. Let

r1,1 = v1 .

If v1 = r1,1e1, we let h1 = id. Otherwise, there is a unique hyperplane reflection h1 such that

h1(v1) = r1,1 e1,

defined such that

(u · w

h

1)

1(u) = u − 2

w

w 2

1

1

for all u ∈ E, where

w1 = r1,1 e1 − v1.

The map h1 is the reflection about the hyperplane H1 orthogonal to the vector w1 = r1,1 e1 −

v1. Letting

r1 = h1(v1) = r1,1 e1,

it is obvious that r1 belongs to the subspace spanned by e1, and r1,1 = v1 is nonnegative.

Next, assume that we have found k linear maps h1, . . . , hk, hyperplane reflections or the

identity, where 1 ≤ k ≤ n − 1, such that if (r1, . . . , rk) are the vectors given by

rj = hk ◦ · · · ◦ h2 ◦ h1(vj),

then every rj is a linear combination of the vectors (e1, . . . , ej), 1 ≤ j ≤ k. The vectors

(e1, . . . , ek) form a basis for the subspace denoted by U , the vectors (e

k

k+1, . . . , en) form

a basis for the subspace denoted by U , the subspaces U and U

are orthogonal, and

k

k

k

E = U

. Let

k ⊕ Uk

uk+1 = hk ◦ · · · ◦ h2 ◦ h1(vk+1).

We can write

uk+1 = uk+1 + uk+1,

286

CHAPTER 10. QR-DECOMPOSITION FOR ARBITRARY MATRICES

where u

and u

. Let

k+1 ∈ Uk

k+1 ∈ Uk

rk+1,k+1 = uk+1 .

If u

= r

k+1

k+1,k+1 ek+1, we let hk+1 = id. Otherwise, there is a unique hyperplane reflection

hk+1 such that

hk+1(uk+1) = rk+1,k+1 ek+1,

defined such that

(u · w

h

k+1)

k+1(u) = u − 2

w

w

2

k+1

k+1

for all u ∈ E, where

wk+1 = rk+1,k+1 ek+1 − uk+1.

The map hk+1 is the reflection about the hyperplane Hk+1 orthogonal to the vector wk+1 =

rk+1,k+1 ek+1 −u

. However, since u

, e

and U is orthogonal to U , the subspace

k+1

k+1

k+1 ∈ Uk

k

k

U is contained in H

, which belong to U , are

k

k+1, and thus, the vectors (r1, . . . , rk) and uk+1

k

invariant under hk+1. This proves that

hk+1(uk+1) = hk+1(uk+1) + hk+1(uk+1) = uk+1 + rk+1,k+1 ek+1

is a linear combination of (e1, . . . , ek+1). Letting

rk+1 = hk+1(uk+1) = uk+1 + rk+1,k+1 ek+1,

since uk+1 = hk ◦ · · · ◦ h2 ◦ h1(vk+1), the vector

rk+1 = hk+1 ◦ · · · ◦ h2 ◦ h1(vk+1)

is a linear combination of (e1, . . . , ek+1). The coefficient of rk+1 over ek+1 is rk+1,k+1 = u

,

k+1

which is nonnegative. This concludes the induction step, and thus the proof.

Remarks:

(1) Since every hi is a hyperplane reflection or the identity,

ρ = hn ◦ · · · ◦ h2 ◦ h1

is an isometry.

(2) If we allow negative diagonal entries in R, the last isometry hn may be omitted.

10.2. QR-DECOMPOSITION USING HOUSEHOLDER MATRICES

287

(3) Instead of picking rk,k = u , which means that

k

wk = rk,k ek − uk,

where 1 ≤ k ≤ n, it might be preferable to pick r

2

k,k = − u

if this makes w

k

k

larger, in which case

wk = rk,k ek + uk.

Indeed, since the definition of h

2

k involves division by

wk , it is desirable to avoid

division by very small numbers.

(4) The method also applies to any m-tuple of vectors (v1, . . . , vm), where m is not neces-

sarily equal to n (the dimension of E). In this case, R is an upper triangular n × m

matrix we leave the minor adjustments to the method as an exercise to the reader (if

m > n, the last m − n vectors are unchanged).

Proposition 10.2 directly yields the QR-decomposition in terms of Householder transfor-

mations (see Strang [100, 101], Golub and Van Loan [47], Trefethen and Bau [106], Kincaid

and Cheney [61], or Ciarlet [22]).

Theorem 10.3. For every real n × n matrix A, there is a sequence H1, . . ., Hn of matrices,

where each Hi is either a Householder matrix or the identity, and an upper triangular matrix

R such that

R = Hn · · · H2H1A.

As a corollary, there is a pair of matrices Q, R, where Q is orthogonal and R is upper

triangular, such that A = QR (a QR-decomposition of A). Furthermore, R can be chosen

so that its diagonal entries are nonnegative.

Proof. The jth column of A can be viewed as a vector vj over the canonical basis (e1, . . . , en)

of

n

E

(where (ej)i = 1 if i = j, and 0 otherwise, 1 ≤ i, j ≤ n). Applying Proposition 10.2

to (v1, . . . , vn), there is a sequence of n isometries h1, . . . , hn such that hi is a hyperplane

reflection or the identity, and if (r1, . . . , rn) are the vectors given by

rj = hn ◦ · · · ◦ h2 ◦ h1(vj),

then every rj is a linear combination of the vectors (e1, . . . , ej), 1 ≤ j ≤ n. Letting R be the

matrix whose columns are the vectors rj, and Hi the matrix associated with hi, it is clear

that

R = Hn · · · H2H1A,

where R is upper triangular and every Hi is either a Householder matrix or the identity.

However, hi ◦ hi = id for all i, 1 ≤ i ≤ n, and so

vj = h1 ◦ h2 ◦ · · · ◦ hn(rj)

for all j, 1 ≤ j ≤ n. But ρ = h1 ◦ h2 ◦ · · · ◦ hn is an isometry represented by the orthogonal

matrix Q = H1H2 · · · Hn. It is clear that A = QR, where R is upper triangular. As we noted

in Proposition 10.2, the diagonal entries of R can be chosen to be nonnegative.

288

CHAPTER 10. QR-DECOMPOSITION FOR ARBITRARY MATRICES

Remarks:

(1) Letting

Ak+1 = Hk · · · H2H1A,

with A1 = A, 1 ≤ k ≤ n, the proof of Proposition 10.2 can be interpreted in terms of

the computation of the sequence of matrices A1, . . . , An+1 = R. The matrix Ak+1 has

the shape

× × × uk+1



1

× × × ×

.

.

.

.

.

.

 0

..

..

..

..

..

.. 



×







 0

0 × uk+1

k

× × × ×

 0 0 0 uk+1



A



k+1

× × × ×

k+1 = 

 ,

 0

0

0 uk+1

k+2

× × × ×

 .

.

.

.

.

.

.

. 

 ..

..

..

..

..

..

..

.. 





 0

0

0 uk+1





n−1

× × × ×

0

0

0 uk+1

n

× × × ×

where the (k + 1)th column of the matrix is the vector

uk+1 = hk ◦ · · · ◦ h2 ◦ h1(vk+1),

and thus

uk+1 = uk+1

1

, . . . , uk+1

k

and

uk+1 = uk+1, uk+1, . . . , uk+1

k+1

k+2

n

.

If the last n − k − 1 entries in column k + 1 are all zero, there is nothing to do, and we

let Hk+1 = I. Otherwise, we kill these n − k − 1 entries by multiplying Ak+1 on the

left by the Householder matrix Hk+1 sending

0, . . . , 0, uk+1, . . . , uk+1

k+1

n

to (0, . . . , 0, rk+1,k+1, 0, . . . , 0),

where rk+1,k+1 = (uk+1, . . . , uk+1

k+1

n

) .

(2) If A is invertible and the diagonal entries of R are positive, it can be shown that Q

and R are unique.

(3) If we allow negative diagonal entries in R, the matrix Hn may be omitted (Hn = I).

(4) The method allows the computation of the determinant of A. We have

det(A) = (−1)mr1,1 · · · rn,n,

where m is the number of Householder matrices (not the identity) among the Hi.

10.3. SUMMARY

289

(5) The “condition number” of the matrix A is preserved (see Strang [101], Golub and Van

Loan [47], Trefethen and Bau [106], Kincaid and Cheney [61], or Ciarlet [22]). This is

very good for numerical stability.

(6) The method also applies to a rectangular m × n matrix. In this case, R is also an

m × n matrix (and it is upper triangular).

10.3

Summary

The main concepts and results of this chapter are listed below:

• Symmetry (or reflection) with respect to F and parallel to G.

• Orthogonal symmetry (or reflection) with respect to F and parallel to G; reflections,

flips.

• Hyperplane reflections and Householder matrices.

• A key fact about reflections (Proposition 10.1).

• QR-decomposition in terms of Householder transformations (Theorem 10.3).

290

CHAPTER 10. QR-DECOMPOSITION FOR ARBITRARY MATRICES