Matrices for programmers

Following the fine tradition of the colour theory post, you are getting another crash course. This time, a lesson in matrices. You’re going to be fine. And yes, I’ll hold your hand while you do this. *smile*

For those who are mathematically inclined, we’ll be working in the realm of real numbers (which I talked about briefly when discussing floating points). Let’s start with…

Scalars

Scalars are simply numbers. For example, 2 is a scalar. So is 3.14159 and 1.618. And so is -273.15. Bonus points if you can figure out what those numbers are special for.

Scalars are stored as normal variables in code. Your ints, floats, doubles come in handy.

Scalars are typically denoted by a lowercase alphabet, such as a or b or c.

Vectors

Vectors are series of scalars. For example, [1 3 5 7 9] is a vector.

You typically store vectors as an array. For example,

int[] v = new int[] { 1, 3, 5, 7, 9 };

Vectors are typically denoted by a lowercase alphabet in bold, such as v.

Matrices

Matrices are series of series of scalars, or series of vectors. In code, they are typically stored as an array of arrays.

int[,] A = new int[3, 3];

Matrices are also known as multidimensional arrays. The dimension of a matrix is m-by-n, where m is the number of rows and n is the number of columns.

When either m or n is 1, we get a vector. So a vector is a special case of a matrix. And because of this, we have to define…

Row and column vectors

It’s easier to just show you how they look like.

A row vector is a matrix where the number of rows is 1. A column vector is a matrix where the number of columns is 1. While we’re at it, a scalar can be thought of as a matrix where the number of rows and columns are both 1.

For our purposes of working towards 3D programming, we’ll be focusing on the column vector. It doesn’t matter which one we use when coding, but in terms of notation, we’ll be using column vectors. You will see why later on.

Matrix entries

Individual entries are referred to with the notation A[i,j] (or a_i,j) where A is the matrix, i is the i-th row and j is the j-th column. Typically, we have
1 <= i <= m and 1 <= j <= n, where m is the number of rows and n is the number of columns.

Take note, because you'll be using them in code. So know how your programming language does indices of arrays. If your language starts with the 0-th element, make sure to shift positions by one less. Then you have
0 <= i <= m-1 and 0 <= j <= n-1.

The 0 index has tripped many a programmer, so be careful.

Square matrices

This is a special case where both the number of rows and number of columns are equal. For example, a 3 by 3 matrix, or a 4 by 4 matrix.

In a stroke of coincidence, we will also be focusing on 3 by 3 and 4 by 4 matrices. Hint: It’s because we’re working in 3D.

Identity matrix

In math, there is a number such that when you multiply anything by it, you get back the same thing. It’s the number 1. For example, 8 * 1 = 1 * 8 = 8.

We have the same concept for matrices. There is a matrix such that when you multiply any matrix by it, you get the same original matrix back. It’s called the identity matrix, typically denoted by an uppercase “I”.

We’ll look at matrix operations soon.

Zero matrix

You know that multiplication unity described above when defining the identity matrix? Guess what, there’s a number such that when you add anything to it, you get back the same thing. It’s the number 0. For example, 8 + 0 = 0 + 8 = 8.

Similarly, we have the zero matrix. It’s simply a matrix with zeroes in all its entries. It’s denoted by a big gigantic 0. Probably not quite useful to you, but nevertheless, you now know something more.

Symmetrical matrices

Symmetrical matrices are symmetrical about the diagonal. Where’s the diagonal? Look at this:

For a 3 by 3 matrix with values:
a b c
d e f
g h i

Entries a, e and i form the diagonal. Notation wise, A[i,i] are the diagonal entries.

If a matrix has zeroes in entries below the diagonal, it’s known as an upper triangular matrix. In our case, d = g = h = 0.

Similarly, if a matrix has zeroes in entries above the diagonal, it’s known as a lower triangular matrix. In our case, b = c = f = 0.

What symmetry means in this case is b=d, c=g and f=h. The general formula is
A[i,j] = A[j,i]

To speed up computations when checking symmetry, some algorithms use
A[i,j] = A[j,i], where i < j

The extra condition leaves out the diagonal and entries below the diagonal. No point double checking values, right?

Transpose of a matrix

Now that we know what a symmetrical matrix and its diagonal, we can define the transpose of a matrix. What you do is simply flip the matrix about its diagonal.

For a matrix A whose values are:
a b c
d e f
g h i

Its transpose is:
a d g
b e h
c f i

The transpose of a matrix A is denoted by A^T. So if A = A^T, A is a symmetrical matrix.

Yes, we’re dealing with square matrices. Rectangular matrices aren’t useful for our purposes in 3D programming, and you’re welcome to research on its practical uses (try “operations research“).

The inverse of a matrix

The inverse of a square matrix A is denoted by A^-1, where
AA^-1 = A^-1A = I

Yes, I know I still haven’t covered matrix multiplication. Just go with it a little longer…

For a matrix product AB, it’s inverse is
(AB)^-1 = B^-1A^-1

Then this looks beautiful:
(AB)^-1AB
= B^-1A^-1AB
= B^-1IB
= B^-1B
= I

Don’t you think that looks beautiful? *smile*

Matrix equality

Matrices A and B are said to be equal if every corresponding entry of both matrices are equal. In notation, A[i,j] = B[i,j] for all i and j.

Matrix addition (and subtraction)

A matrix C is said to be the sum of matrices A and B if
C[i,j] = A[i,j] + B[i,j] for all i and j.

Subtraction is similar. Let me show you a scalar example.
8 - 5 = 8 + (-5)
Same thing for matrices. The negative sign is “pushed in” to individual entries.

Matrix multiplication by scalar

Let’s multiply matrices by scalars first. It’s easy.

Just multiply the scalar with all the entries in the matrix.

Matrix multiplication by vector

This one’s a little more complicated. For our purposes, we are concerned with multiplying a matrix A by a column vector v. Yes, the order and the type of vector matters. Let’s look at a diagram.

The result is a column vector. Suppose we multiply matrix A by column vector x and we get a column vector y, the general formula is
y[i] = A[i,0] * x[0] + A[i,1] * x[1] + … + A[i,n] * x[n]

It actually looks much more concise if I can use the summation notation… BUT, I’m trying to simplify things for you. Hopefully, you can visualise how it works with the diagram. I’ll write another post with code to explain this.

You can’t multiply a matrix by a row vector though. Hopefully through the diagram, you’ll see why it doesn’t work. What happens is, you multiply each row of the matrix by the values down the column vector. Since a row vector only has one value “down the column”, it doesn’t make sense to multiply matrices by row vectors.

You can multiply a row vector by a matrix to get a row vector. But it’s not useful for our purposes. If you understand a little about 3D transformations, then A is a transformation matrix, and x is a vertex. For example, A could be a translation matrix and moves x to point y. If you don’t understand any of this, relax, we’ll get there together soon.

Matrix and matrix multiplication

This is complicated to show and explain, but once you get the idea, it’s actually easy to code.

I’ll leave it to you to figure out the general formula… It’s similar to the one with matrix by vector multiplication, only with more vectors. *smile* This is what I do in university, write out a’s and subscripts, and summation notations in my lecture notes and tutorial questions…

I’ll write another post explaining this (together with the matrix by vector multiplication) with code to illustrate the use.

In terms of 3D transformations, you could have a bunch of transformations done, say you rotate something, then translate (move) it. So you have something like TRx, where R is the rotation matrix, T is the translation matrix and x is the vertex.

Note the order. The earlier (in order) a transformation is done, the closer it is to the vertex in question. Basically you reverse the order of transformations when implementing.

Since we’re at it, matrix multiplications are not commutative. What it means is that
AB != BA
The order is important.

As an exercise, visualise the difference between moving something then rotate, and rotate then move.

End of crash course

Whew… *wipe sweat* How’re you doing? Still with me?

Good. This sets the foundation you need for understanding 3D programming. Yay! Review what you’ve read, do some research if needed, and I’ll see you next time.

Puzzle of 7 points and 6 straight lines - 2nd solution

This is the second solution to this puzzle: Construct a geometric shape with 7 points such that there are 6 straight lines, and each line must pass through 3 points. The first solution was already discussed last week.

And here’s the construction:

The 7 points are labelled A to G. The 6 lines are ADB, AFC, AGE, DGF, DEC and FEB. No, I didn’t label the points so I’ll have AGE and the short forms of the months December and February. It just happened that way…

The construction starts with point A, and you draw two lines down to get points B and C. The lines AB and AC must be of the same length. Then from point B, draw a perpendicular line to meet line AC. That meeting point is F.

From this construction, angles AFB, AFE, CFB and CFE are right angles (90 degrees).

Do the same thing from point C and draw a perpendicular line to meet line AB, and you’ll get point D. Similarly, angles ADC, ADE, BDC and BDE are right angles.

The point E is formed from the cross point of lines DC and FB that was just formed.

Draw a line joining D and F. Draw another line joining A and E. The cross point of lines DF and AE is point G.

The first solution focused on getting the points right, and then forming lines to fit them. This solution focused on constructing the lines, and the required points magically appear.

On hindsight, we didn’t need the right angles to be there. As long as D and F meet the lines AB and AC respectively in the same ratio, the solution is still valid. There are 2 criteria to meet:

• Lines AB and AC must be of the same length. This allows symmetry.
• The length ratios AD:AB and AF:AC must be equal. This is dependent on the previous criteria.

[Update] Yes, that is one heck of a correction. 3 criteria:

• Points B, A, and C don’t form a straight line (they’re not collinear)
• D is somewhere on the line AB (and D not equal to A nor B)
• F is somewhere on the line AC (and F not equal to A nor C)

Then follow similar construction steps for points E and G and as Eric puts it, the rest just happens. Thank you Eric for pointing this out.

Ok, 2 solutions were presented. I hope you had fun reading and thinking about the puzzle.

Puzzle of 7 points and 6 straight lines

My friend presented me with a puzzle: Construct a geometric shape with 7 points such that there are 6 straight lines, and each line must pass through 3 points.

My friend came up with a solution, but he wasn’t sure, so he consulted me. Actually there was a “model” answer, but he wanted to find another solution. So we had 2 solutions. I’ll present that model answer here so you can understand the puzzle better.

Points A, B and C form an equilateral triangle. Points D, E and F are the midpoints of lines AB, AC and BC respectively. Point G is the centre of the triangle.

Note: 3 points are collinear if they lie on a straight line.

The 7 points are A to G. The 6 lines are formed by ADB, AEC, BFC, AGF, BGE and CGD.

[I'm not going to go too much into math theories and proofs. Besides, I'm not even sure if I can recall them after losing track for so long...]

The first three lines should be easy to understand. D is the midpoint of AB, so ADB is a straight line. So it is for AEC and BFC.

E is the midpoint of AC, and BE is the perpendicular bisector (remember ABC is an equilateral triangle). And G lies on the line BE, since G is the centre of the triangle. So BGE is a straight line.

Using this reasoning, AGF and CGD are also straight lines.

I know, the explanation I gave isn’t quite backed up with math proofs, more with intuitive reasoning. But I’m sure they are (I just don’t know exactly which theorems to cite…).

So I have 2 favours:

• Send me a more proper explanation of the solution given above
• Or send me another solution (remember I have another one?)

I know there are at least 2 solutions. Just wondering if there are more. I will post my other solution, together with any submissions from you next Monday. Or earlier, depending on the number of submissions. You’re welcome to do both. *smile*

Since this is a geometric construction, a picture together with some explanations is appreciated. You can host the image on a site like Flickr, then add a comment to this post with a link to that image and a brief explanation.

Or you can send me your solution via email to vincent at polymathprogrammer dot com. Let me know if you want to remain anonymous (why?), and I’ll just post your solution only.

Your construction doesn’t have to be exact in proportions. Meaning if there’s a right angle, it doesn’t have to be 90 degrees exactly, so long as it looks like it’s 90 degrees. Just add some explanation to supplement the drawing. Try Paint.NET if you don’t have any image editing software.

Have fun!

The barber paradox

Suppose there’s a barber who shaves only those who do not shave themselves. The question is, does the barber shave himself?

That was the question I posed in a previous article. The hint to the answer was actually given in the article: “What if your original assumptions were wrong?”

So let’s begin, with two fictitious men, John and Ricky. John has this unfortunate streak of accidental cuts, so he doesn’t shave himself if he could help it. Ricky has this inexplicable fear of people wielding sharp objects around his face (ever watched Sweeney Todd?), so he shaves his own beard.

It’s actually a mathematical question on logic. So forming the statements, we have:

If John does not shave himself, the barber shaves John.
If Ricky shaves himself, the barber does not shave Ricky.

Here’s the interesting part. Let’s substitute “John” and “Ricky” with “the barber”.

If the barber does not shave himself, the barber shaves the barber.
If the barber shaves himself, the barber does not shave the barber.

Either way, the statements don’t make logical sense, each contradicting itself and creating a paradox. So what went wrong?

The statements were correctly formed. It’s our original assumption that’s wrong. What’s our original assumption? That

there’s a barber who shaves only those who do not shave themselves

So the correct answer is, there’s no such barber.

Fibonacci sequence and Golden Ratio

I haven’t written a math-related article in a while, so in this article, I’ll tell you about the Fibonacci sequence, the golden ratio and some associated program code.

Say you’re given this math formula, and told to find what the nth term is.
F(n) = F(n-1) + F(n-2)
where F(1) = F(2) = 1

Wow, initial conditions are given, a formula is given. Functions! In fact, use recursive functions! That was easy to code, wasn’t it?

What if you’re given this sequence of numbers and told to find what the nth term is?
1,1,2,3,5,8,13,21 …

You would get exactly the same answer for both questions. Notice that each subsequent number is a sum of the previous two numbers (except the first two in the sequence). Once you find the pattern, you can make use of simple loops instead of recursive functions. Generally speaking, recursive functions are slower, and you would not have known the simpler loop solution if you hadn’t analysed the problem first.

Of course, if you knew the numbers form the Fibonacci sequence, you wouldn’t have much of a problem in the first place, would you? You might have heard of it in Da Vinci Code, where the sequence was used to decipher a password number.

Now, the interesting thing about this sequence is that Nature uses it. I haven’t personally verified this, but sunflowers, pineapples and daisies exhibit the use. If you count the number of bumps on them going to the left, and the number of bumps to the right, you’ll find that the numbers are right next to each other in the Fibonacci sequence. For example, sunflowers have 34 spirals to the left and 55 to the right.

The rabbits, man do they breed!

There’s actually a story about how the Fibonacci sequence came about. You might have guessed that Fibonacci is the name of a mathematician. Anyway, the story goes like this. Suppose there are 2 rabbits, one male and one female. Each month, they produce two rabbits, again, one male and one female. The baby rabbits take one month to grow, and become sexually reproductive in their second month. In this manner, how many rabbits are there at the end of 12 months?

In the first month, there are 2.
At the end of the second month, there’s 4 (2 original, 2 babies).
At the end of the third month, there’s 6 (2 original, 2 from 2nd month, 2 babies from original).

At the end of the fourth month, there’s the original 2, the 2 from 2nd month, the 2 from 3rd month, 2 babies from the original 2, and 2 babies from the 2 of the 2nd month. Total rabbits: 10.

Just typing this out is confusing, but you can see a pattern emerging.
2, 4, 6, 10 …
Each subsequent term is a sum of the previous two terms.

Oh yes, the number of rabbits in the 12th month is 466.

Some obvious assumptions are

• Rabbits never die
• Babies are always produced in a pair, one male and one female
• Moral values are not considered (incest shmincest!)

The golden ratio

There is another interesting thing. The ratio of F(n+1)/F(n) approaches a limit as n goes to infinity, which is approximately 1.618. This number is known as the golden ratio, with other names such as golden mean, divine proportion and others. Other than its mathematical relevance, I know it to be important as an aesthetic factor.

A rectangle with its sides in this ratio is thought of as aesthetically pleasing. This probably influenced the manufacture of computer screens. You have your standard 4:3s (1.333:1), the 800×600, 1024×768 and others. There are also some who tried the square root 2 ratio, 1.414:1 in computer applications. Then there’s the 16:9 (1.777:1) aspect ratios.

What’s the purpose of these aspect ratios? To approach the golden ratio 1.618:1. Of course, with widescreens, this point is probably moot nowadays. Still, it makes for interesting contemplation.

Ok, let’s do some coding, calculating the nth term using a loop, which I’ve hardcoded as 20. I’ll leave it to you as an exercise to write it as a function. The golden ratio is calculated as well. The first 2 terms are skipped, because they are equal to 1 (initial conditions).

int i;
int current, previous, next;
double phi = 0;
current = previous = 1;
for (i = 2; i < 20; ++i)
{
    next = current + previous;
    previous = current;
    current = next;
    phi = (double)current/(double)previous;
    Console.WriteLine("Term {0,0:d2} = {1,0:d5}, Phi = {2,0:f8}", i + 1, current, phi);
}

Fairly simple. The point is to convert a problem into a program solution. The difficult part isn’t the original problem, nor is it about coding skills. It’s about translating a problem into a program that’s difficult.

There you have it. Math theory and supporting program code. Hope you enjoyed it.