Page 154 - Matrix Analysis & Applied Linear Algebra

148 Chapter 3 Matrix Algebra
Example 3.10.3

Computing A −1 . Although matrix inversion is not used for solving Ax = b,
there are a few applications where explicit knowledge of A −1 is desirable.
Problem: Explain how to use the LU factors of a nonsingular matrix A n×n to
compute A −1 efficiently.
Solution: The strategy is to solve the matrix equation AX = I. Recall from
(3.5.5) that AA −1 = I implies A[A −1 ] ∗j = e j , so the j th column of A −1
is the solution of a system Ax j = e j . Each of these n systems has the same
coefficient matrix, so, once the LU factors for A are known, each system Ax j =
LUx j = e j can be solved by the standard two-step process.

(1) Set y j = Ux j , and solve Ly j = e j for y j by forward substitution.
(2) Solve Ux j = y j for x j =[A −1 ] ∗j by back substitution.

This method has at least two advantages: it’s efficient, and any code written to
solve Ax = b can also be used to compute A −1 .

Note: A tempting alternate solution might be to use the fact A −1 =(LU) −1 =
U −1 L −1 . But computing U −1 and L −1 explicitly and then multiplying the
results is not as computationally efficient as the method just described.

Not all nonsingular matrices possess an LU factorization. For example, there
is clearly no nonzero value of u 11 that will satisfy

01 1 0 u 11 u 12
= .
11 ' 21 1 0 u 22
The problem here is the zero pivot in the (1,1)-position. Our development of
the LU factorization using elementary lower-triangular matrices shows that if no
zero pivots emerge, then no row interchanges are necessary, and the LU factor-
ization can indeed be carried to completion. The converse is also true (its proof
is left as an exercise), so we can say that a nonsingular matrix A has an LU
factorization if and only if a zero pivot does not emerge during row reduction to
upper-triangular form with Type III operations.
Although it is a bit more theoretical, there is another interesting way to
characterize the existence of LU factors. This characterization is given in terms
of the leading principal submatrices of A that are defined to be those
submatrices taken from the upper-left-hand corner of A. That is,
 
a 11 a 12 ··· a 1k

 a 21 a 22 ···
a 11 a 12 a 2k 
A 1 = a 11 , A 2 = ,..., A k =  . . . .  ,....
a 21 a 22  . . . . . . . . 
a k1 a k2 ··· a kk