132 CHAPTER 5. SOME FACTORIZATIONS

5.4 The PLU Factorization

As indicated above, some matrices don’t have an LU factorization. Here is an example.

M =

 1 2 3 2

1 2 3 0

4 3 1 1

 (5.1)

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

Example 5.4.1 Find a PLU factorization for the above matrix in 5.1.

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 0

4 0 1

 1 2 3 2

0 0 0 −2

0 −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 second matrix in such a way as to obtain an upper triangularmatrix. Therefore, consider M with the bottom two rows switched.

M ′ =

 1 2 3 2

4 3 1 1

1 2 3 0

 .

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

4 1 0

1 0 1

 1 2 3 2

0 −5 −11 −7

0 0 0 −2

The second matrix is upper triangular and so the LU factorization of the matrix M ′ is 1 0 0

4 1 0

1 0 1

 1 2 3 2

0 −5 −11 −7

0 0 0 −2

 .

Thus M ′ = PM = LU where L and U are given above. Therefore, M = P 2M = PLU andso  1 2 3 2

1 2 3 0

4 3 1 1

 =

 1 0 0

0 0 1

0 1 0

 1 0 0

4 1 0

1 0 1

 1 2 3 2

0 −5 −11 −7

0 0 0 −2

This process can always be followed and so there always exists a PLU factorization of a

given matrix even though there isn’t always an LU factorization.

Example 5.4.2 Use a PLU factorization of M ≡

 1 2 3 2

1 2 3 0

4 3 1 1

 to solve the system

Mx = b where b =(1, 2, 3)T.