Real-Time Rendering, Third Edition, 3rd Edition

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.