10.7. THE QR FACTORIZATION 215

As in the above problem Q1a1 = b and so Q1A=

(|a1| ∗0 A2

)where A2 is a m−1×n−1

matrix. Now find in the same way as was just done a n−1×n−1 matrix Q̂2 such that

Q̂2A2 =

(∗ ∗0 A3

)

Let Q2 ≡

(1 00 Q̂2

).Then

Q2Q1A =

(1 00 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 (10.3)

where R is upper triangular.Now if Q1 and Q2 are orthogonal, then from properties of matrix multiplication,

Q1Q2 (Q1Q2)T = Q1Q2QT

2 QT1 = Q1IQT

1 = I

and similarly(Q1Q2)

T Q1Q2 = I.

Thus the product of orthogonal matrices is orthogonal. Also the transpose of an orthogonalmatrix is orthogonal directly from the definition. Therefore, from 10.3

A = (QpQp−1 · · ·Q1)T R≡ QR,

where Q is orthogonal. This suggests the proof of the following theorem.

Theorem 10.7.5 Let A be any real m× n matrix. Then there exists an orthogonal matrixQ and an upper triangular matrix R having nonnegative entries down the main diagonalsuch that

A = QR

and this factorization can be accomplished in a systematic manner.

Proof: The theorem is clearly true if A is a 1×m matrix. Suppose it is true for A ann×m matrix. Thus, if A is any n×m matrix, there exists an orthogonal matrix Q such that

QA = R

where R is upper triangular. Suppose A is an (n+1)×m matrix. Then, as indicated above,there exists an orthogonal (n+1)× (n+1) matrix Q1 such that

Q1A =

(a b0 A1

)