Permutation Matrices

Why

Can permuting the rows or columns of a matrix be represented by matrix multiplication?

Definition

Let $\sigma : \upto{n} \to \upto{n}$ be a permutation of $n$. The permutation matrix of $\sigma $ is the matrix $P$ defined by $P_{ij} = 1$ if $\sigma (i) = j$ and 0 otherwise. This is sometimes called the column representation (in contrast to the row representation, in which $P_{ij} = 1$ if $\sigma (j) = i$.

Let $A \in \R ^{n \times n}$. Then pre-multipying $A$ by $P$ permutes the rows of $A$. In other words $PA$ has the same rows as $A$ but permuted according to $\sigma $. Similarly, post-multiplying by $P$ permutes the columns of $A$. In other words, $AP$ has the same columns as $A$ but permuted according to $\sigma $. Clearly, we can also speak of permuting the components of a vector.

Composition

Let $\pi , \sigma \in S_n$ with corresponding permutation matrices $P_\sigma $ and $P_\pi $. Then $P_{\pi }P_{\sigma }A$ has the same rows as $A$ but permuted by $\pi \sigma $. Likewise, $AP_{\pi }P_{\sigma }$ has the same columns as $A$ but permuted by $\pi \sigma $. Clearly, the identity permutation on $\upto{n}$ is the identity $I \in \R ^{n \times n}$.

Inverses

It is clear from the definition that $P_{\sigma }^{-1} = P_{\sigma ^{-1}}$ and so if $P$ is a permutation matrix then $P^{-1}$ is $P^\top $.