Page 155 - Matrix Analysis & Applied Linear Algebra

3.10 The LU Factorization 149

Existence of LU Factors
Each of the following statements is equivalent to saying that a nonsin-
gular matrix A n×n possesses an LU factorization.
• A zero pivot does not emerge during row reduction to upper-
triangular form with Type III operations.
• Each leading principal submatrix A k is nonsingular. (3.10.12)

Proof. We will prove the statement concerning the leading principal submatri-
ces and leave the proof concerning the nonzero pivots as an exercise. Assume
first that A possesses an LU factorization and partition A as

L 11 0 U 11 U 12 L 11 U 11 ∗
A = LU = = ,
L 21 L 22 0 U 22 ∗ ∗
where L 11 and U 11 are each k × k. Thus A k = L 11 U 11 must be nonsingular
because L 11 and U 11 are each nonsingular—they are triangular with nonzero
diagonal entries. Conversely, suppose that each leading principal submatrix in
A is nonsingular. Use induction to prove that each A k possesses an LU fac-
torization. For k =1, this statement is clearly true because if A 1 =(a 11 )is
nonsingular, then A 1 = (1)(a 11 ) is its LU factorization. Now assume that A k
has an LU factorization and show that this together with the nonsingularity
condition implies A k+1 must also possess an LU factorization. If A k = L k U k
is the LU factorization for A k , then A −1 = U −1 L −1 so that
k k k
−1
b 0 L b
A k L k U k k
A k+1 = = −1 −1 , (3.10.13)
T
T
c T c U 1 0 α k+1 − c A b
α k+1
k k
where c T and b contain the first k components of A k+1∗ and A ∗k+1 , re-
spectively. Observe that this is the LU factorization for A k+1 because
−1
0 L b
L k U k k
L k+1 = −1 and U k+1 = −1
T
T
c U 1 0 α k+1 − c A b
k k
are lower- and upper-triangular matrices, respectively, and L has 1’s on its
diagonal while the diagonal entries of U are nonzero. The fact that
T
α k+1 − c A −1 b
=0
k
follows because A k+1 and L k+1 are each nonsingular, so U k+1 = L −1
k+1 A k+1
must also be nonsingular. Therefore, the nonsingularity of the leading principal