Transposes and permutations

Flip a matrix across its diagonal and its rows become its columns. Watch a grid of two rows turn into a grid of two columns.

Rows become columns

The flip in the picture at the top of the page is the transpose. The transpose of $\mathbf{A}$, written $\mathbf{A}^\top$, has the rows of $\mathbf{A}$ as its columns:

The entry in row $p$ and column $q$ of $\mathbf{A}^\top$ is the entry in row $q$ and column $p$ of $\mathbf{A}$:

So an $m\times n$ matrix has an $n\times m$ transpose. The numbers on the diagonal, where $p=q$, stay where they are. Transpose twice and you are back where you started.

A vector is a column, so its transpose is a row. That gives a short way to write the dot product of Length and the dot product: a row times a column is one number, the sum of the matching products.

The product rule reverses

What is the transpose of a product? Take the matrices of Matrix multiplication, $\mathbf{A}=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ and $\mathbf{B}=\begin{bmatrix}0&1\\1&0\end{bmatrix}$. Their product is $\mathbf{A}\mathbf{B}=\begin{bmatrix}2&1\\4&3\end{bmatrix}$, so

The order reverses, as it did for inverses in The inverse matrix:

Here is why. Entry $(p,q)$ of $(\mathbf{A}\mathbf{B})^\top$ is entry $(q,p)$ of $\mathbf{A}\mathbf{B}$: row $q$ of $\mathbf{A}$ times column $p$ of $\mathbf{B}$. Row $q$ of $\mathbf{A}$ is column $q$ of $\mathbf{A}^\top$, and column $p$ of $\mathbf{B}$ is row $p$ of $\mathbf{B}^\top$. So it is row $p$ of $\mathbf{B}^\top$ times column $q$ of $\mathbf{A}^\top$, which is entry $(p,q)$ of $\mathbf{B}^\top\mathbf{A}^\top$. The shapes agree too: if $\mathbf{A}$ is $2\times3$ and $\mathbf{B}$ is $3\times4$, then $\mathbf{A}\mathbf{B}$ is $2\times4$, and both $(\mathbf{A}\mathbf{B})^\top$ and $\mathbf{B}^\top\mathbf{A}^\top$ are $4\times2$.

The rule has a useful form with vectors. Since $(\mathbf{A}\mathbf{x})^\top=\mathbf{x}^\top\mathbf{A}^\top$,

A matrix can move from one side of a dot product to the other, if it is transposed on the way. Check it with $\mathbf{A}=\begin{bmatrix}1&2\\3&4\end{bmatrix}$, $\mathbf{x}=(1,0)$ and $\mathbf{y}=(0,1)$: $\mathbf{A}\mathbf{x}=(1,3)$ and $(1,3)\cdot(0,1)=3$; $\mathbf{A}^\top\mathbf{y}=(3,4)$ and $(1,0)\cdot(3,4)=3$.

Symmetric matrices

A matrix that equals its own transpose, $\mathbf{A}^\top=\mathbf{A}$, is symmetric: the numbers on each side of the diagonal mirror each other. $\begin{bmatrix}1&2\\2&5\end{bmatrix}$ is symmetric; $\begin{bmatrix}1&2\\3&1\end{bmatrix}$ is not.

One way to make a symmetric matrix always works. For any $\mathbf{A}$, the product $\mathbf{A}^\top\mathbf{A}$ is symmetric, because by the product rule

That is the second flip in the picture. For the $2\times3$ matrix at the top, the columns are $(1,0)$, $(2,4)$ and $(3,5)$, and entry $(p,q)$ of $\mathbf{A}^\top\mathbf{A}$ is the dot product of column $p$ with column $q$:

Column $p$ dotted with column $q$ is the same as column $q$ dotted with column $p$, which is the symmetry in plain words. The other product, $\mathbf{A}\mathbf{A}^\top=\begin{bmatrix}14&23\\23&41\end{bmatrix}$, holds the dot products of the rows, and it is symmetric too.

Permutations

A permutation matrix reorders the entries of a vector. It is the identity matrix with its rows in a new order. Here is one that moves every entry down one place, and the last entry round to the top:

That is a cyclic shift. Another one reverses the order. I’ll call it $\mathbf{J}$, the exchange matrix:

Watch both act on a short signal of three samples.

How do you undo a permutation? Put every entry back where it came from. That is the transpose:

The reason is short. The columns of $\mathbf{P}$ are the unit vectors $\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3$ in some order. Entry $(p,q)$ of $\mathbf{P}^\top\mathbf{P}$ is column $p$ dotted with column $q$: 1 when they are the same unit vector and 0 when they are not. For the cyclic shift, $\mathbf{P}^\top$ shifts the other way: $(a,b,c)$ goes to $(b,c,a)$. The flip undoes itself: $\mathbf{J}^2=\mathbf{I}$, and $\mathbf{J}^\top=\mathbf{J}$.

There are $3\cdot2\cdot1=6$ permutation matrices of size $3\times3$, one for each order of three things.

Be careful not to stretch the rule. For a permutation the transpose is the inverse, but for most matrices it is not. The matrix $\begin{bmatrix}2&-1\\1&1\end{bmatrix}$ has transpose $\begin{bmatrix}2&1\\-1&1\end{bmatrix}$ and inverse $\tfrac13\begin{bmatrix}1&1\\-1&2\end{bmatrix}$, two different matrices.

Worked example

1. A shape. The transpose of a $2\times3$ matrix is $3\times2$.
2. Two products. For $\mathbf{A}=\begin{bmatrix}1&2&3\\0&4&5\end{bmatrix}$: $\mathbf{A}^\top\mathbf{A}=\begin{bmatrix}1&2&3\\2&20&26\\3&26&34\end{bmatrix}$ and $\mathbf{A}\mathbf{A}^\top=\begin{bmatrix}14&23\\23&41\end{bmatrix}$, both symmetric.
3. The product rule. For $\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})^\top=\mathbf{B}^\top\mathbf{A}^\top=\begin{bmatrix}2&4\\1&3\end{bmatrix}$.
4. Shapes of a product. $\mathbf{A}$ is $2\times3$ and $\mathbf{B}$ is $3\times4$: $(\mathbf{A}\mathbf{B})^\top$ is $4\times2$.
5. A cyclic shift. $\mathbf{P}$ sends $(1,2,3)$ to $(3,1,2)$, and $\mathbf{P}^\top$ sends it back.
6. A flip. $\mathbf{J}$ sends $(1,2,3)$ to $(3,2,1)$, and $\mathbf{J}$ again sends it back.
7. Predict. Is $\mathbf{A}^\top\mathbf{A}$ symmetric for every $\mathbf{A}$, even one that is not square? Yes: its transpose is itself.

Where you’ll meet this

The product $\mathbf{A}^\top\mathbf{A}$ is at the heart of fitting a line or curve to data, on the page Least squares. The same product, built from data with the averages removed, and divided by a count, gives the covariance matrices of statistics.

The FFT reorders its input with a permutation called bit reversal. For 8 samples it takes them in the order 0, 4, 2, 6, 1, 5, 3, 7. A ring buffer, the circular store that real-time audio programs use for the latest samples, is a cyclic shift in action.

Reference card