How is Matrix Multiplication a Transformation?
A matrix is just a big grid of numbers with rules that define how we can multiply it with other grids or lists of numbers.
In games, we usually want to construct a matrix so that, when multiplied with a list of numbers representing a source position (say, the position of a vertex in a mesh) we get a list of numbers representing a destination position (say, the position of that vertex in the game world, after applying the transformations of all its parent objects, or the position of the vertex projected on the screen by our camera)
Because of how matrix multiplication is defined, we can choose to write this in one of two ways, either: DestinationColumnVector = Matrix * SourceColumnVector
$$
\require{HTML} \style{display: inline-block; transform: rotate(-90deg)}{\begin{bmatrix} \text{vector}\end{bmatrix}}
=
\begin{bmatrix} \text{some big}\\ \text{squarish} \\ \text {matrix}\end{bmatrix}
\times
\require{HTML} \style{display: inline-block; transform: rotate(-90deg)}{\begin{bmatrix} \text{vector}\end{bmatrix}}
$$
or DestinationRowVector = SourceRowVector * Matrix
$$
\begin{bmatrix} \text{destination row vector} \end{bmatrix}
= \begin{bmatrix} \text{source row vector} \end{bmatrix}
\times
\begin{bmatrix} \text{some big}\\ \text{squarish} \\ \text {matrix}\end{bmatrix}
$$
I'm most familiar with the first convention, so that's what I'll use for the examples below, with arrows to denote vectors (in code we usually don't distinguish a vector's row/column orientation) and blackboard bold to denote matrices.
$$\vec p_\text{destination} = \Bbb M \times \vec p_\text{source}$$
If your environment uses the opposite convention, just transpose all of the examples below (turn each column into a row)
What Are We Transforming?
The vectors we're transforming will typically look like this:
$$\begin{array}{cc}
\vec p_\text{source}=\begin{bmatrix}
p_x \\
p_y \\
p_z \\
1 \\
\end{bmatrix}
&
\vec d_\text{source}=\begin{bmatrix}
d_x \\
d_y \\
d_z \\
0 \\
\end{bmatrix}
\end{array}$$
Where \$\vec p_\text{source}\$ is the source position we want to transform into a new coordinate space. The "w" coordinate of 1 means we're using homogeneous coordinates to apply translation.
If instead we're transforming a vector that represents an offset or direction \$\vec d_\text{source}\$, not a position, then we want to ignore any translation in the matrix. (My right arm, outstretched to the side, forms an offset vector from my shoulder to my finger that always points to my right and never gets longer or shorter, no matter where I stand relative to the world origin point). We can do this by setting the "w" component to 0 instead of 1.
This is useful for things like surface normal vectors, but note that if you're applying scaling, then you'll want to use a different, related matrix called the "inverse transpose", \$(\Bbb M^{-1})^T\$, to ensure the normals flatten out correctly and stay perpendicular to the mesh surface as you squash or stretch the model.
What Makes Up a Matrix?
A typical object transform in games (not including camera projection), describing the relationship from our source coordinate system (local/model space) to our destination coordinate system (parent/world space) will look like this:
\$\Bbb M=\begin{bmatrix}
m_{00} & m_{01} & m_{02} & m_{03} \\
m_{10} & m_{11} & m_{12} & m_{13} \\
m_{20} & m_{21} & m_{22} & m_{23} \\
0 & 0 & 0 & 1 \\
\end{bmatrix}= \Bbb T \times \Bbb R \times \Bbb S\$
That is:
\$\vec p_\text{destination} = \Bbb M \times \vec p_\text{source} = \Bbb T \times \Bbb R \times \Bbb S \times \vec p_\text{source}\$
Since we rarely deliberately introduce skew in object transformations, this matrix is generally the product of three distinct kinds of transformations, which we could look at as being three distinct matrices: a translation \$\Bbb T\$, a rotation \$ \Bbb R\$, and an axis-aligned scale \$ \Bbb S\$.
Looking at these in order of application from "most local" (applied directly to \$\vec p_\text{source}\$ in its source space) to "most global" (applied as the last step to get to our final world space position \$\vec p_\text{destination}\$, we have...
Axis-Aligned Scale
Scaling each of the x, y, and z axes of the source space by factors of \$s_x, s_y, s_z\$ respectively:
\$\Bbb S=\begin{bmatrix}
s_x & 0 & 0 & 0 \\
0 & s_y & 0 & 0 \\
0 & 0 & s_z & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\$
Doing this first ensures that our scales are applied parallel to our local axes, rather than squishing the object diagonally when we rotate it.
You'll notice that if all three scale factors are 1 (100% normal size, no change), then this matrix is the "Identity matrix" with all 1s on the main diagonal and zeroes elsewhere. An identity represents "no transformation" / "source and destination spaces are identical" which is exactly what we expect when applying no scale, so this is a good sign that we got our math right so far. :)
Rotation to a New Coordinate Basis
Here we need to choose three unit vectors (length = 1) that are perpendicular to each other (orthogonal), to describe which way the object's right, up, and forward directions should point at the end of the rotation.
The exact names/interpretation we apply to each axis depends on the coordinate system conventions and handedness of the environment we're working in. For a concrete example, in Unity's left-handed coordinate system, we'd choose these vectors so that...
Our local x direction rotates to point to our new "rightward"
\$\vec r = \begin{bmatrix} r_x \\ r_y \\ r_z \\ 0 \end{bmatrix} = \Bbb R \times \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}\$
Our local y direction rotates to point to our new "upward"
\$\vec u = \begin{bmatrix} u_x \\ u_y \\ u_z \\ 0 \end{bmatrix} = \Bbb R \times \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}\$
Our local z direction rotates to point to our new "forward"
\$\vec f = \begin{bmatrix} f_x \\ f_y \\ f_z \\ 0 \end{bmatrix} = \Bbb R \times \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}\$
If we take a unit vector along each of the x, y, and z axes to these new cardinal directions, then every vector that's a combination of x, y, and z will be taken to the corresponding combination of \$\vec r, \vec u, \vec f\$, because matrix multiplication is a linear operation.
Now, storing 3 independent vectors is strictly redundant here (once you know \$\vec r\$ and \$ \vec u\$, there's only one choice for \$\vec f = \vec r \times \vec u\$, using the vector cross product) so in practice we'll usually store our rotations as either a quaternion or a trio of Euler/Tait-Bryan angles, and make the vectors on demand (using eg. quaternion multiplication or spherical coordinate formulae) when it's time to do matrix math with them.
Once we have our basis vectors, to make a matrix that rotates to face them, all we need to do is stuff these vectors in as the first three columns:
\$R= \begin{bmatrix}
\vec r & \vec u & \vec f & \begin{matrix}0\\0\\0\\1\end{matrix}
\end{bmatrix} =\begin{bmatrix}
r_x & u_x & f_x & 0 \\
r_y & u_y & f_y & 0 \\
r_z & u_z & f_z & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\$
Again, notice if our right vector is just the x+ direction (1, 0, 0, 0), and up is y+, and forward is z+, then this is just an identity matrix. "No rotation change"
One handy trick with rotation matrices like this: if you take the transpose, flipping the matrix along its main diagonal, so each row becomes a column and each column a row, then what you get is also a rotation matrix, one that exactly reverses the rotation we started with. Twist, and untwist. We say the transpose of a rotation matrix is also its inverse. :)
And lastly...
Translation to a New Location in Space
Now that we have the object in the shape/size and orientation we want, it's time to place it at the desired position in our scene. We do this last, because scaling and rotation both stretch/squash or rotate things around the origin. If we translated first, our pivot would change based on where we are in the world.
So far both the transformations we've used keep the origin the vector where it was (run (0,0,0,1) through both of the above: no matter how you choose \$s_x, s_y, s_z, \vec r, \vec u, \vec f\$, you always get (0, 0, 0, 1) back out! This is another consequence of matrix multiplication being a linear operation. Zero has to map to zero. If we were using 3x3 matrices and 3-vectors, we'd be out of luck - there would be no way to use a matrix to shift the result off the origin.
But we really would like to be able to take a mesh centered at the origin, and use a matrix to move it to a new part of our scene. That's where this mysterious fourth row / "w" coordinate comes in, using a technique called "homogeneous coordinates"
By bumping up from 3 dimensions to 4 dimensions, we can place all of our content, including the center/pivot of our object, a little away from the origin - not at (0, 0, 0, 0), but at (0, 0, 0, 1). We're 1 unit away from the origin in the w dimension, and that lets use use a fourth column of our matrix to reposition everything - even our pivot point. It's effectively a 4-dimensional shear operation under the hood. But when we lop-off the w to get back to 3D, the effect is translation. :D
So, to translate (shift) our space by an offset vector \$\vec t = \begin{bmatrix}
t_x \\
t_y \\
t_z
\end{bmatrix}\$,
we need a matrix \$\Bbb T\$ such that \$ \begin{bmatrix} \vec t \\ 1 \end{bmatrix} = \Bbb T \times \begin{bmatrix}
0 \\
0 \\
0 \\
1 \end{bmatrix}\$.
Just like with the rotation case, we can get this by stuffing \$ \vec t \$ in as the fourth column of our matrix:
$$\Bbb T = \begin{bmatrix} \Bbb I_\text{3x3} & \vec t \\ \vec 0_3 & 1\end{bmatrix} = \begin{bmatrix}
1 & 0 & 0 & t_x \\
0 & 1 & 0 & t_y \\
0 & 0 & 1 & t_z \\
0 & 0 & 0 & 1 \\
\end{bmatrix}$$
Note again how if \$\vec t = \vec 0\$, ie. if we're applying no translation at all, then this again reverts to an identity matrix, leaving the space it's multiplied by unchanged.
Bringing it All Together
When we multiply all three of these component transformations together, we get:
$$\begin{align}\Bbb M &= \Bbb T \times \Bbb R \times \Bbb S\\
&= \begin{bmatrix}
1 & 0 & 0 & t_x \\
0 & 1 & 0 & t_y \\
0 & 0 & 1 & t_z \\
0 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
r_x & u_x & f_x & 0 \\
r_y & u_y & f_y & 0 \\
r_z & u_z & f_z & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
s_x & 0 & 0 & 0 \\
0 & s_y & 0 & 0 \\
0 & 0 & s_z & 0 \\
0 & 0 & 0 & 1 \\
\end{bmatrix}\\
&=\begin{bmatrix}
s_xr_x & s_yu_x & s_zf_x & t_x \\
s_xr_y & s_yu_y & s_zf_y & t_y \\
s_xr_z & s_yu_z & s_zf_z & t_z \\
0 & 0 & 0 & 1 \\
\end{bmatrix}
\end{align}$$
We've combined three different transformations into one, so now we can apply all three to a new vector for the cost of just one matrix multiplication. And this scales: if I have an object 10 levels deep in a transformation hierarchy, where each child inherits transformation from its parent and adds its own, I can compute a single matrix that combines all these transformations, to shortcut straight from local space to world space, without bubbling up one level at a time.
That's why we're so fond of using matrices to represent transformations: they're extremely flexible, and can collapse many complex operations down to just one straightforward mechanical process.
You'll notice through all that, the bottom row stayed constant. That's because we've been careful to keep to our homogeneous coordinate convention that all our content sits on the w=1 plane. In many math libraries, we'll even skip storing the 4th row in our vectors or matrices, and just pretend it's there by exposing separate methods to TransformPoint (simulate multiplication with a vector that has w=1) or TransformDirection (simulate multiplication with a vector that has w=0).
But this 4th row serves a whole different role once we get into rendering the scene with a camera: we can form a projection matrix that shoves depth information into the w coordinate, then divide by w to get a perspective projection, where things that are closer look bigger, and things that are further away get smaller. For those purposes, we'll typically store the whole 4 rows/components.
One last detail:
Row-Major vs Column-Major Layout
Using the conventions above, you can see vectors we care about often occur as columns in the matrix (eg. translation in the 4th column, direction vectors in the first three columns of the rotation matrix).
So, if we use a column-major matrix representation (where consecutive elements in a column are consecutive in memory storage order), this makes it convenient to set or read columns of the matrix (eg. T[3] = (tx, ty, tz, 1) to set the 4th column of a translation matrix).
A row-major representation would store consecutive elements in a row consecutively, making it easy to do operations on rows of the matrix at a time.
So, row-major vs column-major order is just about using the data representation that's most convenient for the matrix multiplication conventions used by your engine or programming environment.
