Matrices can be your friends (2002)

Thank u so much brother.

I'm surprised we even agree that they should be top-down.

ah, so you can get row vectors with a type cast in C but not column ones. While in Fortran and friends is the converse (if they casted). Yep that is more mathy. Linear map evaluation is linear combination of columns.

EDIT: type cast or just single square bracket application in C

Languages that don't have multidimensional arrays tend to have "arrays of arrays" instead, and that naturally leads to a layout where the last subscript varies fastest. Languages that do have multidimensional arrays can of course lay them out in any order.

Yes. I think what all mathematicians can agree on is that the layout (and the starting index! :-) is like this:

  A[1,1] … A[1,n]
   …        …
  A[m,1] … A[m,n]

I assume they're talking about how when multiplying by a matrix by a vector, it's more natural to think of the matrix as a collection of columns than as a collection of rows, and to think of the vector as a column vector.

That layout is a nearly universal convention in applied practice such as statistics. Readers would be very very confused if you flipped it the other way.

The irony is that "programmers" are much more divided on this than statisticians are.

The MKL blas/lapack implementation also provides the “cblas” interface (I’m sure most blas implementations do, I’m just familiar with MKL—BLIS seems quite willing to provide additional interfaces to I bet they provide it as well) which explicitly accepts arguments for row or column ordering.

Internally the matrix is tiled out anyway (for gemm at least) so column vs row ordering is probably a little less important nowadays (which isn’t to say it never matters).

> is written in languages that inherited their array ordering from C

It’s not just C. Modern GPU hardware only supports row major memory layout for 2D and 3D textures (ignoring specialized layouts like swizzling and block compression but none of them are column major either). Modern image and video codecs only support row major layout for bitmaps.

Really wonder who in his right mind, who can also read a book, would decide to do so in order to enumerate the sequences of items…

> most programmers are visual thinkers

I remember reading that there's a link between aphantasia (inability to visualize) and being on the spectrum.

Being an armchair psychologist expert with decades of experience, I can say with absolute certainty that a lot of programmers are NOT visual thinkers.

You can do rotation with a 3x3 matrix.

The first lecture was using a 4x4 matrix because you can use it for a more general set of transformations, including affine transforms (think: translating an object by moving it in a particular direction).

Since you can combine a series of matrix multiplications by just pre-multiplying the matrix, this sets you up for doing a very efficient "move, scale, rotate" of an object using a single matrix multiplication of that pre-calculated 4x4 matrix.

If you just want to, e.g., scale and rotate the object, a 3x3 matrix suffices. Sounds like your first lecture jumped way too fast to the "here's the fully general version of this", which is much harder for building intuition for.

Sorry you had a bad intro to this stuff. It's actually kinda cool when explained well. I think they probably should have started by showing how you can use a matrix for scaling:

    [[2, 0, 0],
     [0, 1.5, 0],
     [0, 0, 1]]

for example, will grow an object by 2x in the x dimension, 1.5x in the y dimension, and keep it unchanged in the z dimension. (You'll note that it follows the pattern of the identity matrix). The derivation of the rotation matrix is probably best first derived for 2d; the wikipedia article has a decentish explanation:

https://en.wikipedia.org/wiki/Rotation_matrix

The mathematical term for the four by four matrices you were looking at is "quaternion" (I.e. you were looking at a set of four by four matrices isomorphic to the unit quaternions).

Why use quaternions at all, when three by three matrices can also represent rotations? Three by three matrices contain lots of redundant information beyond rotation, and multiplying quaternions requires fewer scalar additions and multiplications than multiplying three by three matrices. So it is cheaper to compose rotations. It also avoids singularities (gimbal lock).

Yeah you need to build up the understanding so that you can re-derive those matrices as needed (it's mostly just basic trigonometry). If you can't, that means a failure of your lecturer or a failure in your studying.

In computer graphics, 4x4 matrices let you do a rotation and a translation together (among other things). There's the 3x3 rotation block you found later as well as a translation vector embedded in it. Multiplying a sequence of 4x4 matrices together accumulates the rotations and translations appropriately as if they were just a bunch of function applications. i.e. rotate(translate(point)) is just rotation_matrix * translation_matrix * point_vector if you construct your matrices properly. Multiplying a 4x4 matrix with another 4x4 matrix yields a 4x4 matrix result, which means that you can store an arbitrary chain of rotations and translations accumulated together into a single matrix...

Usually you just draw a 2D or 3D picture and say "n" while pointing to it. e.g. I had a professor that drew a 2D picture on a board where he labeled one axis R^m and the other R^n and then drew a "graph" when discussing something like the implicit function theorem. One takeaway of a lot of linear algebra is that doing this is more-or-less correct (and then functional analysis tells you this is still kind-of correct-ish even in infinite dimensions). Actually SVD tells you in some sense that if you look at things in the right way, the "heart" of a linear map is just 1D multiplication acting independently along different axes, so you don't need to consider all n dimensions at once.

I think teaching beginner linear algebra using matrices representing systems of equations is a pedagogical mistake. It gives the wrong impression that matrices are linear algebra and makes it difficult for students to think about it in an abstract way. A better way is to start by discussing abstract linear combinations and then illustrating what can be done with this using visualizations in various coordinate systems. Once the student understands this intuitively, systems of equations and matrices can be brought up as equivalent ways to represent linear transformations on paper. It’s important to emphasize that matrices are convenient but not the only way to write the language of linear algebra.

Here are some applications of eigenvectors and eigenvalues:

1) If you have a set of states and a stochastic transition function, which gives for each starting state, the probability distribution over what the state will be at the next time step, you can describe this as a matrix. The long-term behavior of applying this can be described using the eigenvectors and eigenvalues of this matrix. Any stable distribution will be an eigenvector with eigenvalue 1. If there is periodicity to the behavior, where for some initial distributions, the distribution will change over time in a periodic way, where it ends up endlessly cycling through a finite set of distributions, then the matrix will have eigenvalues that are roots of unity (i.e. a complex number s such that s^n = 1 for some positive integer n). Eigenvalues with absolute value less than 1 correspond to transient contributions to the distribution which will decay (the closer to 0, the quicker the decay.). When there are finitely many states, there will always be at least one eigenvector with eigenvalue 1.

2) Related to (1), there is the PageRank algorithm, where one takes a graph where each node has links to other nodes, and one models a random walk on these nodes, and one uses the eigenvector one (approximately) finds in order to find the relative importance of the different nodes.

3) Rotations generally have eigenvalues that are complex numbers with length 1. As mentioned in (1), eigenvalues that are complex numbers with length 1 are associated with periodic/oscillating behavior. Well, I guess it sorta depends how you are using the matrix. If you have a matrix M with all of its eigenvalues purely imaginary, then exp(t M) (with t representing time) will describe oscillations with rates given by those eigenvalues. exp(t M) itself will have eigenvalues that are complex numbers of length 1. This is very relevant in solutions to higher order differential equations or differential equations where the quantity changing over time is a vector quantity.

____

But, for purposes of gamedev, I think probably the eigenvalues/eigenvectors are probably the less relevant things. Probably instead, at least for rendering and such, you want stuff like, "you can use homogeneous coordinates in order to incorporate translations and rotations into a single 4x4 matrix (and also for other things relating the 3d scene to the 2d screen)", and stuff about like... well, quaternions can be helpful.

Of course, it all depends what you are trying to do...

The most obvious application for eigenvalues is that if you find the eigendecomposition A=QλQ^{-1}, where λ=diag(eigenvalues) you can cheaply obtain the results of A^n = QλQ^{-1} ... QλQ^{-1} ... QλQ^{-1} = Qλ^nQ^{-1}. A less likely use is for inverting A or solving a linear system of equations with it.

To remind oneself how to multiply matrices together, it suffices to remember how to apply a matrix to a column vector, and that ((A B) v) = (A (B v)).

For each 1-hot vector e_i (i.e. the row vector that has a 1 in the i-th position and 0s elsewhere), apply B e_i to get the i-th column of the matrix B. Then, apply the matrix A to the result, to obtain A (B e_i), which equals (A B) e_i . This is then the i-th column of the matrix A B. And, when applying the matrix A to some column vector v, for each entry/row of the resulting vector, it is obtained by combining the corresponding row of A, with the column vector v.

So, to get the entry at the j-th row of the i-th column of (A B), one therefore combines the i-th column of B with the j-th row of A. Or, alternatively/equivalently, you can just compute the matrix (A B) column by column, by, for each e_i , computing that the i-th column of (A B) is (A (B e_i)) (which is how I usually think of it).

To be clear, I don't have the process totally memorized; I actually use the above reasoning to remind myself of the computation process a fair portion of the time that I need to compute actual products of matrices, which is surprisingly often given that I don't have it totally memorized.

When I took linear algebra, the professor emphasized the linear maps, and somewhat de-emphasized the matrices that are used to notate them. I think this made understanding what is going on easier, but made the computations less familiar. I very much enjoyed the class.

I think this is pretty instructor-dependent. I had two LinAlg courses, and in the first, I felt like I was building a great intuition. In the second, the instructor seemed to make even the stuff I previously learned seem obtuse and like "facts to memorize."

Maybe linear algebra is more instructor-dependent, since we have fewer preexisting concepts to build on?

I'm an applied math PhD who thinks linear algebra is the best thing ever, and it's the nuts and bolts of modern AI, so for fun and profit I'll attempt a quick cheat sheet.

To manage expectations, this won't be very satisfying by itself. You have to do a lot of exercises for this stuff to become second nature. But hopefully it at least imparts a sense that the topic is conceptually meaningful and not just a profusion of interacting symbols. For brevity, we'll pretend real numbers are the only numbers that exist; assume basic knowledge of vectors; and, I won't say anything about eigenvalues.

1. The most important thing to know about matrices is that they are linear maps. Specifically, an m x n matrix is a map from n-dimensional space (R^n) to m-dimensional space (R^m). That means that you can use the matrix as a function, one which takes as input a vector with n entries and outputs a vector with m entries.

2. The columns of a matrix are vectors. They tell you what outputs are generated when you take the standard basis vectors and feed them as inputs to the associated linear map. The standard basis vectors of R^n are the n vectors of length 1 that point along the n coordinate axes of the space (the x-axis, y-axis, z-axis, and beyond for higher-dimensional spaces). Conversely, a vector with n entries is also an n x 1 column matrix.

3. Every vector can be expressed uniquely as a linear combination (weighted sum) of standard basis vectors, and linear maps work nicely with linear combinations. Specifically, F(ax + by) = aF(x) + bF(y) for any real-valued "weights" a,b and vectors x,y. From this, you can show that a linear map is uniquely determined by what it maps the standard basis vectors to. This + #2 explains why linear maps and matrices are equivalent concepts.

4a. The way you apply the linear map to an arbitrary vector is by matrix-vector multiplication. If you write out (for example) a 3 x 2 matrix and a 2 x 1 vector, you will see that there is only one reasonable way to do this: each 1 x 2 row of the matrix must combine with the 2 x 1 input vector to produce an entry of the 3 x 1 output vector. The combination operation is, you flip the row from horizontal to vertical so it's a vector, then you dot-product it with the input vector.

4b. Notice how when you multiply 3x2 matrix with 2x1 vector, you get a 3x1 vector. In the "size math" of matrix multiplication, (3x2) x (2x1) = (3x1); the inner 2's go away, leaving only the outer numbers. This "contraction" of the inner dimensions, which happens via the dot product of matching vectors, is a general feature of matrix multiplication. Contraction is also the defining feature of how we multiply tensors, the 3D and higher-dimensional analogues of matrices.

5. Matrix-matrix multiplication is just a bunch of matrix-vector multiplications put side-by-side into a single matrix. That is to say, if you multiply two matrices A and B, the columns of the resulting matrix C are just the individual matrix-vector multiplications of A with the columns of B.

6. Many basic geometric operations, such as rotation, shearing, and scaling, are linear operations, so long as you use a version of them that keeps the origin fixed (maps the zero vector to zero vector). This is why they can be represented by matrices and implemented in computers with matrix multiplication.

Here's a recipe for matrix multiplication that you can't forget: choose bases b_i/c_j for your domain/codomain. Then all a matrix is is listing the outputs of a function for your basis: if you have a linear function f, then the ith column of its matrix A is just f(b_i). If you have another function g from f's codomain, then same thing, its matrix B is just the list of outputs g(c_j). Then the ith column of BA is just g(f(b_i)). If you write these things down on paper and expand out what I wrote, you'll see the usual row and column thing pop out. The point is that f(b_i) is a weighted sum of the c_i (since c_i is a basis for the target of f), but you can pull the weighted sums through the definition of g because it's linear. A basis gives you a minimal description/set of points where you need to define a function, and the definition for all other points follows from linearity.

The point of the eigen-stuff is that along some directions, linear functions are just scalar multiplication: f(v) = av. If the action in a direction is multiplication by a, then it can't also be multiplication by b. So unequal eigenvalues must mean different directions/linearly independent subspaces. So e.g. if you can find n different eigenvalues/eigenvectors, you've found a simple basis where each direction is just multiplication. You also know that it's invertible if the eigenvalues are nonzero since all you did was multiply by a_i along each direction, so you can invert it by multiplying by 1/a_i on each direction.

Taught properly it's all very straightforward, though determinants require some more buildup with a detour through things like quotienting and wedge products if you really want it to be straightforward IMO. You start by saying you want to look at oriented areas/volumes, and look at the properties you need. Then quotienting gives you a standard tool to say "I want exactly the thing that has those properties" (wedge products). Then the action on wedges gives you what your map does to volumes, with the determinant as the action on the full space. You basically define it to be what you want, and then you can calculate it by linearity/functoriality just like you expand out the definition of a linear map from a basis.

IDK why but the replies to your comment crack me up because they ended up confusing me rather than helped. It's the same for me. Impenetrable.

You might want to try Linear Algebra Done Right by Sheldon Axler. It's a short book, succinct but extremely clear and approachable. It explains Linear Algebra without using determinants, which are relegated to the end, and emphasises understanding the powerful ideas underpinning the subject rather than learning seemingly arbitrary manipulations of lists and tables of numbers.

Those manipulations are of course extremely useful and worth learning, but the reasons why, and where they come from, will be a lot clearer after reading Axler.

As someone pointed out elsewhere in this thread, the book is available free at https://linear.axler.net/

You might like to try this website that explains it quite intuitively:

https://betterexplained.com/articles/matrix-multiplication/

OK, now what?

This is the most important part.

"...linear transformations between vector spaces."

When you understand what that implies you can start reasoning about it visually.

The 3 simplest (that you can find in blender or any other 3d program, or even partly in 2d programs).

Translation (moving something left,right,up,down,in,out).

Rotation (turn something 2 degrees, 90 degrees, 180 degrees, 360 degrees back to the same heading)

Scaling (make something larger, smaller, etc)

(And a few more that doesn't help right now)

The 2 first can be visualized simply in 2d, just take a paper/book/etc. Move it left-right, up down, rotate it.. the book in the original position and rotation compared to the new position and rotation can be described as a vector space transformation, why?

Because you can look at it in 2 ways, either the book moved from your vantage point, or you follow the book looking at it the same way and the world around the book moved.

In both cases, something moved from one space (point of reference) to another "space".

The thing that defines the space is a "basis vector", basically it says what is "up", what is "left" and was in "in" in the way we move from one space to another.

Think of it as, you have a piece card on a paper. Draw an line/axis along the bottom edge as the X count, then draw on the left side upwards the Y count. In the X,Y space (from space) you count the X and Y steps of various feature points.

Now draw the "to space" as another X axis and another Y axis (could be rotated, could be scaled, could just be moved) and take the counts in steps and put them inside the "to space" measured in equal units as they were in the from space.

Once the feature points are replicated in the "to space" you should have the same image as before, just within the new space.

This is the essence of a so called linear(equal number steps) transform (moved somewhere else), and also exactly what multiplying a set of vectors by a matrix achieves (simplified, in this context, the matrix really is mostly a representation of a number of above mentioned basis vectors that defines the X, Y,etc of the movement).

Spatial transformations? Take a look at the complex matrices in Fourier transforms with nth roots of unity as its elements. The values are cyclic, and do not represent points in an n-D space of Euclidean coordinates.

> The fundamental truth is that matrices represent linear transformations, and all of linear algebra is developed in terms of linear transformations...

Not at all. It is most definitely not a fundamental truth. I think you are conflating matrix multiplication with matrices, as if that's the only operation that one does on matrices.

Matrices are a way to organize data and what operations you define over the matrices define what it represents.

There are other useful operations on matrices, for example Hadamard products, Schur products, Kronecker product, face split products of matrices that finds use in Physics and Engineering (antenna design for one) where the operation does not represent a linear transformation. They can form an algebra and/or algebraic structures different from the very familiar linear algebraic one.