136 CHAPTER 5. SOME FACTORIZATIONS

each of which switches two rows, and L a lower triangular matrix having all ones on themain diagonal, L = L′

n−1 · · ·L′2L

′1, where the L

′j are obtained as just described by moving a

succession of Pk from the left to the right of Lj and modifying the jth column as indicated,such that LPA = U. Then A = PTL−1U .

It is customary to write this more simply as

A = PLU

where L is an upper triangular matrix having all ones on the diagonal and P is a permutationmatrix consisting of P1 · · ·Pn−1 as described above. This proves the following theorem.

Theorem 5.6.1 Let A be any invertible n × n matrix. Then there exists a permutationmatrix P and a lower triangular matrix L having all ones on the main diagonal and anupper triangular matrix U such that A = PLU .

5.7 The QR Factorization

As pointed out above, the LU factorization is not a mathematically respectable thing be-cause it does not always exist. There is another factorization which does always exist. Muchmore can be said about it than I will say here. At this time, I will only deal with real ma-trices and so the inner product will be the usual real dot product. Letting A be an m × nreal matrix and letting (·, ·) denote the usual real inner product,

(Ax,y) =∑i

(Ax)i yi =∑i

∑j

Aijxjyi =∑j

∑i

(AT)jiyixj

=∑j

(ATy

)jxj =

(x,ATy

)Thus, when you take the matrix across the comma, you replace with a transpose.

Definition 5.7.1 An n× n real matrix Q is called an orthogonal matrix if

QQT = QTQ = I.

Thus an orthogonal matrix is one whose inverse is equal to its transpose.

From the above observation,

|Qx|2 = (Qx, Qx) =(x,QTQx

)= (x,Ix) = (x,x) = |x|2

This shows that orthogonal transformations preserve distances. Conversely you can alsoshow that if you have a matrix which does preserve distances, then it must be orthogonal.

Example 5.7.2 One of the most important examples of an orthogonal matrix is the socalled Householder matrix. You have v a unit vector and you form the matrix

I − 2vvT

This is an orthogonal matrix which is also symmetric. To see this, you use the rules ofmatrix operations. (

I − 2vvT)T

= IT −(2vvT

)T= I − 2vvT