Matrix multiplication

Turn then shear, or shear then turn: the same two moves in two orders. Watch the two pictures end up different.

One map, then another

In A matrix moves the plane a matrix was the table of where the two unit arrows $\mathbf{e}_1=(1,0)$ and $\mathbf{e}_2=(0,1)$ land: the first column says where $\mathbf{e}_1$ goes, the second where $\mathbf{e}_2$ goes. This page uses two such maps.

The first is a quarter turn anticlockwise. It sends $\mathbf{e}_1$ to $(0,1)$ and $\mathbf{e}_2$ to $(-1,0)$:

The second is a shear. It slides every point sideways by its height, so $(x,y)$ goes to $(x+y,\,y)$. It leaves $\mathbf{e}_1$ where it is and pushes $\mathbf{e}_2$ over to $(1,1)$:

Now do one, then the other. Turn first, then shear. Where do the unit arrows end up? Follow each one through both maps:

• $\mathbf{e}_1$ turns to $(0,1)$, and the shear pushes that to $(0+1,\,1)=(1,1)$.
• $\mathbf{e}_2$ turns to $(-1,0)$, and the shear leaves it at $(-1+0,\,0)=(-1,0)$.

Two arrows and their landing places: that is a matrix. The single map “turn, then shear” is

It is the left panel’s end state at the top of the page. This matrix is the product of the two, written $\mathbf{A}_\text{shear}\mathbf{A}_\text{rot}$.

Why the order is written backwards

Look at the order of the names. The turn happens first, but it is written on the right. Here is why. A point $\mathbf{x}$ is turned to $\mathbf{A}_\text{rot}\mathbf{x}$, and then that is sheared:

The first map stands next to $\mathbf{x}$, because it touches $\mathbf{x}$ first. So read a product from right to left: $\mathbf{A}\mathbf{B}$ means “do $\mathbf{B}$, then do $\mathbf{A}$”.

One check remains. Is “one map, then another” always a matrix? It is, because each map keeps the linear rule from A matrix moves the plane. If $\mathbf{B}$ keeps scaling and adding, and so does $\mathbf{A}$, then

So the chain is linear too, and a linear map of the plane is fixed by where it sends the two unit arrows.

The other order

Now shear first, then turn:

• $\mathbf{e}_1$ is not moved by the shear, and the turn sends it to $(0,1)$.
• $\mathbf{e}_2$ is sheared to $(1,1)$, and the turn sends that to $(-1,1)$.

That is not $\begin{bmatrix}1&-1\\1&0\end{bmatrix}$, the matrix of the first order.

Watch the clip again and compare the two end pictures: the same picture, the same two moves, two different results. In general $\mathbf{A}\mathbf{B}\ne\mathbf{B}\mathbf{A}$. Some pairs do agree, such as two turns, but you can’t count on it.

Columns of the product

The same reasoning works for any two matrices. Column $q$ of $\mathbf{B}$, which I call $\mathbf{b}_q$, is where $\mathbf{B}$ sends the unit arrow $\mathbf{e}_q$. Then $\mathbf{A}$ sends it on to $\mathbf{A}\mathbf{b}_q$. So:

To multiply two matrices, multiply the first by each column of the second, one at a time. Each of those is a matrix times a vector, which you already know how to do.

Watch where the two arrows land. Each one is a column of $\mathbf{B}$ pushed through $\mathbf{A}$, and nothing else.

Shapes that fit

Matrices need not be square. Say $\mathbf{A}$ is $m\times n$: $m$ rows and $n$ columns, so it takes $n$ numbers in. Each column of $\mathbf{B}$ goes into $\mathbf{A}$, so each column of $\mathbf{B}$ must have $n$ numbers: $\mathbf{B}$ has $n$ rows. Let $\mathbf{B}$ have $K$ columns; on this page $K$ is only that count. Then

The two inside numbers must match, and the two outside numbers give the shape of the answer. A $2\times3$ matrix can’t multiply another $2\times3$: it takes 3 numbers in, and the columns of the second have only 2.

Row times column

Each column $\mathbf{A}\mathbf{b}_q$ is a matrix times a vector, and A matrix moves the plane computed that one row at a time: entry $p$ is row $p$ of $\mathbf{A}$ dotted with the vector. So one entry of the product is one row of $\mathbf{A}$ dotted with one column of $\mathbf{B}$:

Here $a_{pk}$ is the entry of $\mathbf{A}$ in row $p$ and column $k$, counted from 1, and $k$ runs along the row of $\mathbf{A}$ and down the column of $\mathbf{B}$ together.

Try it on $\mathbf{A}=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ and $\mathbf{B}=\begin{bmatrix}0&1\\1&0\end{bmatrix}$:

The answer is $\mathbf{A}$ with its two columns swapped. That makes sense from the columns picture: $\mathbf{B}$ sends $\mathbf{e}_1$ to $\mathbf{e}_2$ and $\mathbf{e}_2$ to $\mathbf{e}_1$, so the product’s first column is $\mathbf{A}$‘s second.

Column times row

There is a third way to get the same numbers. Take column $k$ of $\mathbf{A}$ and row $k$ of $\mathbf{B}$. A column of $m$ numbers times a row of $K$ numbers makes a full $m\times K$ table: the entry in row $p$ and column $q$ is $a_{pk}b_{kq}$. Add these tables for $k=1$ to $n$, and each entry collects $a_{p1}b_{1q}+\dots+a_{pn}b_{nq}$, the same sum as before.

For the same $\mathbf{A}$ and $\mathbf{B}$:

Three ways, one answer. Columns tell you what the product does to the unit arrows. Rows times columns are the quickest by hand. Columns times rows show a product as a sum of simple pieces, a view that comes back often in linear algebra.

The rules

Grouping does not matter. $(\mathbf{A}\mathbf{B})\mathbf{C}=\mathbf{A}(\mathbf{B}\mathbf{C})$. Both sides mean “do $\mathbf{C}$, then $\mathbf{B}$, then $\mathbf{A}$”, so they are the same chain of maps, and you may drop the brackets: $\mathbf{A}\mathbf{B}\mathbf{C}$.

Order does matter. $\mathbf{A}\mathbf{B}$ and $\mathbf{B}\mathbf{A}$ are usually different, as the two panels showed. For the $\mathbf{A}$ and $\mathbf{B}$ above, $\mathbf{B}\mathbf{A}=\begin{bmatrix}3&4\\1&2\end{bmatrix}$: on the left, $\mathbf{B}$ swaps the rows of $\mathbf{A}$ instead of the columns.

The identity changes nothing. The map that leaves both unit arrows where they are is the identity matrix,

Doing nothing before or after a map leaves the map as it was. For $n$ numbers, $\mathbf{I}$ is $n\times n$ with 1s down the diagonal and 0s elsewhere.

Blocks multiply like entries. Cut $\mathbf{A}$ into a left and a right block of columns, $\mathbf{A}_1$ and $\mathbf{A}_2$, and cut $\mathbf{B}$ into a top and a bottom block of rows, $\mathbf{B}_1$ and $\mathbf{B}_2$, at the same place. Then

the column-times-row rule with blocks in place of single columns and rows. The order inside each block product stays as it was.

Worked example

1. The two orders. Rotate, then shear:

Entry by entry: row 1 times column 1 is $1\cdot0+1\cdot1=1$, row 1 times column 2 is $1\cdot(-1)+1\cdot0=-1$, and row 2 gives $0\cdot0+1\cdot1=1$ and $0\cdot(-1)+1\cdot0=0$.

Check with the arrows: $\mathbf{e}_1\to(0,1)\to(1,1)$ and $\mathbf{e}_2\to(-1,0)\to(-1,0)$, the two columns. Shear, then rotate: $\mathbf{A}_\text{rot}\mathbf{A}_\text{shear}=\begin{bmatrix}0&-1\\1&1\end{bmatrix}$, with $\mathbf{e}_1\to(1,0)\to(0,1)$ and $\mathbf{e}_2\to(1,1)\to(-1,1)$. Follow the point $(1,2)$ to see the difference: the first order takes it to $(-1,1)$, the second to $(-2,3)$.

2. Swapping columns and rows. With $\mathbf{A}=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ and $\mathbf{B}=\begin{bmatrix}0&1\\1&0\end{bmatrix}$, $\mathbf{A}\mathbf{B}=\begin{bmatrix}2&1\\4&3\end{bmatrix}$ swaps the columns of $\mathbf{A}$ and $\mathbf{B}\mathbf{A}=\begin{bmatrix}3&4\\1&2\end{bmatrix}$ swaps its rows. The column-times-row sum above gives the same $\mathbf{A}\mathbf{B}$.

3. Shapes. Now take a new $2\times3$ matrix $\mathbf{A}$ and a new $3\times2$ matrix $\mathbf{B}$:

$\mathbf{A}\mathbf{B}$ is $2\times2$: the first entry is $1\cdot1+0\cdot0+2\cdot1=3$, and in all

$\mathbf{B}\mathbf{A}$ is $3\times3$. Here the two orders don’t even have the same shape.

Predict before you compute: a $4\times3$ matrix times a $3\times5$ matrix gives what shape? $4\times5$: 20 entries, each one row of 3 numbers dotted with one column of 3.

Where you’ll meet this

Graphics. A drawing program that scales a shape, turns it and tilts it multiplies the three matrices once and applies the single product to every corner of the shape. One product, thousands of corners. To move shapes too, graphics programs add one extra coordinate so that a move becomes a matrix as well.

Layers of a neural network. Two layers that take 784 numbers to 128 and then 128 to 10 hold a $128\times784$ and a $10\times128$ matrix: 101,632 numbers. If nothing happened between the layers, their product would be a single $10\times784$ matrix of 7,840 numbers doing the same job. Real networks put a step that is not linear between the layers, and that step is what stops the two from merging into one.

Filters in a chain. In signal processing a filter is a matrix too, so two filters in a chain are a product of two matrices.

Reference card