Matrix Multiplication as Composition

Matrix multiplication as composition underlies every place linear transformations are chained together. In computer graphics, a 3D object's position is transformed by successive matrices for scaling, rotation, and translation (via homogeneous coordinates), and the entire pipeline is a single matrix product precisely because applying transformations in sequence is composition. In quantum mechanics, sequential measurements or time evolutions correspond to products of operator matrices, and the physical fact that order of operations matters (non-commuting observables) is the same phenomenon as $AB \ne BA$ above, now carrying deep physical content (the uncertainty principle traces back to non-commutativity of position and momentum operators). In cryptography and coding theory, linear codes and certain cipher constructions compose linear transformations over finite fields, again multiplying matrices to represent "encode, then transmit, then decode" pipelines. In statistics and machine learning, a neural network's layers are (affine or linear) maps, and the composite map of a multi-layer network is captured, layer by layer, as a product of weight matrices, with the non-commutativity of layer order being exactly why architecture (which transformation comes first) matters. In numerical analysis, factorizations like $LU$ or $QR$ decompose one matrix as a product of simpler ones, implicitly asserting that a complicated linear map is literally a composition of easily-understood ones — an idea that leads directly to Elementary Matrices and Row Operations and to criteria for Invertibility of Linear Maps.

Ask the tutor: Can you show me why $(AB)^{-1} = B^{-1}A^{-1}$ follows directly from viewing $AB$ as a composition of maps?

Think of a linear map as a machine that takes a vector, reads off its coordinates, and outputs new coordinates via a fixed table of instructions. If $T$ is such a machine turning $U$-coordinates into $V$-coordinates, and $S$ is a machine turning $V$-coordinates into $W$-coordinates, then bolting $S$ onto the output of $T$ builds a new machine, $S \circ T$, turning $U$-coordinates directly into $W$-coordinates. Matrix multiplication is the recipe for building the instruction table of the bolted-together machine directly from the two original tables, without ever computing an intermediate vector by hand. The reason the formula involves a sum over an index $k$ is that a basis vector $a_j$ of $U$ does not land on a single basis vector of $V$ — it lands on a combination $\sum_k A_{kj} b_k$. Each of those $b_k$'s is then pushed forward by $S$ into its own combination of $c_i$'s, and all these contributions to the coefficient of $c_i$ must be added up. The index $k$ ranges over the intermediate basis, which is exactly why the shared dimension $n$ must match: it counts the number of routes a basis vector of $U$ can take to reach $c_i$. ```mermaid ```

Every basis vector $a_j$ of $U$ fans out to all of $V$'s basis vectors under $T$ (with coefficients $A_{kj}$), and each of those fans out again to all of $W$'s basis vectors under $S$ (with coefficients $B_{ik}$). The total coefficient of $c_i$ in $S(T(a_j))$ collects one term for each intermediate route through some $b_k$, giving exactly $\sum_k B_{ik}A_{kj}$. This is the entire content of the theorem below, made rigorous.

Example 1 (a genuinely non-square, non-commuting composition). Let $U = \mathbb{F}^2$, $V = \mathbb{F}^3$, $W = \mathbb{F}^2$, all with standard bases. Let $T: U \to V$ and $S: V \to W$ have matrices

Here $n = 3$ (the shared middle dimension) matches: $A$ has $3$ rows, $B$ has $3$ columns, so $BA$ is defined and lands in $\mathbb{F}^{2\times 2}$. Compute $(BA)_{ij} = \sum_{k=1}^3 B_{ik}A_{kj}$ entrywise:

So

Sanity check via the composition meaning: take $u = (1,0)$, the first standard basis vector of $U$. Then

This matches column $1$ of $BA$, exactly as the theorem predicts: $\mathcal{M}(S\circ T)$'s first column records the coordinates of $(S\circ T)(a_1) = S(T(a_1))$. The computation confirms the entrywise product formula is not a bookkeeping accident but literally is tracking $S(T(a_1))$.

Example 2 ($AB$ vs $BA$ — non-commutativity made concrete). Let $S, T : \mathbb{F}^2 \to \mathbb{F}^2$ have matrices

Compute $BA$ ("rotate, then stretch"):

Now compute $AB$ ("stretch, then rotate"):

Indeed $BA \neq AB$. Trace the vector $e_1 = (1,0)$ through each order to see why, geometrically: under $BA$, $e_1 \mapsto (0,1)$ (rotate $e_1$ to $(0,1)$, then stretching the $x$-axis does nothing to it since its $x$-coordinate is $0$). Under $AB$, $e_1 \mapsto (0,2)$ (stretch $e_1$ to $(2,0)$, then rotating sends $(2,0)$ to $(0,2)$). Stretching before rotating versus after gives different final lengths, because the stretch treats the $x$-axis specially and rotation moves points off that axis. This is the concrete meaning of non-commutativity: composing functions in different orders produces different functions.

Arthur Cayley, working in the mid-1800s, is credited with the first systematic treatment of matrices as objects in their own right, including the definition of matrix multiplication designed exactly to mirror composition of the linear substitutions (what we would now call linear maps) that matrices encode. Cayley's 1858 Memoir on the Theory of Matrices introduced matrix algebra abstractly, proved the Cayley–Hamilton theorem for small cases, and explicitly remarked that matrix multiplication corresponds to compounding linear substitutions — the same insight this article makes rigorous with modern coordinate-vector language.