[latexpage]

A $n \times n$ matrix $P$ is a permutation matrix if it is obtained by permuting the rows or columns of an $n \times n$ identity matrix according to some permutation of the numbers $1$ to $n$. Permutation matrices are orthogonal (hence, their inverse is their transpose: $P^{-1}=P^{T}$) and satisfy $P^2 = P$.

For example, the matrix

\[P = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.\]

is obtained by exchanging the columns $2$ and $3$, and $4$ and $5$, of the $6 \times 6$ identity matrix.

A permutation matrix allows to exchange rows or columns of another via the matrix-matrix product. For example, if we take any $5 \times 6$ matrix $A$, then $AP$ (with $P$ defined above) is the matrix $A$ with columns $2, 3$ and $4, 5$ exchanged.