Linear Algebra

5.2 Finding An LU Factorization

There is a convenient procedure for finding an LU factorization. It turns out that it is only necessary to keep track of the multipliers which are used to row reduce to upper triangular form. This procedure is described in the following examples and is called the multiplier method. It is due to Dolittle.

Write the matrix next to the identity matrix as shown.

( ) ( ) 1 0 0 1 2 3 |( 0 1 0 |) |( 2 1 − 4 |) . 0 0 1 1 5 2

The process involves doing row operations to the matrix on the right while simultaneously updating successive columns of the matrix on the left. First take −2 times the first row and add to the second in the matrix on the right.

( ) ( ) 1 0 0 1 2 3 |( 2 1 0 |) |( 0 − 3 − 10 |) 0 0 1 1 5 2

Note the method for updating the matrix on the left. The 2 in the second entry of the first column is there because −2 times the first row of A added to the second row of A produced a 0. Now replace the third row in the matrix on the right by −1 times the first row added to the third. Thus the next step is

( ) ( ) | 1 0 0 | | 1 2 3 | ( 2 1 0 ) ( 0 − 3 − 10 ) 1 0 1 0 3 − 1

Finally, add the second row to the bottom row and make the following changes

( ) ( ) 1 0 0 1 2 3 |( 2 1 0 |) |( 0 − 3 − 10 |) . 1 − 1 1 0 0 − 11

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

The justification for this gimmick will be given later.

This time everything is done at once for a whole column. This saves trouble. First multiply the first row by

and then add to the last row. Next take times the first and add to the second and then times the first and add to the third.

( ) ( ) 1 0 0 0 1 2 1 2 1 || 2 1 0 0 || || 0 − 4 0 − 3 − 1 || |( 2 0 1 0 |) |( 0 − 1 − 1 − 1 0 |) . 1 0 0 1 0 − 2 0 − 1 1

This finishes the first column of L and the first column of U. Now take −

times the second row in the matrix on the right and add to the third followed by − times the second added to the last.

( ) ( ) 1 0 0 0 1 2 1 2 1 || 2 1 0 0 || || 0 − 4 0 − 3 − 1 || |( 2 1∕4 1 0 |) |( 0 0 − 1 − 1∕4 1∕4 |) 1 1∕2 0 1 0 0 0 1∕2 3∕2

This finishes the second column of L as well as the second column of U. Since the matrix on the right is upper triangular, stop. The LU factorization has now been obtained. This technique is called Dolittle’s method. ▸▸

This process is entirely typical of the general case. The matrix U is just the first upper triangular matrix you come to in your quest for the row reduced echelon form using only the row operation which involves replacing a row by itself added to a multiple of another row. 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 to reduce to LU form is about half the number needed to place the matrix in row reduced echelon form. This is why an LU factorization is of interest in solving systems of equations.