Page 149 - Matrix Analysis & Applied Linear Algebra

3.10 The LU Factorization 143

is the partially triangularized result after k − 1 elimination steps, then

T T
T k A k−1 = I − c k e k A k−1 = A k−1 − c k e A k−1
k
   
∗∗· · · α 1 ∗· · · ∗ 0
 0 ∗· · · α 2 ∗· · · ∗   0 
 . . . . . . . . . . . .   . . 



 . . . . . .   . 



=  00 ··· α k ∗· · · ∗  , where c k =  0 


 00 ··· 0 ∗· · · ∗   α k+1 /α k 
   
 . . . . . .   . 
 . . . . . .   . 
. . . . . . .
00 ··· 0 ∗· · · ∗ α n /α k
contains the multipliers used to annihilate those entries below α k . Notice that
T
T k does not alter the first k − 1 columns of A k−1 because e [A k−1 ] =0
k ∗j
whenever j ≤ k−1. Therefore, if no row interchanges are required, then reducing
A to an upper-triangular matrix U by Gaussian elimination is equivalent to
executing a sequence of n − 1 left-hand multiplications with elementary lower-
triangular matrices. That is, T n−1 ··· T 2 T 1 A = U, and hence
−1 −1 −1
A = T 1 T 2 ··· T n−1 U. (3.10.4)
T
Making use of the fact that e c k = 0 whenever j ≤ k and applying (3.10.3)
j
reveals that

T −1 T −1 ··· T −1 = I + c 1 e T I + c 2 e T ··· I + c n−1 e T
1 2 n−1 1 2 n−1 (3.10.5)
T
T
= I + c 1 e + c 2 e + ··· + c n−1 e T .
1 2 n−1
By observing that
00 ··· 0 0 ··· 0
 
 00 ··· 0 0 ··· 0 
. . . . . . 

 . . . . . . 
 . . . . . . 
T
c k e =  00 ··· 0 0 ··· 0  ,


k
 00 ··· ' k+1,k 0 ··· 0 


 . . . . . . 
 . . . . . . 
. . . . . .
00 ··· ' nk 0 ··· 0
where the ' ik ’s are the multipliers used at the k th stage to annihilate the entries
below the k th pivot, it now follows from (3.10.4) and (3.10.5) that
A = LU,