Linear Algebra: $n!$ permutation matrices proof, and amount of permutation matrices with $x$ row exchanges from $I$

Question

Can anyone give me an intuitive proof of why there are $n!$ permutation matrices $P$ of dimension $n \times n$? The reason I'm asking this is for my own curiosity, and also because it ties into another question of mine: how does one calculate the amount of permutation matrices with $x$ row exchanges from $I$? For example, if I wanted to know the amount of $5 \times 5$ permutation matrices that have had $2$ row exchanges from $I$, how would I do it? Thanks!

Answer 1

There are $n!$ permutation matrices of an $n \times n$ matrix.

A permutation matrix permutes the rows (or columns, depending which side it's being multiplied on) of a matrix. Let's label the rows $1, 2, \dots, n$. We are now counting the number of permutations of the list $[1, 2, \dots, n ]$. To visualize this, let's start with an "empty list" $[\_, \dots, \_ ]$ and fill it in as we go. There are $n$ ways to fill the first spot. There are $n - 1$ ways to fill the second spot. This pattern continues until there is $1$ way to fill the last spot. Thus there are $n \cdot (n-1) \cdot (n-2 ) \cdots 1 = n!$ total permutations.

Permutations with a fixed number of row exchanges

This question is more complicated—you're going to want to look into cycle notation. This is a succinct way to represent permutations. Again, let's say the objects $1, 2, \dots, n$ are filling the slots $[\_, \dots, \_]$ in some order. Then $(ab)$ represents the permutation which swaps the $a$th slot with the $b$th slot. For example, applying $(12)$ to the permutation $[3, 2, 1]$ gives $[2, 3, 1]$.

If you want to do two swaps, you can multiply these permutations. Applying $(12)(34)$ to the permutation $[4, 2, 1, 3]$ gives $[2, 4, 3, 1]$, because we swapped the $1$st and $2$nd slot, then the $3$rd and $4$th slot.

Things get a little more complicated when permutations you multiply share elements. For example, consider the permutation $(12)(23)$ and the list $[4,5,6]$. If I apply $(12)$ and then $(23)$, then I get $[5, 6, 4]$. But if I apply $(23)$ and then $(12)$, I get $[6, 4, 5]$. Just like how matrix multiplication is not commutative, multiplying permutations is not commutative.

So you have to fix a convention. Let's say that we multiply permutations from right to left. This means that when applying $(12)(23)$ to $[4,5,6]$, we apply the rightmost permutation $(23)$ first.

Now, every permutation which is obtained by two row exchanges can be written as $(ab)(cd)$, with $a,b,c,d$ possibly not all distinct. To count the total number of such permutations, you'll need to do a bit of casework based on which of $a,b,c,d$ are equal. Specifically, without loss of generality, you can look at $3$ cases:

1. $a,b,c,d$ are distinct.
2. $a = c$ and $b \neq d$
3. $a = c$ and $b = d$

You can count each case using binomial coefficients.