Game Development Reference
In-Depth Information
A method similar to that used to transform a matrix into its reduced form (see
Algorithm 3.6) can also be used to calculate the inverse of a matrix. To find the
inverse of an nn
matrix M by concatenat-
ing the identity matrix to the right of M , as shown below.
matrix M , we first construct an nn
×
×
M
M
10
0
M
11
12
1
n
MM
M
01
0
21
22
2
n
M
=
(3.34)
     
MM
M
00
1
n
1
n
2
nn
Performing elementary row operations on the entire matrix M until the left side
nn
matrix becomes the identity matrix I yields the inverse of M in the right
side nn
×
matrix. This process is known as Gauss-Jordan elimination and is illus-
trated in Algorithm 3.12.
×
Algorithm 3.12. Gauss-Jordan Elimination. This algorithm calculates the in-
verse of an nn
×
matrix M .
A. Construct the augmented matrix M given in Equation (3.34). Through-
out this algorithm, M refers to the current state of the augmented ma-
trix, not the original state.
B. Set the column j equal to 1. We will loop through columns 1 to n .
M has the largest absolute value. If
C. Find the row i with i
j
such that
ij
M
0
no such row exists for which
, then M is not invertible.
ij
D. If i
j
, then exchange rows i and j using elementary row operation (a)
under Definition 3.3. This is the pivot operation necessary to remove
zeros from the main diagonal and to provide numerical stability.
M . This sets the
, jj entry of M to 1 using ele-
E. Multiply row j by 1
(
)
jj
mentary row operation (b).
times row j to row r .
M
F. For each row r where 1
≤≤
rn
and r
j
rj
This step clears each entry above and below row j in column j to 0 using
elementary row operation (c).
G. If j
<
n
, increment j and loop to step C.
The implementation of Algorithm 3.12 is straightforward and has the benefit
that it can determine whether a matrix is invertible. The following example
demonstrates the inner workings of the algorithm.