beavers Who are Busy

When you start on learning discrete mathematics, one of the first really interesting ideas you’ll come across (well maybe it won’t be that close to being the first, but you get the point…) is that of even and odd parity permutations.

If you haven’t heard of permutations before, they’re basically just ways of scrambling numbers in a line. For example, I could permute the sequence “1 2 3 4 5” by switching the 4 and the 5 to get “1 2 3 5 4”.

An odd parity permutation is one that can be reached with an odd number of these swaps from the original sequence (“original” here just refers to the increasing one starting from 1). An even parity permutation is one that can be reached in an even number of swaps.

At first this definition might seem a little weird; couldn’t an even permutation also be an odd permutation, why should they be mutually exclusive?

Well it takes a little bit of work to prove it, but even permutations are even no matter how you look at them, and the same goes for odds. I’ll show you a really nice way of proving this fact in this post.

I’ll preface this by saying that this method is historically a little sketchy, since permutations were a thing way before determinants were, but they make for a really nice proof, so I’ll let it slide today (and I hope you will too).

The basic idea is to embed the permutation as a simple matrix. The way we’ll do this is by treating the matrix almost like a coordinate grid, where position in the permutation is the horizontal axis and numerical value is the vertical axis. For every (number, position) pair in our sequence, we find the correspondent y-axis coordinate, and x-axis coordinate and place a “1”.

For example the permutation “1 2 3 5 4” would be embedded like this:

We assign to any given permutation the value of the determinant of its matrix.

Since whenever we perform a swap, we’re basically swapping the columns of the matrix, and since swapping matrix columns results in negation of the determinant, the sign of the permutation’s determinant swaps with every swap of permutation values.

Since two permutations can only be equal if their determinants are equal, this completes the proof that it takes an even number of moves to get from an even to an even or an odd to and odd, while it takes an odd number of moves to get from an odd to an even or an even to an odd.

I think this proof is really a lesson in the ways things that seem totally unrelated can often connect in the most beautiful ways in math. It often takes just a little leap of faith to find a nugget of gold.