10.6. THE PLU FACTORIZATION 211

product is of the form

1 0 · · · 0 0−M21 1 · · · 0 0

... −M32. . .

......

−M(M−1)1... · · · 1 0

−MM1 −MM2 · · · −MMM−1 1

In words, beginning at the left column and moving toward the right, you simply insert,

into the corresponding position in the identity matrix, −1 times the multiplier which wasused to zero out an entry in that position below the main diagonal in A, while retaining themain diagonal which consists entirely of ones. This is L.

10.6 The PLU FactorizationAs indicated above, some matrices don’t have an LU factorization. Here is an example.

M =

 1 2 3 21 2 3 04 3 1 1

 (10.2)

In this case, there is another factorization which is useful called a PLU factorization. HereP is a permutation matrix.

Example 10.6.1 Find a PLU factorization for the above matrix in 10.2.

Proceed as before trying to find the row echelon form of the matrix. First add −1 timesthe first row to the second row and then add −4 times the first to the third. This yields 1 0 0

1 1 04 0 1

 1 2 3 2

0 0 0 −20 −5 −11 −7

There is no way to do only row operations involving replacing a row with itself added to amultiple of another row to the matrix on the right in such a way as to obtain an upper trian-gular matrix. Therefore, consider the original matrix with the bottom two rows switched.

M′ =

 1 2 3 24 3 1 11 2 3 0

=

 1 0 00 0 10 1 0

 1 2 3 2

1 2 3 04 3 1 1

= PM

Now try again with this matrix. First take −1 times the first row and add to the bottom rowand then take −4 times the first row and add to the second row. This yields 1 0 0

4 1 01 0 1

 1 2 3 2

0 −5 −11 −70 0 0 −2

