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.