permutation | Arithmetic variety

A standard part of the theory of permutations is the classification of permutations into “odd” and “even” types. In this post I will develop the theory of odd and even permutations, focusing on adjacent permutations.

Let $X$ be an finite ordered set. A permutation of $X$ is a rearrangement of $X$ ; formally, it is a bijection $\sigma: X \to X$ . For simplicity, we will label the elements of $X$ as $1, 2, \dots n$ , and we will represent a permutation $\sigma$ by the list $\sigma(1)\sigma(2)\dots\sigma(n)$ . Thus if $X$ has five elements, then the permutation that reverses $X$ can be written as $54321$ .

The set of permutations of $X$ naturally forms a group. That is, given two permutations $\sigma_1$ and $\sigma_2$ , we can form their product $\sigma_2 \dot \sigma_1$ (or $\sigma_2\sigma_1$ for short), which is defined by performing $\sigma_1$ first and then $\sigma_2$ , following the convention for composition of functions. For example, the product of the permutations $13425 \cdot 21345$ is $31425$ .

Here are some standard permutations. The identity permutation is the permutation that does nothing. A transposition is a permutation that swaps two elements. If a transposition swaps $a$ and $b$ , we will denote it as $(a \ b)$ . An adjacent transposition is a transposition that swaps two adjacent elements (so it is denoted $(a \ a+1)$ ).

An important property of a permutation is its inversion number. An inversion of a permutation $\sigma$ is a pair $i, j \in \{1, 2, \dots n\}$ where $i < j$ such that $\sigma(i) > \sigma(j)$ . In other words, it is a pair of elements whose relative positions have been switched by the permutation. The inversion number of $\sigma$ is the size of its set of inversions. Thus the inversion number is at most ${n \choose 2}$ (this occurs when the permutation reverses $X$ ). A permutation has inversion number $0$ if and only if it is the identity permutation. Also, a permutation has inversion number $1$ if and only if it is an adjacent transposition.

A permutation is called odd if its inversion number is odd, and even if its inversion number is even. We would like to show that the product of odd and even permutations behaves like addition of odd and even numbers. To show this, we will use the following lemma:

Every permutation is a product of adjacent transpositions.

This can be proved by using insertion sort, an algorithm which effectively writes any permutations as a product of adjacent transpositions.

Here is how it works. Consider, for example, the permutation $\sigma$ given by $23154$ . Let us try to sort this list. Insertion sort first moves $1$ to the front by repeated swaps, first swapping the second and third position and then the first and second positions. Then we get $12354$ . Then insertion sort would swap the fourth and fifth positions, and then finish with $12345$ . So, if we do these transpositions in reverse, we get our original permutation. That is, $\sigma = (2 3)(1 2)(4 5)$ . We can see that using this process, insertion sort can write any permutation as a product of adjacent transpositions.

We need one more lemma:

If $\sigma$ is a permutation and $\rho$ an adjacent transposition, then $\sigma$ and $\sigma\rho$ have opposite parity. That is, one is odd and one is even.

Here is why. After performing $\sigma$ , if we swap two adjacent elements $a$ and $a+1$ , then the only change to the set of inversions is $a, a+1$ , since $a$ and $a+1$ haven’t moved relative to any other element. So, the only possible change is that $a, a+1$ was an inversion and no longer is, or it wasn’t an inversion and now is. So the inversion number has either been increased or decreased by one – so the parity has been switched.

So, if a permutation $\sigma$ is written as a product of $n$ adjacent transpositions, then its parity is equal to the parity of $n$ . This establishes that the product of odd and even permutations behaves like addition of odd and even numbers (formally, what we are saying is that “parity” defines a homomorphism from the permutation group to $\mathbb{Z}/2\mathbb{Z}$ ).

Another interesting fact is that every transposition is odd. We can see this (without needing to count inversions) by noticing that we can obtain any transposition $(a \ b)$ (with $a < b$ ) by repeatedly swapping adjacent elements till the element in place $a$ is moved to place $b$ , and then repeatedly swapping the other direction till the element originally in place $b$ is moved to place $a$ . If we write this out we see that $(a \ b) = (a \ a+1)(a+1 \ a+2) \dots (b-2 \ b-1)(b-1 \ b)(b-2 \ b-1) \dots (a \ a+1)$ , which has an odd number of terms.

Thus every permutation can be written only either as a product of an odd number or an even number of transpositions. Since the identity permutation is clearly even, we have the following remarkable fact: given any list, it is impossible, after performing an odd number of swaps, to obtain the original list.

Acknowledgements: Thanks to Anton Cao for suggestions. Thanks to Jessica Meng for reminding me the correct convention for composition order.

Arithmetic variety

Tag Archives: permutation

Odd and even permutations