LU Decomposition

LU decomposition is used to write a square matrix as a product of an upper triangular matrix and a lower triangular matrix. Gaussian elimination is used to obtain the upper triangular matrix and the steps to obtain the upper triangular matrix are recorded and used to obtain the lower triangular matrix.

Consider the matrix:

We start the process of Gaussian elimination by subtracting 2 times the first row from the second row. In order to record what we have done, we will put the multiplier, 2, into the place it was used to make a zero, i.e. the second row,first column. In order to make it clear that it is a record of the step and not an element of the matrix, we will put it in parentheses, obtaining

The zero in the lower left corner requires no action. We record this fact with a (0).

To eliminate the 2 in the third row, second column, we need to subtract −2 times the second row from the third row. Recording the −2 in the spot it was used we have:

Let U be the upper triangular matrix produced, and let L be the lower triangular matrix with the

records and ones on the diagonal, i.e.:

A is the product of L and U.

When a matrix can be written as a product of simpler matrices, we call that a decomposition of and this one we call the LU decomposition. The decomposition is not unique in general.