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

≠

, add

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.

Search Nedrilad ::

Custom Search