Permutations and transpositions

I skipped an important detail on the previous page. We calculated determinants of permutation matrices (i.e. matrices that have all rows of the identity matrix, but in a different order) by swapping the rows until we eventually got to $\det(I)=1$, e.g. $$ \begin{align} \det\begin{bmatrix} \red0&\red0&\red1 \\ \blue1&\blue0&\blue0 \\ \green0&\green1&\green0 \end{bmatrix} &= -\det\begin{bmatrix} \blue1&\blue0&\blue0 \\ \red0&\red0&\red1 \\ \green0&\green1&\green0 \end{bmatrix} \\ &= \det\begin{bmatrix} \blue1&\blue0&\blue0 \\ \green0&\green1&\green0 \\ \red0&\red0&\red1 \end{bmatrix} = 1. \end{align} $$ With an even number of swaps, this shows that the determinant of the original matrix is $1$, because the sign in front flips an even number of times. With an odd number of swaps, we get $-1$. But can it possible to do an even or an odd number of swaps? If it is, we must make the determinant undefined, because it can't simultaneously be both $1$ and $-1$.

Counting transpositions

Let's assign the numbers $1,2,\dots,n$ to each row of the $n \times n$ identity matrix, so that with $n=3$ for example, $1$ means $(1,0,0)$, $2$ means $(0,1,0)$ and $3$ means $(0,0,1)$. Now the identity matrix is represented as $123\dots n$, and other permutation matrices are represented as the same numbers but possibly in a different order. The numbers $123\dots n$, but possibly in a different order, are called a permutation.

Any permutation can be turned into $123\dots n$ by swapping the numbers, and now the question becomes whether there exists permutations where this can be done with an even number of swaps (determinant $+1$) and with an odd number of swaps (determinant $-1$).

We say that a transposition (not to be confused with transpose) is a pair of numbers in a permutation where a bigger number is before a smaller one. The numbers don't have to be next to each other. For example, the permutation $1234\dots n$ has no transpositions, and the permutation $1432$ has three transpositions: $43$, $42$ and $32$.

Note that swapping two adjacent numbers (i.e. any two numbers next to each other) of a permutation always adds or removes one transposition, depending on whether the first number is bigger or smaller: $$ \begin{align} 1\green{43}2 & \quad \text{3 transpositions: }\green{43}, 32, 42 \\ 1\red{34}2 & \quad \text{2 transpositions: }32, 42 \end{align} $$

Swapping any two numbers can be done as a combination of several swaps of adjacent numbers. The below animation shows how this works when there are 3 numbers between the numbers being swapped.

The animation consists of 7 swaps: first 3 swaps to bring the swapped numbers next to each other, then one swap to actually swap them, and then 3 more to bring them back to their original places. In general, if there are $k$ unrelated numbers between the numbers you want to swap, you need $k+1+k = 2k+1$ swaps of adjacent elements. Because each swap of adjacent numbers makes the number of transpositions go from even to odd or from odd to even (as it increases or decreases by one), an odd number of swaps of adjacent elements as a whole makes the number of transpositions go from even to odd or from odd to even.

Now consider any permutation. If it has an even number of transpositions, it is impossible to get to $123\dots n$ by doing an odd number of swaps: because each swap toggles between even and odd number of transpositions, the resulting permutation would have an odd number of transpositions, even though $123\dots n$ has zero (an even number) of transpositions. Similarly, if the permutation has an odd number of transpositions, it is impossible to get to $123\dots n$ by doing an even number of swaps.

For determinants of permutation matrices, this means:

When computing the determinant of a permutation matrix, the result does not depend on which swaps are used to get to identity matrix.

This shows that there are no problems with how we defined the determinant. Our definition works for matrices of any size.