10.3. USING MULTIPLIERS TO FIND AN LU FACTORIZATION 207

Again, the product is unchanged because we just did and then undid a row operation. Fi-nally, we will add the second row to the bottom row and make the following changes 1 0 0

2 1 01 −1 1

 1 2 3

0 −3 −100 0 −11

 .

At this point, we stop because the matrix on the right is upper triangular. An LU factoriza-tion is the above.

The justification for this gimmick will be given later in a more general context.

Example 10.3.2 Find an LU factorization for A =

1 2 1 2 12 0 2 1 12 3 1 3 21 0 1 1 2

 .

▶▶We will use the same procedure as above. However, this time we will do everything

for one column at a time. First multiply the first row by (−1) and then add to the last row.Next take (−2) times the first and add to the second and then (−2) times the first and addto the third. 

1 0 0 02 1 0 02 0 1 01 0 0 1



1 2 1 2 10 −4 0 −3 −10 −1 −1 −1 00 −2 0 −1 1

 .

This finishes the first column of L and the first column of U. As in the above, what happenedwas this. Lots of row operations were done and then these were undone by multiplying bythe matrix on the left. Thus the above product equals the original matrix. Now take−(1/4)times the second row in the matrix on the right and add to the third followed by −(1/2)times the second added to the last.

1 0 0 02 1 0 02 1/4 1 01 1/2 0 1



1 2 1 2 10 −4 0 −3 −10 0 −1 −1/4 1/40 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.