Page 159 - 35Linear Algebra

7.7 LU Redux 159

7.7 LU Redux

Certain matrices are easier to work with than others. In this section, we
2
will see how to write any square matrix M as the product of two simpler
matrices. We will write
M = LU ,

where:
• L is lower triangular. This means that all entries above the main
i
i
diagonal are zero. In notation, L = (l ) with l = 0 for all j > i.
j j
 
l 1 0 0 · · ·
1
 2 l 2 0 · · · 
l
 1 2 
L =  3 l 3 l 3 · · · 
l
 1 2 3 
. . . . . . . . . .
.
.
• U is upper triangular. This means that all entries below the main
i
i
diagonal are zero. In notation, U = (u ) with u = 0 for all j < i.
j
j
 
u 1 u 1 u 1 · · ·
1 2 3
0 u u
 2 2 · · · 
 2 3 
U =  0 0 u 3 · · · 
. . . . . . . . . .
 3 
.
.
M = LU is called an LU decomposition of M.
This is a useful trick for computational reasons; it is much easier to com-
pute the inverse of an upper or lower triangular matrix than general matrices.
Since inverses are useful for solving linear systems, this makes solving any lin-
ear system associated to the matrix much faster as well. The determinant—a
very important quantity associated with any square matrix—is very easy to
compute for triangular matrices.

Example 96 Linear systems associated to upper triangular matrices are very easy to
solve by back substitution.

a b 1 e 1 be
⇒ y = , x = 1 −
0 c e c a c
2
The case where M is not square is dealt with at the end of the section.

159