Showing that the product of two permutation matrices results in another permutation matrix

Question

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?

Answer 1

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.

Answer 2

I'd recommend slowing down and thinking carefully about the definition of matrix multiplication: Multiplying on a matrix the left by a permutation matrix scrambles its rows (why?) and multiplying on the right by a permutation matrix scrambles its columns (why?).

Well, if you scramble the rows of a permutation matrix, it's still a permutation matrix: each row and each column still has exactly one entry that is equal to one, and the rest zero. And if you scramble the columns of a permutation matrix, it's still a permutation matrix, for the same reason. (Think about how you can be sure I'm not lying to you here.)

So the product of two permutation matrices must be a permutation matrix.