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)
Why is the permutation matrix called so? Any combinatorial meaning?
2 Answers
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.
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}$.