Why is the permutation matrix called so? Any combinatorial meaning?

Question

My question is very simple but I cannot really have it answer. Why the permutation matrix is called permutation matrix?? Is there any combinatorial meaning with the permutation matrix? (As I know, a permutation matrix have one and all zero for all entries of every rows and columns)

Answer 1

Try writing down such a matrix in a small dimension, and see how it acts on the standard basis. Say

$$A = \left(\begin{array}{rrr} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array}\right).$$

Then

$$\left(\begin{array}{rrr} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array}\right) \left(\begin{array}{c} 1 \\ 0\\ 0 \end{array}\right) =\left(\begin{array}{c} 0 \\ 0\\ 1 \end{array}\right), $$ $$\left(\begin{array}{rrr} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array}\right) \left(\begin{array}{c} 0 \\ 1\\ 0 \end{array}\right) =\left(\begin{array}{c} 1 \\ 0\\ 0 \end{array}\right), $$

$$\left(\begin{array}{rrr} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{array}\right) \left(\begin{array}{c} 0 \\ 0\\ 1 \end{array}\right) =\left(\begin{array}{c} 0 \\ 1\\ 0 \end{array}\right), $$

So you see, they are called "permutation matrices" because they permute the standard basis. In fact, this example I wrote down is the standard representation of $S_3$ (the permutation group on $3$ letters) in $GL_3$ (the group of invertible $3\times3$ matrices).

Once you know they permute the standard basis, it follows that multiplying a matrix on the left by a permutation matrix will permute the rows, and multiplying on the right by a permutation matrix will permute the columns.

Answer 2

If you multiply any matrix at the right/left by a permutation matrix, you simply permute the rows and respectively columns of that matrix by the permutation $\sigma$, respectively by $\sigma^{-1}$.