Page 124 - Matrix Analysis & Applied Linear Algebra

118 Chapter 3 Matrix Algebra

Although we usually try to avoid computing the inverse of a matrix, there are
times when an inverse must be found. To construct an algorithm that will yield
A −1 when A n×n is nonsingular, recall from Example 3.7.2 that determining
A −1 is equivalent to solving the single matrix equation AX = I, and due to
(3.5.5), this in turn is equivalent to solving the n linear systems defined by

Ax = I ∗j for j =1, 2,...,n. (3.7.10)
In other words, if X ∗1 , X ∗2 ,..., X ∗n are the respective solutions to (3.7.10), then
X =[X ∗1 | X ∗2 |···| X ∗n ] solves the equation AX = I, and hence X = A −1 .
If A is nonsingular, then we know from (3.7.7) that the Gauss–Jordan method
reduces the augmented matrix [A | I ∗j ]to[I | X ∗j ], and the results of §1.3 insure
that X ∗j is the unique solution to Ax = I ∗j . That is,
Gauss–Jordan −1 !
[A | I ∗j ] −−−−−−−−→ I [A ] ∗j .

But rather than solving each system Ax = I ∗j separately, we can solve them
simultaneously by taking advantage of the fact that they all have the same
coefficient matrix. In other words, applying the Gauss–Jordan method to the
larger augmented array [A | I ∗1 | I ∗2 |···| I ∗n ] produces
" #

Gauss–Jordan −1 −1 −1
[A | I ∗1 | I ∗2 |···| I ∗n ] −−−−−−−−→ I [A ] ∗1 [A ] ∗2 ··· [A ] ∗n ,
or more compactly,
Gauss–Jordan −1
[A | I] −−−−−−−−→ [I | A ]. (3.7.11)
What happens if we try to invert a singular matrix using this procedure?
The fact that (3.7.5) ⇐⇒ (3.7.6) ⇐⇒ (3.7.7) guarantees that a singular matrix
A cannot be reduced to I by Gauss–Jordan elimination because a zero row will
have to emerge in the left-hand side of the augmented array at some point during
the process. This means that we do not need to know at the outset whether A
is nonsingular or singular—it becomes self-evident depending on whether or not
the reduction (3.7.11) can be completed. A summary is given below.

Computing an Inverse

Gauss–Jordan elimination can be used to invert A by the reduction
Gauss–Jordan −1
[A | I] −−−−−−−−→ [I | A ]. (3.7.12)

The only way for this reduction to fail is for a row of zeros to emerge
in the left-hand side of the augmented array, and this occurs if and only
if A is a singular matrix. A different (and somewhat more practical)
algorithm is given Example 3.10.3 on p. 148.