Schneider P., Eberly D.H. Geometric Tools for Computer Graphics
Подождите немного. Документ загружается.
34 Chapter 2 Matrices and Linear Systems
by 1, and that multiplication by a scalar matrix αI is equivalent to multiplication by
the scalar α.
2.5.2 Triangular Matrices
Two particularly important types of triangular matrices are termed upper triangular
and lower triangular—these are matrices that have, respectively, all 0 elements below
and above the diagonal:
M =
a
1,1
a
1,2
··· a
1,n
0 a
2,2
··· a
2,n
.
.
.
.
.
.
.
.
.
.
.
.
00··· a
n,n
M =
a
1,1
0 ··· 0
a
2,1
a
2,2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
a
n,1
a
n,2
··· a
n,n
Triangular matrices have some useful properties as well:
i. If A and B are lower triangular, then C = AB is lower triangular, and similarly for
upper triangular.
ii. If A and B are lower triangular, then C =A + B is lower triangular, and similarly
for upper triangular.
iii. If A is an invertible lower triangular matrix, its inverse A
−1
is lower triangular,
and similarly for upper triangular (Section 2.5.4 covers the inverse of a matrix).
Triangular matrices are particularly important in the representation and solution
of linear systems, as can be seen in Sections 2.4.4 and A.1.
2.5.3 The Determinant
The determinant of a square matrix (it’s not defined for nonsquare matrices) is a real
number, which can be computed in a variety of ways. For 2 × 2 and 3 × 3 matri-
ces, there are some reasonably intuitive interpretations/uses of the determinant (see
Sections 3.3.2 and 4.4.4), but in the general case, the various definitions and com-
putation schemes seem rather arbitrary. In 2D, a matrix M maps a unit square with
vertices
0, ı, , ı + to a parallelogram with vertices
0, ı M, M, (ı +)M. The area
of the parallelogram is |det(M)|.Ifdet(M)>0, then the counterclockwise ordering
of the square’s vertices is preserved by M (that is, the parallelogram’s vertices are also
2.5 Square Matrices 35
ordered counterclockwise); if det(M)<0, then the corresponding parallelogram’s
vertices are ordered clockwise. In 3D, a matrix M with nonzero determinant maps the
unit cube to a parallelepiped, whose volume is |det(M)|. Vertex ordering preservation
is analogous to the 2D case.
Terminology
We’ll start with some terminology: given a matrix M, the determinant of M is notated
as det(M) or
|
M
|
. The “vertical bar” notation is frequently applied to the matrices as
well; for example, if we have
M =
a
1,1
a
1,2
a
2,1
a
2,2
we can write det(M) as
|
M
|
=
a
1,1
a
1,2
a
2,1
a
2,2
Special Solutions for 2 ×2 and 3 × 3 Matrices
Because they’re so common, here are the formulas for the 2 ×2 and 3 × 3 cases:
a
1,1
a
1,2
a
2,1
a
2,2
= a
1,1
a
2,2
− a
2,1
a
1,2
a
1,1
a
1,2
a
1,3
a
2,1
a
2,2
a
2,3
a
3,1
a
3,2
a
3,3
=
a
1,1
a
2,2
a
3,3
+ a
1,2
a
2,3
a
3,1
+
a
1,3
a
2,1
a
3,2
− a
3,1
a
2,2
a
1,3
−
a
3,2
a
2,3
a
1,1
− a
3,3
a
2,1
a
1,2
And, by definition, for the 1 ×1 case:
a
1,1
= a
1,1
In fact, these are so frequently encountered that it’s quite useful to have the
formulas memorized. For the 1 × 1 and 2 ×2 cases, this isn’t too tough, but for the
3 ×3 case, there’s a convenient trick: write out the matrix, then write out another
copy of the first two columns just to the right of the matrix. Next, multiply together
the elements along each diagonal, and add the results of the upper-left to lower-right
diagonals, and subtract the results of the lower-left to upper-right diagonals:
36 Chapter 2 Matrices and Linear Systems
a
1,3
a
1,1
a
1,2
a
1,2
a
1,1
a
2,3
a
2,1
a
2,2
a
2,2
a
2,1
a
3,3
a
3,1
a
3,2
a
3,2
a
3,1
Note that this also works for the 2 ×2 case as well, but not for anything larger than
3 × 3.
General Determinant Solution
A more general appproach to computing det(M) is known as determinant expansion
by minors or Laplacian expansion. To understand this, we need to define the terms
submatrix, minor, and cofactor.
A submatrix is simply a matrix formed by deleting one or more rows and/or
columns from a matrix. For example, if we have a matrix
M =
3925
2713
8461
9526
we can form a submatrix by deleting the third column and fourth row of M:
M
4,3
=
395
273
841
A minor is a determinant of a submatrix; specifically, for an element a
i,j
of M, its
minor is the determinant of the matrix M
ij
, which is formed by deleting the ith row
and jth column of M.
A cofactor c
i,j
of an element a
i,j
of M is the minor for that element, or its
negation,asdefinedby
c
i,j
=
(
−1
)
i+j
M
i,j
(Note that these cofactors are frequently taken together as a matrix of cofactors, often
denoted C.) An example can make this clear. If we have a 3 × 3 matrix, we can use
2.5 Square Matrices 37
this cofactor-based method to compute the determinant as follows:
a
1,1
a
1,2
a
1,3
a
2,1
a
2,2
a
2,3
a
3,1
a
3,2
a
3,3
= a
1,1
a
2,2
a
2,3
a
3,2
a
3,3
− a
1,2
a
2,1
a
2,3
a
3,1
a
3,3
+ a
1,3
a
2,1
a
2,2
a
3,1
a
3,2
In general, a determinant of an n × n matrix gets “reduced” to a sum of scaled
(n −1) ×(n −1) determinants, which we can solve individually by applying the same
approach, and so on until we have a single scalar (of course, in the above example, we
get 2 ×2 minors, which we could solve using the direct method described earlier).
Properties of the Determinant
Like the other operations on matrices, the determinant possesses a number of inter-
esting and useful properties:
i. The determinant of a matrix is equal to the determinant of its transpose:
|
M
|
=
M
T
.
ii. The determinant of the product of two matrices is equal to the product of the
determinants:
MM
1
=
|
M
|
M
1
.
iii. The determinant of the inverse of a matrix is equivalent to the multiplicative
inverse of the determinant of the matrix:
M
−1
= 1/
|
M
|
.
iv. The determinant of the identity matrix is 1:
|
I
|
= 1.
v. The determinant of a scalar multiple of a matrix is the product of the scalar, raised
to the size of the matrix, times the determinant of the matrix:
|
αM
|
=α
n
|
M
|
.The
n shows up because M is an n × n matrix.
vi. Interchanging any two rows (or columns) of M changes the sign of
|
M
|
.
vii. If all the elements of one row (or column) of M are multiplied by a constant α,
then the determinant is α
|
M
|
.
viii. If two rows (or columns) of M are identical, then
|
M
|
= 0.
ix. The determinant of a triangular matrix is equal to the product of the diagonal
elements:
a
1,1
a
1,2
··· a
1,n
0 a
2,2
··· a
2,n
.
.
.
.
.
.
.
.
.
.
.
.
00··· a
n,n
=
a
1,1
0 ··· 0
a
2,1
a
2,2
··· 0
.
.
.
.
.
.
.
.
.
.
.
.
a
n,1
a
n,2
··· a
n,n
= a
1,1
a
2,2
···a
n,n
38 Chapter 2 Matrices and Linear Systems
2.5.4 Inverse
We’ve seen that many of the properties of scalar multiplication apply to matrices. One
useful property is the multiplicative inverse: for any real α = 0, there is a number β
such that αβ =1, and of course β =1/α. It would be quite useful to have this property
apply to matrices as well, as we just saw in the previous section. Recalling that the
identity element for matrices is I, the identity matrix, for a given matrix M
1
we would
like to find a matrix M
2
, if possible, such that M
1
M
2
= I. If there is such a matrix, it
is called the inverse of M
1
and is denoted M
2
= M
−1
1
.
Now the question is, how can you compute M
−1
1
, and when is it possible to do so?
Recall that multiplying a matrix M
1
by M
2
is accomplished by computing each ele-
ment i, j of the result by multiplying the ith row of M
1
by the jth column of M
2
.Ifwe
employ the notational scheme of writing each n × 1 column of M
2
as v
1
, v
2
, ···, v
n
,
the product M
1
M
2
can be computed column-by-column by multiplying each row of
M
1
by column v
i
of M
2
: M
1
v
i
. If we then consider each column of the identity matrix
I to consist of the n ×1vectore
i
, which consists of all zero elements save the i, which
is 1, we can rewrite the product M
1
M
2
= I as
M
1
[
v
1
v
2
··· v
n
]
=
[
e
1
e
2
··· e
n
]
This can be interpreted as a series of n linear systems:
M
1
v
1
= e
1
M
1
v
2
= e
2
.
.
.
M
1
v
n
= e
n
If we then solve each of these n linear systems, we’ll be solving for each column of M
2
,
and since the product is I, we’ll have computed M
−1
1
. Because these are just linear
systems, we can solve them using any of the general techniques, such as Gaussian
elimination (see Section A.1) or LU decomposition (Press et al. 1988).
Another approach to computing the inverse of a matrix can be found by looking
at a formal definition of the inverse of a matrix: if we have a square matrix M,ifithas
an inverse M
−1
, then element a
−1
i,j
of M
−1
is defined as
a
−1
i,j
=
(
−1
)
i+j
M
j,i
|
M
|
2.5 Square Matrices 39
Recall that the expression in the numerator is just a cofactor, and so we can then write
M
−1
=
C
T
|
M
|
Note that the transposition is the result of the subscript ordering j , i in the previous
equation; the matrix C
T
is also known as the adjoint of M.
To see how this works, we’ll show a simple example with a 2 × 2 matrix. Let
M =
12
34
with determinant |M|=1 × 4 − 3 ×2 =−2. We then compute the cofactors
c
11
= (−1)
1+1
|M
11
|=|4|=4
c
12
= (−1)
1+2
|M
12
|=−|3|=−3
c
21
= (−1)
2+1
|M
21
|=−|2|=−2
c
22
= (−1)
2+2
|M
22
|=|1|=1
giving us
C =
4 −3
−21
The inverse then is
M
−1
=
C
T
|
M
|
=
4 −2
−31
−2
=
−21
3/2 −1/2
Verifying, we see
12
34
−21
3/2 −1/2
=
10
01
= I
40 Chapter 2 Matrices and Linear Systems
Properties of the Inverse
There are a number of useful properties of the matrix inverse (assuming the inverses
exist):
i. If MM
−1
= I, then M
−1
M = I
ii.
M
1
M
2
−1
= M
−1
2
M
−1
1
iii.
M
−1
−1
= M
iv.
(
αM
)
−1
=
(
1/α
)
M
−1
(with α = 0)
When Does the Inverse Exist?
The previous sections have hinted that the inverse does not always exist for a square
matrix, and this is indeed the case. So, the question is how to determine whether an
inverse exists for a given n × n matrix M. There are several (equivalent) ways to put
this:
i. It is of rank n.
ii. It is nonsingular.
iii.
|
M
|
= 0.
iv. Its rows (columns) are linearly independent.
v. Considered as a transformation, it does not reduce dimensionality.
Singular Matrices
A matrix M is defined to be nonsingular if it is square (n × n) and its determinant
is nonzero (|M| = 0). Any matrix failing to meet either of these conditions is called
singular. Nonsingularity is an important property of a matrix, as can be seen by this
list of equivalent if-and-only-if criteria for an n × n matrix M being nonsingular:
i. |M| = 0.
ii. The rank of M is n.
iii. The matrix M
−1
exists.
iv. The homogeneous system MX = 0 has only the trivial solution X =0.
This last definition is particularly significant—because that property and the first
are if-and-only-if conditions, it follows that a homogeneous system MX = 0 has a
nontrivial solution (X = 0) if and only if |M|=0.
2.6 Linear Spaces 41
2.6 Linear Spaces
In this section, we’ll introduce the concept of a linear (or vector) space and discuss the
representation of vector spaces, and operations on linear spaces, in terms of matrices
and matrix operations. Unlike some treatments of this subject, we’re going to forgo
references to any sort of geometrical interpretation of such spaces for the time being; a
subsequent chapter will address these issues explicitly, after we’ve covered geometrical
vectors themselves in an abstract fashion.
2.6.1 Fields
Before formally defining a linear space, we need to define the term field.Afieldis“an
algebraic system of elements in which the operations of addition, subtraction, multi-
plication, and division (except by zero) may be performed without leaving the system,
and the associative, commutative, and distributive rules hold” (www.wikipedia.com/
wiki/Field). Formally, a field F consists of a set and two binary operators “+” and “∗”
(addition and multiplication) with the following properties:
i. Closure of F under addition and multiplication: ∀a, b ∈F , both (a +b) ∈F and
(a ∗b) ∈ F .
ii. Associativity of addition and multiplication: ∀a, b, c ∈ F , both a + (b + c) =
(a +b) + c and a ∗ (b ∗ c) = (a ∗b) ∗ c.
iii. Commutativity of addition and multiplication: ∀a, b ∈F , a + b = b + a and a ∗
b = b ∗ a.
iv. Distributivity of multiplication over addition: ∀a, b, c ∈ F , both a ∗ (b + c) =
(a ∗b) + (a ∗c) and (b + c) ∗ a =(b ∗ a) + (c ∗ a).
v. Existence of additive identity element: ∃0 ∈ F such that ∀a ∈F , a + 0 = a and
0 +a = a.
vi. Existence of multiplicative identity element: ∃1 ∈ F such that ∀a ∈ F , a ∗ 1 =
a and 1 ∗ a =1.
vii. Additive inverse: ∀a ∈ F , ∃−a ∈ F such that a + (−a) = 0 and (−a) + a =0.
viii. Multiplicative inverse: ∀a = 0 ∈ F , ∃a
−1
∈ F such that a ∗ a
−1
= 1 and a
−1
∗
a = 1.
A field is also known as a commutative ring or commutative division algebra.
Examples of fields are
the rational numbers Q ={
a
b
|a, b ∈ Z, b = 0},whereZ denotes the integers
the real numbers R
the complex numbers C
42 Chapter 2 Matrices and Linear Systems
Note that the integers do not form a field, but only a ring (there is no multiplicative
inverse for integers).
2.6.2 Definition and Properties
Informally, a linear space consists of a collection of objects (called vectors), real
numbers (scalars), and two operations (adding vectors and multiplying vectors by
scalars), which are required to have certain properties. Rather than sticking to the
lowercase boldface generic tuple notation, we’re going to use a notation that makes
explicit the fact that we’re dealing with vectors—vectors will be notated as lowercase
italic letters with a diacritical arrow. Typically, we use u, v, and w,orv
1
, v
2
, ..., v
n
for lists of vectors. Formally, suppose we have the following:
AfieldK (which, for us, will be R).
A (nonempty) set of vectors V .
An addition operator “+” defined on elements u, v ∈V .
A multiplication operator “∗” defined on scalars k ∈K and v ∈ V (often, the “∗”
is omitted and concatenation used, as in v =k u).
The addition and multiplication operations exhibit the rules listed below.
Properties:
i. Closure under multiplication: ∀k ∈ K and ∀v ∈V , kv ∈ V .
ii. Closure under addition: ∀u, v ∈V , u +v ∈ V .
iii. Associativity of addition: ∀u, v, w ∈ V , u + (v +w) = (u +v) +w.
iv. Existence of additive identity element: ∀v ∈ V , ∃ avector
0 ∈ V called the zero
vector, such that v +
0 =v.
v. Existence of additive inverse: ∀v ∈ V , ∃ avector −v, such that v +(−v) =
0.
vi. Commutativity of addition: ∀u, v ∈V , u +v =v +u.
vii. Distributivity of multiplication over addition: ∀k ∈K and ∀u, v ∈V , k(u +v) =
k u + k v.
viii. Distributivity of addition over multiplication: ∀k
1
, k
2
∈ K and ∀v ∈ V , (k
1
+
k
2
)v = k
1
v + k
2
v.
ix. Associativity of multiplication: ∀k
1
, k
2
∈ K, and ∀v ∈ V , (k
1
k
2
)v = k
1
(k
2
v).
x. Existence of multiplicative identity: ∀v ∈ V ,1∗v =v.
As we stated earlier, our concern here is with computer graphics, and as a result
the field K is just the real numbers R, and the vectors in V are tuples of real numbers:
a =(a
1
, a
2
, ..., a
n
). In later chapters, once we’ve established the relationship between
2.6 Linear Spaces 43
geometrical vectors, vector spaces, and matrices, we’ll switch from this rather abstract
tuple-oriented notation for vectors to one that reflects the geometrical interpretation
of tuples in R
n
(the set of all such n-tuples).
2.6.3 Subspaces
Given a linear space V over R,letS be a subset of V , and let the operations of S and
V be the same. If S is also a linear space over R, then S is a subspace of V .
While the above seems rather obvious, its subtlety is revealed by pointing out
that a subset of a linear space may or may not itself be a linear space. An example
from Agnew and Knapp (1978) shows this rather nicely: Consider a subset S
1
of R
3
consisting of all 3-tuples of the form (a
1
, a
2
,0). A quick check of this against all the
rules defining a linear space shows that this is, indeed, a linear space. However, if we
have a subspace S
2
consisting of 3-tuples of the form (a
1
, a
2
,1), and check if all the
rules for a linear space apply to it, we see that it fails on several of them:
i. Closure under addition: (a
1
, a
2
,1) + (b
1
, b
2
,1) = (a
1
+ b
1
, a
2
+ b
2
,2), which is
not in S
2
.
ii. Closure under multiplication: (a
1
, a
2
,1) ∈ S
2
, but k(a
1
, a
2
,1) = (ka
1
, ka
2
, k) ∈
S
2
for k = 1.
iii. Existence of identity element: (0, 0, 0) ∈ S
2
.
iv. Existence of additive inverse: (a
1
, a
2
,1) ∈ S
2
, but (−a
1
, −a
2
, −1) ∈ S
2
.
v. Closure under multiplication: (a
1
, a
2
,1) ∈ S
2
, but k(a
1
, a
2
,1) = (ka
1
, ka
2
, k) ∈
S
2
for k = 1.
It is interesting to note that this example is not simply arbitrary, and its significance
will become apparent later.
2.6.4 Linear Combinations and Span
A linear combination of a set of items is constructed by forming a sum of scalar
multiples of the items. Suppose we have a vector set A whose elements are a set
of vectors (tuples) in R
n
: {a
1
, a
2
, ..., a
n
}. You can form a vector u = k
1
a
1
+ k
2
a
2
+
···+k
n
a
n
. This vector u is of course itself a vector because each k
i
a
i
isavectorand
the sum of each of these vectors is itself a vector.
Given a set of vectors (tuples) {v
1
, v
2
, ..., v
n
} defining a linear space V , the set
S of all linear combinations of the vectors is itself a linear space, and this space is the
space spanned by {v
1
, v
2
, ..., v
n
}. The set {v
1
, v
2
, ..., v
n
} is called the spanning set
for S. The significance of this idea of a spanning set is that any vector w ∈S can be
written in terms of {v
1
, v
2
, ..., v
n
}, by simply finding the scalars k
1
, k
2
, ..., k
n
for
which w = k
1
v
1
+ k
2
v
2
+···+k
n
v
n
.