Page 162 - 35Linear Algebra

162 Matrices

7.7.2 Finding an LU Decomposition.

In chapter 2, section 2.3.4, Gaussian elimination was used to find LU matrix
decompositions. These ideas are presented here again as review.
For any given matrix, there are actually many different LU decomposi-
tions. However, there is a unique LU decomposition in which the L matrix
has ones on the diagonal. In that case L is called a lower unit triangular
matrix.
To find the LU decomposition, we’ll create two sequences of matrices
L 1 , L 2 , . . . and U 1 , U 2 , . . . such that at each step, L i U i = M. Each of the L i
will be lower triangular, but only the last U i will be upper triangular. The
main trick for this calculation is captured by the following example:

Example 98 (An Elementary Matrix)
Consider

1 0 a b c · · ·
E = , M = .
λ 1 d e f · · ·
Lets compute EM

a b c · · ·
EM = .
d + λa e + λb f + λc · · ·
Something neat happened here: multiplying M by E performed the row operation
R 2 → R 2 + λR 1 on M. Another interesting fact:

1 0
−1
E :=
−λ 1
obeys (check this yourself...)
E −1 E = 1 .

Hence M = E −1 EM or, writing this out

a b c · · · = 1 0 a b c · · · .
d e f · · · −λ 1 d + λa e + λb f + λc · · ·
Here the matrix on the left is lower triangular, while the matrix on the right has had
a row operation performed on it.

We would like to use the first row of M to zero out the first entry of every
row below it. For our running example,
 
6 18 3
M =  2 12 1  ,
4 15 3

162