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