Matrix Multiplication

The rule, and why it exists

Before I state the rule, I need you to understand where it comes from — because without the "why," you're just memorizing a mechanical procedure, and that is a waste of both our time. We built functions in the Sets stratum. Matrices are functions on $\mathbb{R}^n$ (full story next lesson). When you compose two functions $g \circ f$, you want a single object that represents "apply $f$ first, then $g$." For matrices, that single object is the product $AB$ — and the requirement that $(AB)\vec{v} = A(B\vec{v})$ for every vector $\vec{v}$ is what forces the multiplication rule. The rule is not arbitrary. It is the only rule consistent with composition. Remember when the Sets stratum showed that composition is almost never commutative? We're about to see that explode spectacularly, and it'll be fucking glorious.

The product rule: For $A$ ($m \times n$) and $B$ ($n \times p$), the product $AB$ is the $m \times p$ matrix whose entry in row $i$, column $j$ is the dot product of row $i$ of $A$ with column $j$ of $B$:

$(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj} = (\text{row } i \text{ of } A) \cdot (\text{col } j \text{ of } B)$

Every entry of $AB$ is a dot product. This is not coincidental — it's the algebraic trace of the composition requirement.

Dimension compatibility: the handshake requirement

For $AB$ to exist, the inner dimensions must match: $A$ is $m \times n$, $B$ must be $n \times p$ for some $p$. The result is $m \times p$.

$(\underbrace{m \times n}_{A})(\underbrace{n \times p}_{B}) = (\underbrace{m \times p}_{AB})$

The inner $n$'s must agree — they "cancel". Think of it as a handshake: the number of columns in the left matrix must equal the number of rows in the right matrix, or they refuse to shake hands and the product is undefined.

A concrete product

Let $A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ and $B = \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix}$, both $2\times 2$.

$(AB)_{11} = (1)(5) + (2)(7) = 5 + 14 = 19$ $(AB)_{12} = (1)(6) + (2)(8) = 6 + 16 = 22$ $(AB)_{21} = (3)(5) + (4)(7) = 15 + 28 = 43$ $(AB)_{22} = (3)(6) + (4)(8) = 18 + 32 = 50$

$AB = \begin{pmatrix} 19 & 22 \\ 43 & 50 \end{pmatrix}$

Each entry required a dot product: row of the left matrix against column of the right. Every. Single. Entry.

$AB \ne BA$ in general

Now watch this. Using the same matrices:

$(BA)_{11} = (5)(1) + (6)(3) = 5 + 18 = 23$ $(BA)_{12} = (5)(2) + (6)(4) = 10 + 24 = 34$ $(BA)_{21} = (7)(1) + (8)(3) = 7 + 24 = 31$ $(BA)_{22} = (7)(2) + (8)(4) = 14 + 32 = 46$

$BA = \begin{pmatrix} 23 & 34 \\ 31 & 46 \end{pmatrix} \ne AB = \begin{pmatrix} 19 & 22 \\ 43 & 50 \end{pmatrix}$

Matrix multiplication is not commutative. This should not be surprising — you already knew from the Sets stratum that composition of functions is not commutative. "Put on socks then shoes" and "put on shoes then socks" are not the same sequence. $AB$ is "apply $B$ first, then $A$". $BA$ is "apply $A$ first, then $B$". Different order, different result. The non-commutativity of matrix multiplication is not a bug, it is not a quirk, it is not something to be apologized for. It is the direct mathematical signature of the non-commutativity of function composition, made concrete and inescapable. Every time a student writes $AB = BA$ without checking, somewhere in this lab a beaker cracks.

The matrix-vector product: columns are key

A special and vital reading of matrix multiplication: $A\vec{x}$ for a matrix $A$ ($m \times n$) and a column vector $\vec{x}$ ($n \times 1$) is a matrix product yielding an $m \times 1$ vector.

$A\vec{x} = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} a_{11} x_1 + a_{12} x_2 \\ a_{21} x_1 + a_{22} x_2 \end{pmatrix}$

But here's the reading you should burn into your memory: if $\vec{c}_1, \vec{c}_2$ are the columns of $A$, then

$A\vec{x} = x_1 \vec{c}_1 + x_2 \vec{c}_2$

$A\vec{x}$ is a linear combination of $A$'s columns, with the entries of $\vec{x}$ as the coefficients. The components of $\vec{x}$ are the mixing weights. This is THE most important reading of matrix-vector multiplication, and we will use it constantly — burn it into your skull: in understanding systems of equations ($A\vec{x} = \vec{b}$ is solvable iff $\vec{b}$ is a combination of $A$'s columns), in understanding transformations (next lesson), and throughout the Vector Spaces stratum. If you take nothing else from this lesson, take that sentence. Write it on your hand. Tattoo it somewhere tasteful.