Page 157 - Matrix Analysis & Applied Linear Algebra

3.10 The LU Factorization 151

When row interchanges are allowed, zero pivots can always be avoided when the
original matrix A is nonsingular. Consequently, we may conclude that for every
nonsingular matrix A, there exists a permutation matrix P (a product of
elementary interchange matrices) such that PA has an LU factorization. Fur-
thermore, because of the observation in (3.10.14) concerning how the multipliers
˜
in T k and T k trade places when a row interchange occurs, and because
−1 T
˜ −1

T
T = I − ˜ c k e = I + ˜ c k e ,
k k k
it is not difficult to see that the same line of reasoning used to arrive at (3.10.6)
can be applied to conclude that the multipliers in the matrix L in (3.10.15) are
permuted according to the row interchanges that are executed. More specifically,
if rows k and k+i are interchanged to create the k th pivot, then the multipliers
( ' k1 ' k2 ··· ' k,k−1 ) and ( ' k+i,1 ' k+i,2 ··· ' k+i,k−1 )
trade places in the formation of L.
This means that we can proceed just as in the case when no interchanges are
used and successively overwrite the array originally containing A with each mul-
tiplier replacing the position it annihilates. Whenever a row interchange occurs,
the corresponding multipliers will be correctly interchanged as well. The per-
mutation matrix P is simply the cumulative record of the various interchanges
used, and the information in P is easily accounted for by a simple technique
that is illustrated in the following example.
Example 3.10.4
Problem: Use partial pivoting on the matrix
1 2 −3 4
 
 4 8 12 −8 
2 3 2 1
A =  
−3 −1 1 −4
and determine the LU decomposition PA = LU, where P is the associated
permutation matrix.
Solution: As explained earlier, the strategy is to successively overwrite the array
A with components from L and U. For the sake of clarity, the multipliers ' ij
are shown in boldface type. Adjoin a “permutation counter column” p that
is initially set to the natural order 1,2,3,4. Permuting components of p as the
various row interchanges are executed will accumulate the desired permutation.
The matrix P is obtained by executing the final permutation residing in p to
the rows of an appropriate size identity matrix:
1 2 −3 4 1 4 8 12 −8 2
   
 4 8 12 −8 2   1 2 −3 4 1 
2 3 2 1 3 2 3 2 1 3
[A|p]=   −→  
−3 −1 1 −4 4 −3 −1 1 −4 4