# Showing that the product of two permutation matrices results in another permutation matrix [closed]

The idea that the product of two permutation matrices gives another permutation matrix makes sense to me, since we know that they only have one entry of 1 in each row and column (and 0s everywhere else). However, how would we show/prove this mathematically?

• I think the simplest way is to note that the composition of two permutations is always a permutation. Matrix multiplication is just composition of the matrices when viewed as linear functions so the product must be a permutation. A more concrete way is to notice that multiplying an arbitrary matrix on the right by a permutation matrix yields original matrix except with columns permuted. Permuting the columns of permutation matrix still yields a permutation matrix. Oct 20 at 16:11

For permutation matrices $$P_{ij},Q_{ij}$$ just compute their product:
$$R_{ij}=\sum_kP_{ik}Q_{kj}.$$
It should be obvious from the properties of permutation matrices that $$R_{ij}\in\{0,1\}$$ since each matrix has exactly one 1 in each row/column. Next, sum over $$i$$. Notice that $$Q_{kj}$$ is equal to 1 in exactly one spot, say $$Q_{nj}$$ and notice that $$P_{in}$$ must be 1 for some unique $$i$$. This will imply that $$R_{ij}$$ has exactly one 1 in each row. Repeat the argument for columns.