i
i
i
i
i
i
i
i
Appendix A
Some Linear Algebra
BOOK I. DEFINITIONS.
A point is that which has no part.
A line is a breadthless length.
The extremities of a line are points.
A straight line is a line which lies evenly with the points on
itself.
—The first four definitions from Elements by Euclid [320]
This appendix deals with the fundamental concepts of linear algebra that
are of greatest use for computer graphics. Our presentation will not be as
mathematically abstract and general as these kinds of descriptions often
are, but will rather concentrate on what is most relevant. For the inexpe-
rienced reader, it can be seen as a short introduction to the topic, and for
the more experienced one, it may serve as a review.
We will start with an introduction to the Euclidean spaces. This may
feel abstract at first, but in the section that follows, these concepts are
connected to geometry, bases, and matrices. So bite the bullet during the
first section, and reap the rewards in the rest of the appendix and in many
of the other chapters of this book.
If you are uncertain about the notation used in this book, take a look
at Section 1.2.
A.1 Euclidean Space
The n-dimensional real Euclidean space is denoted R
n
. A vector v in this
space is an n-tuple, that is, an ordered list of real numbers:
1
1
Note that the subscripts start at 0 and end at n − 1, a numbering system that
follows the indexing of arrays in many programming languages, such as C and C++.
This makes it easier to convert from formula to code. Some computer graphics books
and linear algebra books start at 1 and end at n.
889
i
i
i
i
i
i
i
i
890 A. Some Linear Algebra
v ∈ R
n
⇐⇒ v =
⎛
⎜
⎜
⎜
⎝
v
0
v
1
.
.
.
v
n−1
⎞
⎟
⎟
⎟
⎠
with v
i
∈ R,i=0,...,n− 1. (A.1)
The vector can also be presented as a row vector, but most computer
graphics book use column vectors, in what is called the column-major form.
We call v
0
,...,v
n−1
the elements, the coefficients, or the components of
the vector v. All bold lowercase letters are vectors that belong to R
n
,and
italicized lowercase letters are scalars that belong to R.Asanexample,a
two-dimensional vector is v =(v
0
,v
1
)
T
∈ R
2
. For vectors in a Euclidean
space there exist two operators, addition and multiplication by a scalar,
which work as might be expected:
u + v =
⎛
⎜
⎜
⎜
⎝
u
0
u
1
.
.
.
u
n−1
⎞
⎟
⎟
⎟
⎠
+
⎛
⎜
⎜
⎜
⎝
v
0
v
1
.
.
.
v
n−1
⎞
⎟
⎟
⎟
⎠
=
⎛
⎜
⎜
⎜
⎝
u
0
+ v
0
u
1
+ v
1
.
.
.
u
n−1
+ v
n−1
⎞
⎟
⎟
⎟
⎠
∈ R
n
(addition)
(A.2)
and
au =
⎛
⎜
⎜
⎜
⎝
au
0
au
1
.
.
.
au
n−1
⎞
⎟
⎟
⎟
⎠
∈ R
n
(multiplication by a scalar). (A.3)
The “∈ R
n
” simply means that addition and multiplication by a scalar
yields vectors of the same space. As can be seen, addition is done com-
ponentwise, and multiplication is done by multiplying all elements in the
vector with the scalar a.
A series of rules hold for Euclidean space.
2
Addition of vectors in a
Euclidean space also works as might be expected:
(i)(u + v)+w = u +(v + w) (associativity)
(ii) u + v = v + u (commutativity).
(A.4)
There is a unique vector, called the zero vector, which is 0 =(0, 0,...,0)
with n zeros, such that
(iii) 0 + v = v(zeroidentity).
(A.5)
2
Actually, these are the definition of Euclidean space.
i
i
i
i
i
i
i
i
A.1. Euclidean Space 891
There is also a unique vector −v =(−v
0
, −v
1
,...,−v
n−1
) such that
(iv) v +(−v)=0 (additive inverse).
(A.6)
Rules for multiplication by a scalar work as follows:
(i)(ab)u = a(bu)
(ii)(a + b)u = au + bu (distributive law)
(iii) a(u + v)=au + av (distributive law)
(iv)1u = u.
(A.7)
For a Euclidean space we may also compute the dot product
3
of two
vectors u and v. The dot product is denoted u · v, and its definition is
shown below:
u · v =
n−1
i=0
u
i
v
i
(dot product). (A.8)
For the dot product we have the rules:
(i) u · u ≥ 0, with u · u =0ifandonlyifu =(0, 0,...,0) = 0
(ii)(u + v) · w = u · w + v ·w
(iii)(au) · v = a(u · v)
(iv) u · v = v · u (commutativity)
(v) u · v =0⇐⇒ u ⊥ v.
(A.9)
The last formula means that if the dot product is zero then the vectors
are orthogonal (perpendicular). The norm of a vector, denoted ||u||,isa
nonnegative number that can be expressed using the dot product:
||u|| =
√
u · u =
(
n−1
i=0
u
2
i
(norm).
(A.10)
3
Also called inner (dot) product or scalar product.
i
i
i
i
i
i
i
i
892 A. Some Linear Algebra
The following rules hold for the norm:
(i) ||u|| =0⇐⇒ u =(0, 0,...,0) = 0
(ii) ||au|| = |a|||u||
(iii) ||u + v|| ≤ ||u|| + ||v|| (triangle inequality)
(iv) |u · v|≤||u||||v|| (Cauchy–Schwartz inequality).
(A.11)
The next section shows how we can use the theory in this section by
interpreting everything geometrically.
A.2 Geometrical Interpretation
Here, we will interpret the vectors (from the previous section) geometrically.
For this, we first need to introduce the concepts of linear independence and
the basis.
4
If the only scalars to satisfy Equation A.12 below are v
0
= v
1
= ...=
v
n−1
=0, then the vectors, u
0
,...u
n−1
, are said to be linearly independent.
Otherwise, the vectors are linearly dependent:
v
0
u
0
+ ···+ v
n−1
u
n−1
= 0 (A.12)
For example, the vectors u
0
=(4, 3) and u
1
=(8, 6) are not linearly in-
dependent, since v
0
=2andv
1
= −1 (among others) satisfy Equation A.12.
Only vectors that are parallel are linearly dependent.
If a set of n vectors, u
0
,...,u
n−1
∈ R
n
, is linearly independent and any
vector v ∈ R
n
can be written as
v =
n−1
i=0
v
i
u
i
, (A.13)
then the vectors u
0
,...,u
n−1
are said to span Euclidean space R
n
.If,
in addition, v
0
,...,v
n−1
are uniquely determined by v for all v ∈ R
n
,
then u
0
,...,u
n−1
is called a basis of R
n
. What this means is that every
vector can be described uniquely by n scalars (v
0
,v
1
,...,v
n−1
)andthe
basis vectors u
0
,...,u
n−1
. The dimension of the space is n,ifn is the
largest number of linearly independent vectors in the space.
4
Note that the concepts of linear independence and the basis can be used without
any geometry.
i
i
i
i
i
i
i
i
A.2. Geometrical Interpretation 893
Figure A.1. A three-dimensional vector v =(v
0
,v
1
,v
2
) expressed in the basis formed by
u
0
, u
1
, u
2
in R
3
. Note that this is a right-handed system.
An example of a linearly independent basis is u
0
=(4, 3) and u
1
=
(2, 6). This spans R
2
, as any vector can be expressed as a unique combina-
tion of these two vectors. For example, (−5, −6) is described by v
0
= −1
and v
1
= −0.5 and no other combinations of v
0
and v
1
.
To completely describe a vector, v, one should use Equation A.13, that
is, using both the vector components, v
i
and the basis vectors, u
i
.That
often becomes impractical, and therefore the basis vectors are often omitted
in mathematical manipulation when the same basis is used for all vectors.
If that is the case, then v can be described as
v =
⎛
⎜
⎜
⎜
⎝
v
0
v
1
.
.
.
v
n−1
⎞
⎟
⎟
⎟
⎠
, (A.14)
which is exactly the same vector description as in Expression A.1, and so
this is the one-to-one mapping of the vectors in Section A.1 onto geomet-
rical vectors.
5
An illustration of a three-dimensional vector is shown in
Figure A.1. A vector v can either be interpreted as a point in space or as a
directed line segment (i.e., a direction vector). All rules from Section A.1
apply in the geometrical sense, too. For example, the addition and the
scaling operators from Equation A.2 are visualized in Figure A.2. A basis
can also have different “handedness.” A three-dimensional, right-handed
basis is one in which the x-axisisalongthethumb,they-axis is along
index-finger, and the z-axis is along the middle finger. If this is done with
the left hand, a left-handed basis is obtained. See page 901 for a more
formal definition of “handedness.”
The norm of a vector (see Equation A.10) can be thought of as the
length of the vector. For example, the length of a two-dimensional vector,
5
In mathematics, this is called an isomorphism.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.