138 CHAPTER 5. SOME FACTORIZATIONS
With the solution to this simple problem, here is how to obtain a QR factorization forany matrix A. Let
A = (a1,a2, · · · ,an)where the ai are the columns. If a1 = 0, let Q1 = I. If a1 ̸= 0, let
b ≡
|a1|0...
0
and form the Householder matrix
Q1 ≡ I − 2(a1 − b)
|a1 − b|2(a1 − b)
T
As in the above problem Q1a1 = b and so
Q1A =
(|a1| ∗0 A2
)where A2 is am−1×n−1 matrix. Now find in the same way as was just done am−1×m−1matrix Q̂2 such that
Q̂2A2 =
(∗ ∗0 A3
)Let
Q2 ≡
(1 0
0 Q̂2
).
Then
Q2Q1A =
(1 0
0 Q̂2
)(|a1| ∗0 A2
)
=
|a1| ∗ ∗... ∗ ∗0 0 A3
Continuing this way until the result is upper triangular, you get a sequence of orthogonalmatrices QpQp−1 · · ·Q1 such that
QpQp−1 · · ·Q1A = R (5.4)
where R is upper triangular.Now if Q1 and Q2 are orthogonal, then from properties of matrix multiplication,
Q1Q2 (Q1Q2)T= Q1Q2Q
T2Q
T1 = Q1IQ
T1 = I
and similarly(Q1Q2)
TQ1Q2 = I.
Thus the product of orthogonal matrices is orthogonal. Also the transpose of an orthogonalmatrix is orthogonal directly from the definition. Therefore, from 5.4
A = (QpQp−1 · · ·Q1)TR ≡ QR.
This proves the following theorem.