Matrices and their product

Two transformations applied one after the other are again a transformation, so it has a matrix of its own, and working out what that matrix is defines multiplication.

The previous lesson established the fact this one rests on: a linear map is determined by where it sends the basis vectors, and the matrix of the map is the list of those images, written as columns. So $A = [(3, 1), (- 1, 2)]$ sends $e_{1}$ to $(3, 1)$ and $e_{2}$ to $(- 1, 2)$ , and $A x$ is the combination of the columns weighted by the components of $x$ .

Deriving the product

Let $A$ and $B$ be matrices, and consider doing $B$ first and then $A$ . The composite map sends $x$ to $A (B x)$ , and it is linear, since a composition of maps that each preserve combinations preserves combinations. Being linear, it has a matrix, which is written $A B$ and read right to left: $B$ acts first.

Finding that matrix requires no new idea, only the rule that a matrix is the list of the images of the basis vectors. Column $j$ of $A B$ is the image of $e_{j}$ under the composite, which is $A (B e_{j})$ . But $B e_{j}$ is column $j$ of $B$ . So:

Column $j$ of $A B$ is $A$ applied to column $j$ of $B$ .

That is the definition of matrix multiplication, and every other description of it is this one rearranged. Since $A$ applied to a vector takes the dot product of each row of $A$ with that vector, the entry in row $i$ and column $j$ of $A B$ is row $i$ of $A$ dotted with column $j$ of $B$ , which is the rule usually taught first and which looks arbitrary until it is seen to come from composition.

Take $A = [(2, 1), (- 1, 3)]$ and $B = [(1, 4), (2, 0)]$ . Column one of $A B$ is $A (1, 4) = 1 (2, 1) + 4 (- 1, 3) = (- 2, 13)$ . Column two is $A (2, 0) = 2 (2, 1) = (4, 2)$ . So $A B = [(- 2, 13), (4, 2)]$ . Checking one entry by the row rule: row one of $A$ is $(2, - 1)$ , and dotted with column one of $B$ , which is $(1, 4)$ , it gives $2 - 4 = - 2$ , matching.

The shape rule now explains itself. To form $A B$ , the vectors that $B$ produces must be vectors that $A$ can eat, so the number of rows of $B$ must equal the number of columns of $A$ . An $m$ by $n$ matrix times an $n$ by $p$ matrix gives an $m$ by $p$ matrix, and any other combination is not a failure of arithmetic but a request to feed a map something it does not take.

Example. With $A = [(2, 1), (- 1, 3)]$ and $B = [(1, 4), (2, 0)]$ , compute $B A$ .

Column one of $B A$ is $B$ applied to column one of $A$ , that is $B (2, 1) = 2 (1, 4) + 1 (2, 0) = (4, 8)$ . Column two is $B (- 1, 3) = - 1 (1, 4) + 3 (2, 0) = (5, - 4)$ . So $B A = [(4, 8), (5, - 4)]$ , which is nothing like $A B = [(- 2, 13), (4, 2)]$ .

Now you. With $C = [(1, 2), (0, 1)]$ and $D = [(3, 0), (1, 1)]$ , compute $C D$ .

Answer

Column one is $C (3, 0) = 3 (1, 2) + 0 (0, 1) = (3, 6)$ . Column two is $C (1, 1) = 1 (1, 2) + 1 (0, 1) = (1, 3)$ . So $C D = [(3, 6), (1, 3)]$ .

Order matters

Multiplication of numbers is commutative and multiplication of matrices is not, and this is a feature rather than a defect: composing operations in the other order genuinely gives a different result, and the algebra had better say so.

Take $R$ , a quarter turn anticlockwise, with matrix $[(0, 1), (- 1, 0)]$ , and $S$ , the shear $[(1, 0), (1, 1)]$ . Then $R S$ means shear first, and its columns are $R (1, 0) = (0, 1)$ and $R (1, 1) = (- 1, 1)$ , so $R S = [(0, 1), (- 1, 1)]$ . Meanwhile $S R$ means turn first, with columns $S (0, 1) = (1, 1)$ and $S (- 1, 0) = (- 1, 0)$ , giving $S R = [(1, 1), (- 1, 0)]$ .

The two differ, and the difference is visible in a single vector: $R S$ sends $(1, 0)$ to $(0, 1)$ , while $S R$ sends it to $(1, 1)$ . Anyone can reproduce this with a book. Rotate it a quarter turn about the vertical axis and then a quarter turn about the horizontal one, then start again and do the two in the opposite order: the book ends up in two different orientations. Three-dimensional rotations do not commute, and the matrices that represent them must fail to commute in exactly the same pattern.

What does survive is associativity: $(A B) C = A (B C)$ , always. No calculation is needed, because both sides describe the map "do $C$ , then $B$ , then $A$ ", and function composition is associative by its nature. Proving it from the entry formula takes half a page of index manipulation and produces less understanding. Distributivity, $A (B + C) = A B + A C$ , follows from linearity in the same way, addition of matrices being entry by entry.

The identity $I = [(1, 0), (0, 1)]$ satisfies $A I = I A = A$ , since it does nothing before or after anything else. And powers make sense for square matrices: $A^{2} = A A$ is the map applied twice. Shearing by $k$ and shearing by $k$ again gives $[(1, 0), (2 k, 1)]$ , a shear by $2 k$ , which is the algebra confirming that two equal slides compose into a double slide.

What composition proves

Because the product means composition, computing a product sometimes proves a theorem in trigonometry for free.

Rotating by $β$ and then by $α$ must be the same as rotating by $α + β$ . Write the two matrices out, using the rotation matrix derived in the previous lesson. Column one of $R_{α} R_{β}$ is $R_{α}$ applied to $(\cos β, \sin β)$ , which is

\cos β (\cos α, \sin α) + \sin β (- \sin α, \cos α)

that is, $(\cos α \cos β - \sin α \sin β, \sin α \cos β + \cos α \sin β)$ . But that column must be the first column of $R_{α + β}$ , namely $(\cos (α + β), \sin (α + β))$ . Comparing components gives both angle addition formulas at once. Anyone who has forgotten which sign goes where can rebuild them from the geometry in a minute.

Example. With $R$ the quarter turn and $S$ the shear above, compute $R^{2}$ and identify it.

Column one is $R (0, 1) = (- 1, 0)$ and column two is $R (- 1, 0) = (0, - 1)$ , so $R^{2} = [(- 1, 0), (0, - 1)]$ , which is $- I$ . Two quarter turns make a half turn, and a half turn negates every vector.

Now you. Compute $S^{3}$ for the shear $S = [(1, 0), (1, 1)]$ .

Answer

$S^{2} = [(1, 0), (2, 1)]$ from the doubling rule above, and $S^{3} = S^{2} S$ has columns $S^{2} (1, 0) = (1, 0)$ and $S^{2} (1, 1) = 1 (1, 0) + 1 (2, 1) = (3, 1)$ . So $S^{3} = [(1, 0), (3, 1)]$ , a shear by $3$ , as three equal slides should be.

Zero products and other surprises

The algebra of matrices departs from the algebra of numbers in a second way, which is worth meeting deliberately rather than discovering in the middle of a proof.

Let $P = [(1, 0), (0, 0)]$ , the projection onto the horizontal axis, and $Q = [(0, 0), (0, 1)]$ , the projection onto the vertical. Neither is the zero matrix. Their product is: column one of $P Q$ is $P (0, 0) = 0$ , and column two is $P (0, 1) = 0$ , so $P Q$ is the zero matrix, and so is $Q P$ . Geometrically this is obvious once seen. $Q$ flattens everything onto the vertical axis, and $P$ then flattens the vertical axis onto the origin, so the composite destroys everything.

The consequence is that $A B = 0$ does not imply that $A$ or $B$ is zero, and therefore that cancellation is illegal: from $A B = A C$ you may not conclude $B = C$ . The offending matrices are exactly those that collapse something, which the lesson on determinants identifies precisely.

A second surprise: $P$ satisfies $P^{2} = P$ , since projecting twice is the same as projecting once. Among numbers only $0$ and $1$ do that, and among matrices there are infinitely many such idempotents, one for every projection.

Transpose

The transpose $A^{T}$ swaps rows and columns, so the columns of $A$ become the rows of $A^{T}$ . If $A = [(2, 1), (- 1, 3)]$ , its rows are $(2, - 1)$ and $(1, 3)$ , so $A^{T} = [(2, - 1), (1, 3)]$ . Transposing an $m$ by $n$ matrix gives an $n$ by $m$ one, and transposing twice returns the original.

Two facts about it are used constantly. First, the dot product is a matrix product in disguise: $a \cdot b = a^{T} b$ , a one by $n$ matrix times an $n$ by one matrix, giving a single number. Second, the transpose reverses products, $(A B)^{T} = B^{T} A^{T}$ . The reason is visible through the dot product: for all vectors, $(A B x) \cdot y = (B x) \cdot (A^{T} y) = x \cdot (B^{T} A^{T} y)$ , and the matrix that behaves this way on every pair of vectors is unique. A matrix with $A = A^{T}$ is symmetric, which requires it to be square and which turns out to be the best-behaved case in the whole subject, as the final lesson shows.

Example. Verify $(A B)^{T} = B^{T} A^{T}$ for $A = [(2, 1), (- 1, 3)]$ and $B = [(1, 4), (2, 0)]$ .

$A B = [(- 2, 13), (4, 2)]$ from above, whose rows are $(- 2, 4)$ and $(13, 2)$ , so $(A B)^{T} = [(- 2, 4), (13, 2)]$ . Now $B^{T} = [(1, 2), (4, 0)]$ and $A^{T} = [(2, - 1), (1, 3)]$ , and $B^{T} A^{T}$ has column one $B^{T} (2, - 1) = 2 (1, 2) - 1 (4, 0) = (- 2, 4)$ and column two $B^{T} (1, 3) = 1 (1, 2) + 3 (4, 0) = (13, 2)$ . The two agree.

Now you. Is the product of two symmetric matrices always symmetric?

Answer

No. $(A B)^{T} = B^{T} A^{T} = B A$ when both are symmetric, and $B A$ equals $A B$ only if the two commute. For a concrete failure take $A = [(1, 0), (0, 0)]$ and $B = [(0, 1), (1, 0)]$ , both symmetric: $A B$ has columns $A (0, 1) = (0, 0)$ and $A (1, 0) = (1, 0)$ , so $A B = [(0, 0), (1, 0)]$ , whose transpose is $[(0, 1), (0, 0)]$ , a different matrix.

What it costs

Multiplying two $n$ by $n$ matrices by the definition takes $n$ multiplications per entry and there are $n^{2}$ entries, so $n^{3}$ multiplications in total. For $n = 1000$ that is $10^{9}$ operations, about a second at a billion per second, and for $n = 10000$ it is $10^{12}$ , which is why the size of the matrices in a machine learning model is a budget rather than a detail.

The exponent three is not forced. In 1969 Volker Strassen found a way to multiply two by two blocks using seven multiplications instead of eight, at the cost of extra additions, and applying it recursively gives an exponent of $\log_{2} 7 = 2.807$ . At $n = 10000$ that is $1.7 \times 10^{11}$ instead of $10^{12}$ , a real saving, though the constants and the numerical stability are worse and library implementations only switch to it for large matrices. Later work has pushed the exponent below $2.372$ , but those algorithms have constants so large that no practical matrix is big enough to benefit, and nobody knows the true minimum. The obvious lower bound is $n^{2}$ , since every entry must at least be read.

Honest limits

Matrix multiplication is associative and distributive but not commutative, and there is no division. The natural question is whether a given matrix can be undone at all, and the answer is sometimes no, as the projection above shows: once a vector has been flattened onto the horizontal axis, no transformation can recover which height it came from.

There is also a warning about notation. Because $A B$ means " $B$ first", chains of matrices read backwards relative to the order the operations happen, and this is a permanent source of error when translating a geometric description into a product. Some fields, including parts of computer graphics, avoid it by writing vectors as rows on the left instead, so that $x A B$ means $A$ first. Both conventions are in use, they produce transposed matrices, and mixing them silently gives wrong answers.

The next lesson takes up the undoing question. It turns out that a single number computed from the entries decides whether a square matrix can be inverted, and that the number has a plain geometric meaning: it is how much the transformation multiplies area.