Game Development Reference

In-Depth Information

E E
that

satisfy Equation (3.47) is impossible. This is true because singular matrices are

exactly those whose rows form a linearly dependent set, as the following theorem

states.

If a matrix
M
is singular, then finding elementary matrices

,

,

,

12

k

Theorem 3.15.
An
nn

matrix
M
is invertible if and only if the rows of
M

form a linearly independent set of vectors.

×

Proof.
Let the rows of
M
be denoted by

RR

TT

,

,

. We prove this theorem

,

T

1

2

n

in two parts.

(a) We prove that if
M
is invertible, then the rows of
M
form a linearly inde-

pendent set of vectors by proving the contrapositive, which states that if the

rows of
M
form a linearly dependent set of vectors, then
M
must be singular.

So assume that the rows of
M
are linearly dependent. Then there exists a row

r
that can be written as a linear combination of
k
other rows of the matrix as

follows.

T

T

T

T

(3.48)

RR R

=

a

+

a

+

+

a

R

r

1

s

2

s

k

s

1

2

k

The values of
a
are scalars, and the values of
s
index
k
rows in the ma-

trix
M
other than row
r
. Let the
nn

matrix
E
be equal to the elementary

matrix representing the addition of
a
times row
s
to row
r
. Then we can

write

×

E
,

M

=

EE

′

(3.49)

kk

−

1

1

′

where

M
is equal to
M
, except that row
r
has been replaced by all zeros. By

Theorem 3.9, the matrix

′

M
is singular, and thus
M
is singular.

(b) Now assume that the rows of
M
form a linearly independent set of vectors.

We first observe that performing elementary row operations on a matrix does

not alter the property of linear independence within the rows. Running

through Algorithm 3.12, if step C fails, then rows
j
through
n
of the matrix at

that point form a linearly dependent set since the number of columns for

which the rows

T

R
through
T
R
have at least one nonzero entry is less than the

number of rows itself. This is a contradiction, so step C of the algorithm can-

not fail, and
M
must be invertible.

Search Nedrilad ::

Custom Search