27
$\begingroup$

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.

$\endgroup$
38
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is this making sense, 65422? $\endgroup$ – Namaste Apr 15 '13 at 1:54
  • $\begingroup$ Such a nice descriptive answer, hope you get feedback! +1 $\endgroup$ – Amzoti Apr 15 '13 at 4:22
  • 3
    $\begingroup$ I didn't get how >$(12)(12) = (12)(12)(3)\cdots(n) = (1)(2)(3)\cdots (n)$ shows that identity is an even permutation. $\endgroup$ – sequence Dec 1 '15 at 6:28
  • $\begingroup$ How do you write so clearly? Namaste! $\endgroup$ – omehoque Mar 11 at 7:00
7
$\begingroup$

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)(31). Similarly, a 4 element cycle is odd - (6572) becomes (65)(57)(72).

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please state the book's name. Thanks in anticipation. $\endgroup$ – jiten Aug 29 '18 at 13:01
  • $\begingroup$ Hi, I answered this 3 years back. Let me search for the book. can't promise that I will be able to find it. Ill surely try. $\endgroup$ – Sahil Singh Aug 29 '18 at 13:19
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.