Page 349 - Matrix Analysis & Applied Linear Algebra

5.7 Orthogonal Reduction 345

Householder and Givens reductions are closely related to the results pro-
duced by applying the Gram–Schmidt process (p. 307) to the columns of A.
When A is nonsingular, Householder, Givens, and Gram–Schmidt each pro-
duce an orthogonal matrix Q and an upper-triangular matrix R such that
A = QR (Q = P T in the case of orthogonal reduction). The upper-triangular
matrix R produced by the Gram–Schmidt algorithm has positive diagonal en-
tries, and, as illustrated in Examples 5.7.1 and 5.7.2, we can also force this to be
true using the Householder or Givens reduction. This feature makes Q and R
unique.

QR Factorization

n×n
For each nonsingular A ∈ , there is a unique orthogonal matrix Q
and a unique upper-triangular matrix R with positive diagonal entries
such that
A = QR.

This “square” QR factorization is a special case of the more general
“rectangular” QR factorization discussed on p. 311.

Proof. Only uniqueness needs to be proven. If there are two QR factorizations

A = Q 1 R 1 = Q 2 R 2 ,

T
let U = Q Q 1 = R 2 R −1 . The matrix R 2 R −1 is upper triangular with positive
2
1
1
T
diagonal entries (Exercises 3.5.8 and 3.7.4) while Q Q 1 is an orthogonal matrix
2
(Exercise 5.6.5), and therefore U is an upper-triangular matrix whose columns
are an orthonormal set and whose diagonal entries are positive. Considering the
first column of U we see that




u 11

 0 
. =1 =⇒ u 11 = ±1 and u 11 > 0=⇒ u 11 =1,

 
.

 . 

0
so that U ∗1 = e 1 . A similar argument together with the fact that the columns
of U are mutually orthogonal produces
T
U U ∗2 =0 =⇒ u 12 =0 =⇒ u 22 =1 =⇒ U ∗2 = e 2 .
∗1
Proceeding inductively establishes that U ∗k = e k for each k (i.e., U = I ), and
therefore Q 1 = Q 2 and R 1 = R 2 .