0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 20 at 16:11
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.