130 CHAPTER 5. SOME FACTORIZATIONS

Note the method for updating the matrix on the left. The 2 in the second entry of the firstcolumn is there because −2 times the first row of A added to the second row of A produceda 0. Now replace the third row in the matrix on the right by −1 times the first row addedto the third. Thus the next step is 1 0 0

2 1 0

1 0 1

 1 2 3

0 −3 −10

0 3 −1

Finally, add the second row to the bottom row and make the following changes 1 0 0

2 1 0

1 −1 1

 1 2 3

0 −3 −10

0 0 −11

 .

At this point, stop because the matrix on the right is upper triangular. An LU factorizationis the above.

The justification for this gimmick will be given later.

Example 5.2.2 Find an LU factorization for A =

1 2 1 2 1

2 0 2 1 1

2 3 1 3 2

1 0 1 1 2

 .

This time everything is done at once for a whole column. This saves trouble. Firstmultiply the first row by (−1) and then add to the last row. Next take (−2) times the firstand add to the second and then (−2) times the first and add to the third.

1 0 0 0

2 1 0 0

2 0 1 0

1 0 0 1



1 2 1 2 1

0 −4 0 −3 −1

0 −1 −1 −1 0

0 −2 0 −1 1

 .

This finishes the first column of L and the first column of U. Now take − (1/4) times thesecond row in the matrix on the right and add to the third followed by − (1/2) times thesecond added to the last.

1 0 0 0

2 1 0 0

2 1/4 1 0

1 1/2 0 1



1 2 1 2 1

0 −4 0 −3 −1

0 0 −1 −1/4 1/4

0 0 0 1/2 3/2

This finishes the second column of L as well as the second column of U . Since the matrixon the right is upper triangular, stop. The LU factorization has now been obtained. Thistechnique is called Dolittle’s method. ▶▶

This process is entirely typical of the general case. The matrix U is just the first uppertriangular matrix you come to in your quest for the row reduced echelon form using onlythe row operation which involves replacing a row by itself added to a multiple of anotherrow. The matrix L is what you get by updating the identity matrix as illustrated above.

You should note that for a square matrix, the number of row operations necessary toreduce to LU form is about half the number needed to place the matrix in row reducedechelon form. This is why an LU factorization is of interest in solving systems of equations.