Handmade Hero»Forums»Code
Den V
19 posts
None
Linear Independence
Edited by Den V on
I am catching up on latest episodes of Handmade Hero and just finished watching Day 90.

Not sure why Casey back-paddled on linear independence, as it is directly related to basis. So I decided to write a brief explanation.

Vectors {v[sub]1[/sub], v[sub]2[/sub], ..., v[sub]n[/sub]} are said to be linearly dependent if one vector in the set, can be represented by linear combination of some other vectors in the set (example at the bottom of the post). If that is not the case -- no vector in the set can be represented as a linear combination of some other vectors in the set, the vectors are said to be linearly independent.

A set of linearly independent vectors forms a basis for a vector space. A basis is a set of vectors that generates a vector space (also said "spans a vector space"). Vector space is just a set of vectors generated by a basis.

So far the stuff is theoretical, lets finally see what it means for us. Consider 2D plane or coordinate system with x and y axes. This space is also called R[sup]2[/sup], where R means "real number" and 2 is for 2-dimensional. Two dimensional space, where every point in the space is represented by a pair of real numbers. Sounds familiar, right? That is what Casey is using for world coordinate system and camera coordinate system.

Now consider any point in the Handmade Hero world space (R[sup]2[/sup] space). Lets consider point (5,3). We know that we can arrive at that point by going 5 units over on x positive, and 3 unit up on y. Again, Casey already explained it on the stream. Now realize that for any point we choose, we can use the same "algorithm" to "get to it" -- make your way on x, then on y.

Since any point can be thought of as a vector starting at the origin (0,0), then we realize that our Handmade Hero world coordinate system is a vector space. Our basis (set of vectors that generate any vector in the vector space) is a set of vectors {(1,0), (0,1)}, where we can see the (1,0) is pointing the same direction as x axis and (0,1) pointing in the direction of y axis. You can relate this to where Casey explains how he needs only two axis to generate a point (or a vector) in the world (vector space). He also points out that if he had a third vector, if would be redundant.

Now, lets see why having third vector would be redundant mathematically. Consider basis B = {(1,0), (0,1), (2,3)}. Assume B generates (spans) our vector space for Handmade Hero world. If B is a basis, then every vector in the basis MUST be linearly independent. In other words, no vector can be represents as a linear combination of some other vectors. But we see that (2,3) can be represented as a linear combination 2(1,0) + 3(0,1). Our assumption was wrong. We conclude that B is not a basis. Same as Casey visually showed redundancy on the black board.

Only a set of linearly independent vectors can be a basis.

In fact, {(1,0), (0,1)} is called natural basis. It is a set of unit vectors pointing in the direction of the axes in the Cartesian coordinate system.

I hope that helps to understand how linear (in)dependence is directly related to basis and vector space generation.




--------- Definitions for other terms used in the post ------------
Set - collection of unique elements.
Examples:
1. (1, 3, 4, 3, 3) - not a set, "3" is a repeating element.
2. (1, 2, 3) - is a set, no repeating elements.

Linear Combination - multiplying a term by a constant and/or adding it to another term also multiplied by a constant. Consider v1 and v2 terms (vectors, in our case), and c1 and c2 scalars (any scalar number that is in the same space -- we are working in the space of real numbers). Then expression of type c1*v1 + c1*v2 is said to be linear combination of vectors v1 and v1.
Examples:
1. 2(4,1) + 5(3,9) is a linear combination
2. (3,4) can be written as a linear combination 1(3,4)
3. 4(1,2) is a linear combination
4. (1,2) + (3,4) can be written as a linear combination 1(1,2) + 1(3,4)




-------------- Other examples ----------------
Basis
Any vector space has a basis that generates it. A single vector can be a basis. For example, consider vector (3,4). Even though in the example of Linear combination I said you can thing of 1(3,4) as a linear combination, it does not change the components of vector (3,4), 1(3,4) = (3,4). So vector (3,4) cannot be represented as a linear combination of some other vectors in the set (we only have one vector). The set B={(3,4)} is a basis. We know that basic vector(s) generate (span) a vector space. So lets see what vector space we can generate with basis B. Well, to generate a vector space, we need to construct linear combinations of basis vector(s). Since we only have one vector, our linear combinations will look like C(3,4), where C is a real number scalar. We can plug in any real number in place of C to generate another vector in the space. Lets choose 4, that give us 4(3,4) = (12,16). Now we have a vector space with two vectors -- {(3,4), (12,16)}. Lets choose another one, say C = 3. Now we have 3(3,4) = (9,12). Our vector space grew to three vectors -- {(3,4), (12,16), (9,12)}. We can also go in negative direction. Since we have infinitely many real numbers, we can see that we can generate infinitely many vectors in the vector space generated by basis B. If you plot those vectors on 2D coordinate system, you will see that it looks like a straight line. And that is what we expected. Because if you think about it, we had a single vector that we kept scaling either up or down and reversing direction (in case C is negative). So piling all those vectors on top of each other just gives us a straight line that visualizes our vector space.

Linear Dependency
Consider set of vectors {(1,2), (3,6)}. The set is linearly dependent, because (3,6) can be expressed as linear combination 3(1,2). So we can a vector in the set that is expressed as a linear combination of some other vector(s) in the set.
Den V
19 posts
None
Linear Independence
When I said Handmade Hero world is in R[sup]2[/sup] space, I completely forgot about the Z