Linear Algebra for Computer Graphics 101

What is a vector?

A vector is an element of a vector space. Not very helpful is it? This leads to the next question which is…

What is a vector space?

A vector space is nothing more than a set of elements (let’s call the set V) along with two operations, the addition operation and the multiplication by scalar operation, such that the following properties hold:

  • Commutativity

u + v = v + u      ,for all v,u V

  • Associativity

( u + v ) + w = u + ( v + w )        for all v,u,w V

  • Additive identity

There exists an element 0 V such that v + 0 = v for all v V

  • Additive inverse

For every v V, there exists a w V such that v + w = 0

  • Multiplicative identity

1 * v = v             for all v V

  • Distributive properties

a * ( u + v ) = a * u + a * v           for all u,v V and a   ℝ

The elements of the set V are called vectors. Note that this is a more abstract way of thinking about vectors than we, graphics programmers, usually do…

With this definition of vector space, we can now prove that ℝ³ is a vector space. It is indeed a set of elements, each element of the form v ={x,y,z}, it has an addition operation defined as v + u = { v.x + u.x, v.y + u.y, v.z + u.z } and a multiplication by an scalar defined as k * v = { k * v.x, k * v.y, k + v.z }. It’s easy to proof that it holds all the properties required to be considered a vector space.

With this definition we could also prove that quadratic polynomials ( polynomials of the form a2*x^2 + a1*x + a0 ), for example, form, also, a vector space. You can try to prove that for yourself.

What is a linear combination of vectors?

By definition, a linear combination of a list of vectors (v1, v2, …, vn ) is a vector of the form:
v = a1*v1 + a2*v2 + … + an*vn,  where a1,a2…,an are scalars.

The set formed by all linear combinations of a list of vectors (v1, v2, … vn ) is called the span of that list.

A list of vectors is linearly independent if the only choice of a1,a2,…,an that makes a1*v1 + a2*v2 + … + an*vn equal the zero vector is if a1 = a2 = … = an = 0. Let’s see an example:

Is the list formed by v1 = {1,2} and v2 = {0,1} linearly independent?

{0,0} = a1*v1 + a2 * v2;

0 = a1 * 1 + a2 * 0;  -> a1 = 0
0 = a1 * 2 + a2 * 1;  -> a2 = 0

We have proved that the list (v1, v2) is linear independent.

Is the list formed by v1 = {1,2} and v2 = {2,4} linear independent

{0,0} = a1*v1 + a2 * v2;

0 = a1 * 1 + a2 * 2; // a1 = -2a2
0 = a1 * 2 + a2 * 4; // 0 = 0

This equation system has not a unique solution, so, we have proved that v1 and v2 are not linear independent.

A list of vectors is linear independent if and only if each vector in the span of the list  has only one representation as a linear combination of the list. That is useful because using a linear independent list, we can refer to any vector of its span using only its a1, a2, …, an coefficients. That’s what we called the coordinates of the vector. So, back to R^3, when we talk about the vector v=[1,2,3], what we are really saying is that vector v is a linear combination of the linear independent list v0=[1,0,0], v1=[0,1,0] and v2=[0,0,1]. v can be written as :

v = 1 * v0 + 2 * v1 + 3 * v2 -> v = 1 * [1,0,0] + 2 * [0,1,0] + 3 * [0,0,1] = [1,2,3]

Note that v0, v1 and v2 are linearly independent so there is no other way to combine those three vectors to produce the vector v= [1,2,3]. Actually, the list formed by v0,v1 and v2 spans the whole R3 vector space, so, any vector on R3 can be expressed as a linear combination of them. They form what is known as a basis of a vector space, in this case the vector space is R3.

What is a linear map?

A linear map is a function from an origin vector space V to a target vector space W.

T: V -> W

with the following properties:

  • Additivity

T(U+V) = T(U) + T(V)

  • Homogeneity

T(k*V) = k * T(V)

So, a linear map takes vectors from one vector space V and maps them to a target vector space W. Let’s see some examples:

T(x,y,z) = ( x, y )

T(x,y,z) is a map from ℝ³ to ℝ². You can easily verify that it follows the properties needed to be considered a linear map.

It is not necessary for the origin and target vector space to be different though, as you can see in the next example

T(x,y,z) = ( 2x, 2y, 2z )

This linear map takes vectors in ℝ³ and maps them to vectors in ℝ³. It is also a linear map, and a very common one indeed as it is a scale by 2 operation.

Now, pay attention to this trick. Suppose (v1,…,vn) is a basis of V. If v € V, then we can write v as:

v = a1*v1 + … + an*vn

If we apply a linear map T:V->W to the vector v, the linearity of T implies that

T(v) = a1 * T(v1) + … + an * T(vn)

If we precompute the vectors ( T(v1), … , T(vn) ) we can apply the linear map to any vector of V just using multiplications and additions.

Imagine we have this linear map on ℝ³:

T(x,y,z) = ( sin(x)*cos(y), cos(x)*sin(y), sin(z) )

Computing all those trigonometric functions for every vector in V we want to transform can be expensive. If we just compute that for the basis vectors of V, we can calculate the linear map for any vector in V ( assuming we know its coordinates in that basis ) using only multiplication and addition.

What is the matrix of a linear map?

With that trick in mind, we can finally understand what is the matrix of a linear map. The matrix of a linear map is nothing else than a way to arrange the transformed basis vectors so we can apply the linear map as a simple matrix-vector multiplication.

In the case of the previous linear map, we can form the matrix:

T(1,0,0) = (sin(1)*cos(0), cos(1)*sin(0), sin(0) ) = (0.017452406, 0.0, 0.0)

T(0,1,0) = (sin(0)*cos(1), cos(0)*sin(1), sin(0) ) = (0.0,0.017452406, 0.0)

T(0,0,1) = (sin(0)*cos(0), cos(0)*sin(0), sin(1) ) = (0.0, 0.0, 0.017452406 )

       |  0.017452406      0.0          0.0        |
T(v) = |     0.0       0.017452406      0.0        |
       |     0.0          0.0        0.017452406   |

Now, we can apply the linear map to any vector doing a simple matrix-vector multiplication avoiding the computation of  the trigonometric functions in the definition of the map.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s