Page 150 - Matrix Analysis & Applied Linear Algebra

144 Chapter 3 Matrix Algebra

where
1 0 0 ··· 0
 
1 0
 ' 21 ··· 0 

T
T
L = I + c 1 e + c 2 e + ··· + c n−1 e T =  ' 32 1 ··· 0  (3.10.6)
 ' 31
n−1
1
2
 . . . . . 
 . . . .
. . . . . . 
' n1 ' n2 ' n3 ··· 1
is the lower-triangular matrix with 1’s on the diagonal, and where ' ij is precisely
the multiplier used to annihilate the (i, j) -position during Gaussian elimination.
Thus the factorization A = LU can be viewed as the matrix formulation of
Gaussian elimination, with the understanding that no row interchanges are used.
LU Factorization
If A is an n × n matrix such that a zero pivot is never encountered
when applying Gaussian elimination with Type III operations, then A
can be factored as the product A = LU, where the following hold.
• L is lower triangular and U is upper triangular. (3.10.7)
• ' ii = 1 and u ii
= 0 for each i =1, 2,...,n. (3.10.8)
• Below the diagonal of L, the entry ' ij is the multiple of row j that
is subtracted from row i in order to annihilate the (i, j) -position
during Gaussian elimination.

• U is the final result of Gaussian elimination applied to A.
• The matrices L and U are uniquely determined by properties
(3.10.7) and (3.10.8).
The decomposition of A into A = LU is called the LU factorization
of A, and the matrices L and U are called the LU factors of A.

Proof. Except for the statement concerning the uniqueness of the LU fac-
tors, each point has already been established. To prove uniqueness, observe
that LU factors must be nonsingular because they have nonzero diagonals. If
L 1 U 1 = A = L 2 U 2 are two LU factorizations for A, then

L −1 L 1 = U 2 U −1 . (3.10.9)
2 1
Notice that L −1 L 1 is lower triangular, while U 2 U −1 is upper triangular be-
2
1
cause the inverse of a matrix that is upper (lower) triangular is again up-
per (lower) triangular, and because the product of two upper (lower) trian-
gular matrices is also upper (lower) triangular. Consequently, (3.10.9) implies
L −1 L 1 = D = U 2 U −1 must be a diagonal matrix. However, [L 2 ] ii =1=
2 1
[L −1 ] ii , so it must be the case that L −1 L 1 = I = U 2 U −1
2 2 1 , and thus L 1 = L 2
and U 1 = U 2 .