Odd/Even Permutations

How do you classify a permutation as odd or even (composition of an odd or even number of transpositions)? I somewhat understand the textbook definition of it but I’m having hard time conceptualizing and determining how it is actually determined if it’s odd or even.

Solutions Collecting From Web of "Odd/Even Permutations"

Every permutation can be expressed as the product of one and only one of the following:

  • an odd number of transpositions $\iff$ odd permutation
  • an even number of transpositions $\iff$ even permutation

There are many ways to write a permutation as the product of transpositions, and they can vary in length, but those products will have either an odd or an even number of factors, never both.

If you know cycle notation, knowing the parity (oddness/evenness) can be found fairly easily.

One can always resort to following the pattern:

$$(a_1, a_2, a_3, a_4, a_5) = (a_1, a_5)(a_1, a_4)(a_1, a_3)(a_1, a_2)$$ which is even because there are four transpositions.

Alternatively:

$$(a_1, a_2, a_3, a_4, a_5) = (a_1, a_2)(a_2, a_3)(a_3, a_4)(a_4, a_5)$$

Again, an even number of transpositions $\iff$ the permutation is even.

You’ll see that the number of transpositions in a product corresponding to a permutation that is a cycle of length $n$ can be expressed as the product of $n – 1$ transpositions. So a cycle with a length that is even (has an even number of elements) is ODD, and a cycle with a length that is odd (has an odd number of elements) is EVEN.

If you have a permutation that is the product of disjoint cycles: say three cycles, corresponding to lengths $n_1, n_2, n_3$, then the number of transpositions representing this permutation can be computed by the parity of $(n_1 – 1)+(n_2 – 1) + (n_3 – 1)$ or simply the parity (oddness/evenness) of $n_1+n_2+n_3 – 1$


One final note: the identity permutation (i.e., the “do nothing” permutation): the permutation which can be represented as the product of one-cycles sending $1 \mapsto 1,\;2\mapsto 2,\; \cdots , n\mapsto n\;$ is always considered to be an EVEN permutation. Why? Well, note that we can represent the identity permutation by the product, say, of $(12)(12) = (12)(12)(3)\cdots(n) = (1)(2)(3)\cdots (n)$, so it is indeed an even permutation.

Simply put, it’s like adding odd and even numbers. If you add two even numbers, you’ll only ever get another even number. If you add two odd numbers, you’ll get an even number. If you add an odd and an even number, you’ll get another odd number.

It works the same for permutations. “Odd” and “Even” are defined in terms of how they interact. Define the identity permutation (that is, the one that doesn’t move any elements) as an even permutation, since applying it twice will produce itself.

Now, consider the smallest possible permutations – the ones that interchange two elements, but otherwise leave everything as-is. For instance, looking at {1,2,3,4,5}, you might have {1,3,2,4,5} as an example. These are defined to be “odd” permutations, and are referred to as “transpositions”.

The use of this concept is that, when expressing a permutation in terms of other permutations, oddness and evenness is preserved, no matter how you might express it. Like how, if you have the number 37, then it doesn’t matter how many ways you express it as a sum of integers, there will necessarily be an odd number of odd numbers in the sum – 36+1 has one odd, 32+3+1+1 has three odds, and so on.

The permutation {3,2,1} could be expressed as “switch one and three”, a single transposition. That makes it an odd permutation. It could also be expressed as “switch positions 1 and 2 ({2,1,3}), then switch positions 2 and 3 ({2,3,1}), then switch positions 1 and 2 ({3,2,1})” – three transpositions, again odd. No matter how you express it, it will always require an odd number of odd permutations.

To demonstrate it in action, consider the function
$$
f(a,b,c) = \frac{a}{b}+\frac{b}{c}+\frac{c}{a}
$$
Now, if you apply an odd permutation over the three variables, you’ll get a different result. But if you apply an even permutation, it will produce the same result.

One can also think of oddness in terms of “cycles”. Every permutation can be expressed in terms of a set of mutually exclusive cycles. For instance, {3,7,4,1,6,2,5} can be expressed as (431)(6572), where the notation means “move 4 to 3, move 3 to 1, and move 1 to 4” and “move 6 to 5, move 5 to 7, move 7 to 2, and move 2 to 6”. How does this help? Quite simply, if you count the number of elements within a cycle, then if the result is even, it’s an odd permutation, and vice versa. So here, we have 3 elements and 4 elements, making an even and an odd permutation, respectively.

Why does 3 elements make an even permutation? Because you can express it as two transpositions: (431) becomes (43)(14). Similarly, a 4 element cycle is odd – (6572) becomes (65)(57)(72).

There is another definition of even/odd permutation I found in one of the books, which I found to be easier to understand. It is:

Let P is a permutation function on a set S. For a pair (i,j) of elements in S such that i < j , if P(i) > P(j), then the permutation is said to invert the order of (i,j). The number of such pairs is known as the parity of the permutation. If permutation inverts even number of such pairs it is an even permutation else it is an odd permutation.

Making it even more simple:

Every permutation can be reduced to a sequence of “two-element swaps”: for example, the permutation that changes 123 into 312 can be written as (13)(12): first swap 1 and 3: 123-> 321, then swap 1 and 2: 321->312.

Of course, there are many different ways to do that. Any one permutation will consist of either an even number of swaps or an odd number no matter how that is done.

An even permutation is one that requires and even number of “swaps”, an odd permutation is one that requires an odd number of permutations.

Any permutation may be written as a product of transpositions. If the number of transpositions is even then it is an even permutation, otherwise it is an odd permutation. For example $(132)$ is an even permutation as $(132)=(13)(12)$ can be written as a product of 2 transpositions.

To determine whether $(a_1a_2\cdots a_n)(b_1b_2\cdots b_m)\cdots$ is an even permutation break each cycle down into transpositions : $(a_1a_2\cdots a_m)=(a_1a_2)(a_1a_3)\cdots(a_1a_n)$. The total number of transpositions for all cycles should be an even number for an even permutation.