Odd/Even Permutations

Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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 "swaps".

Answer 4

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.

Answer 5

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.

Answer 6

One other definition of the sign of a permutation comes from linear algebra, a permutation is a map of sets $\sigma:X\rightarrow X$, so we can view it as a linear map on a vector space with a basis indexed by our set X. Then the sign of sigma is simply the determinant of this linear map, interpreted in our field.

This perspective can be helpful for computing the signs of permutations arising from other actions too, such as the symmetric group acting on $k$ element subsets of $X$. It also suggests to look at other coefficients of the characteristic polynomial, for example, the trace counts the number of fixed points of $\sigma$ on $X$.

Answer 7

The results follow naturally upon considering the action of $ S_n $ on arrangements :

A list $ [k_1, \ldots, k_n] $ made by taking $ 1, 2, \ldots, n $ in some order is called an arrangement.

For $ \sigma \in S_n $ and arrangement $ [k_1, \ldots, k_n] $, we can define

$$ \sigma * [k_1, \ldots, k_n] := ( [k_1, \ldots, k_n] \text{ after putting each } k_i \text{ into slot } \sigma(i) )$$

That is, $ [k_1, \ldots, k_n] \rightsquigarrow \sigma * [k_1, \ldots, k_n] $ amounts to putting whatever is in slot $ i $ into slot $ \sigma(i) $.

---

Note $\sigma * [k_1, \ldots, k_n] = [k_{\sigma^{-1} (1)}, \ldots, k_{\sigma^{-1} (n)}]$

[Because in $ [k_1, \ldots, k_n] \rightsquigarrow \sigma * [k_1, \ldots, k_n] $ the $ k_t $ which gets sent to slot $ j $ satisfies $ \sigma(t) = j $ i.e. $ t = \sigma ^{-1} (j) $.]

Also $ \sigma * ( \tau * [k_1, \ldots, k_n] ) = (\sigma \tau) * [k_1, \ldots, k_n] $

[Because in $[k_1, \ldots, k_n] \rightsquigarrow \sigma * (\tau * [k_1, \ldots, k_n])$, $k_i$ is first sent to slot $ \tau(i) $ and then to slot $ \sigma(\tau(i)) $. And $ [k_1, \ldots, k_n] \rightsquigarrow (\sigma \tau)*[k_1, \ldots, k_n] $ has the same effect.]

We'll write $ ``\, [k_1, \ldots, k_n] \stackrel{\sigma}{\rightsquigarrow} [l_1, \ldots, l_n]"$ to mean $`` \, [l_1, \ldots, l_n] = \sigma * [k_1, \ldots, k_n]" $.

---

Example 1. Cycle $ (1 \, \, 2 \, \, 3 \, \, 4) = (1 \, \, 4) (1 \, \, 3) (1 \, \, 2) $. It's easy to check this is true, but here is one way we can come up with the decomposition :

So $$ (1 \, \, 2 \, \, 3 \, \, 4)*[1,2,3,4] = (1 \, \, 4)*\bigg( (1 \, \, 3) * ( (1 \, \, 2) * [1,2,3,4]) \bigg)$$

i.e.

$$(1 \, \, 2 \, \, 3 \, \, 4)*[1,2,3,4] = (1 \, \, 4) (1 \, \, 3) (1 \, \, 2) * [1,2,3,4] $$

i.e.

$$ (1 \, \, 2 \, \, 3 \, \, 4) = (1 \, \, 4) (1 \, \, 3) (1 \, \, 2) $$

This suggests in general $ (a_1 \, \, a_2 \, \, \ldots \, \, a_k) = (a_1 \, \, a_k) (a_1 \, \, a_{k-1}) \ldots (a_1 \, \, a_2) $, which is readily verified to be true.

Also any $ \sigma \in S_n $ is a product of disjoint cycles, and each cycle decomposes by $ (a_1 \, \, a_2 \, \, \ldots \, \, a_k) = (a_1 \, \, a_k) (a_1 \, \, a_{k-1}) \ldots (a_1 \, \, a_2) $. So each $ \sigma \in S_n $ is a product of transpositions.

---

Example 2.

So

$$ (1 \, \, 4) = (1 \, \, 2) (2 \, \, 3) (3 \, \, 4) (2 \, \, 3) (1 \, \, 2) $$

Similarly in general any transposition is a product of an odd number of "elementary transpositions" [i.e. transpositions of the form $ (j \, \, j+1) $]

---

For $ \sigma \in S_n $, a pair $ i < j $ such that $ \sigma(i) > \sigma(j) $ is called an inversion in $ \sigma $. Also $ \text{inv}(\sigma) $ denotes the number of inversions in $ \sigma $.

To keep track of parity of $ \text{inv}(\sigma) $, we can look at sign $ \text{sgn}(\sigma) := (-1)^{\text{inv}(\sigma)} $. Permutations with sign $ 1 $ are called even, and those with sign $ (-1) $ odd.

By an "inversion in arrangement $[k_1, \ldots, k_n]$", we'll mean an inversion in $ \sigma = \begin{pmatrix} 1 &2 &\ldots &n \\ k_1 &k_2 &\ldots &k_n \end{pmatrix} $ [that is, a pair $ k_i, k_j $ in $[k_1, \ldots, k_n]$ where the larger of the two is to the left of the smaller]. Similarly sign of an arrangement is also meaningful.

---

Notice for any $ (j \, \, j+1) \in S_n $, $ [k_1, \ldots, k_n] \rightsquigarrow (j \, \, j+1)*[k_1, \ldots, k_n] $ changes number of inversions by $ \pm 1 $ (and therefore flips sign).

Hence for any transposition $ \tau \in S_n $, writing it as a product of odd number of elementary transpositions (example 2) gives that $ [k_1, \ldots, k_n] \rightsquigarrow \tau * [k_1, \ldots, k_n] $ reverses sign.

---

Let $ \tau_1, \ldots, \tau_k \in S_n $ be transpositions. Looking at their product $ \sigma = \tau_1 \ldots \tau_k $,

$$ (\tau_1 \ldots \tau_k)*[1, \ldots, n] = \tau_1 * \big( \ldots * (\tau_k * [1, \ldots, n]) \ldots \big) $$

As RHS has sign $ (-1)^k $,

$$ \text{sgn}(\tau_1 \ldots \tau_k * [1, \ldots, n]) = (-1)^k $$

i.e.

$$ \text{sgn}([\sigma^{-1}(1), \ldots, \sigma^{-1}(n)]) = (-1)^k $$

i.e. $ \text{sgn}(\sigma ^{-1}) = (-1)^k $, that is $ \text{sgn}(\tau_k \ldots \tau_1) = (-1)^k $.

So product of any $ k $ transpositions has sign $ (-1)^k $.

---

Let $ \sigma, \pi \in S_n $. Writing them as product of transpositions (example 1)

$$ \sigma = \tau_1 \ldots \tau_k \\ \pi = \tau'_1 \ldots \tau'_l $$

we have $ \text{sgn}(\sigma \pi) = \text{sgn}(\tau_1 \ldots \tau_k \tau'_1 \ldots \tau'_l) $ $ = (-1)^{k+l} = (-1)^k (-1)^l $ $ = \text{sgn}(\tau_1 \ldots \tau_k) \text{sgn}(\tau'_1 \ldots \tau'_l) $ $ = \text{sgn}(\sigma) \text{sgn}(\pi) $.

So finally for any $ \sigma, \pi \in S_n $, $$ \fbox{$ \text{sgn}(\sigma \pi) = \text{sgn}(\sigma) \text{sgn} (\pi) $} $$

---

Example 3. As $ (a_1 \, \, a_2 \, \, \ldots \, \, a_k) = (a_1 \, \, a_k) (a_1 \, \, a_{k-1}) \ldots (a_1 \, \, a_2) $, $ \text{sgn}(a_1 \, \, a_2 \, \, \ldots \, \, a_k) = (-1)^{k-1} $.

---

Ref: A similar discussion can be found in E.B.Vinberg's "Course in Algebra".

Answer 8

[This is one approach, mentioned in Jacobson's Basic Algebra Vol 1]

Fix $n \in \mathbb{Z} _{\gt 0}.$ For $\sigma \in S _n,$ let $N(\sigma)$ be the number of cycles in the cycle decomposition of $\sigma.$

Th: Let $\sigma \in S _n,$ and let $\tau \in S _n$ be a transposition. Then $N(\tau \sigma) = N(\sigma) \pm 1$ (especially $\sigma \rightsquigarrow \tau \sigma$ flips the parity of number of cycles).
Pf: Let $\tau = (\alpha \text{ } \beta),$ and let $\sigma = C _1 \ldots C _{N(\sigma)}$ be the cycle decomposition of $\sigma.$
$\underline{\textbf{Case-1}}$ (Both $\alpha, \beta$ appear in the same cycle of $\sigma$)
WLOG $C _1$ has both $\alpha, \beta$ in it. Now the cycle decomposition of $(\alpha \text{ } \beta) C _1$ is: ${ ({\color{purple}{\alpha}} \text{ } {\color{green}{\beta}}) ({\color{purple}{\alpha}} \text{ } x _1 \ldots \text{ } x _k \text{ } {\color{green}{\beta}} \text{ } x _{k+1} \text{ } \ldots \text{ } x _l) }$ ${ = ({\color{purple}{\alpha}} \text{ } x _1 \text{ } \ldots \text{ } x _k) ({\color{green}{\beta}} \text{ } x _{k+1} \text{ } \ldots \text{ } x _l ) }.$ So ${ N(\tau \sigma) = N(\sigma) + 1}$ in this case.
$\underline{\textbf{Case-2}}$ ($\alpha, \beta$ appear in different cycles of $\sigma$)
WLOG $C _1$ has $\alpha$ and $C _2$ has $\beta$ in it. Now the cycle decomposition of ${ (\alpha \text{ } \beta) C _1 C _2 }$ is: ${ ({\color{purple}{\alpha}} \text{ } {\color{green}{\beta}} ) ({\color{purple}{\alpha}} \text{ } x _1 \text{ } \ldots \text{ } x _k) ( {\color{green}{\beta}} \text{ } y _1 \text{ } \ldots \text{ } y _l) }$ ${ = (x _1 \text{ } \ldots \text{ } x _k \text{ } {\color{green}{\beta}} \text{ } y _1 \text{ } \ldots \text{ } y _l \text{ } {\color{purple}{\alpha}} ). }$ So $N(\tau \sigma) = N(\sigma) -1$ in this case.

Cor: If two products of transpositions $\tau _1 \ldots \tau _k$ and $\tau' _1 \ldots \tau' _l$ are equal in $S _n,$ then $k,l$ have the same parity.

---

Every $\sigma \in S _n$ is a product of transpositions.

$\sigma$ is a product of disjoint cycles, and each cycle $(a _1 \text{ } \ldots \text{ } a _k)$ is $\underbrace{(a _1 \text{ } a _k) \ldots (a _1 \text{ } a _2)} _{k-1 \text{ transpositions}} .$

But from the corollary, no matter how we express $\sigma$ as a product of transpositions in $S _n$ the quantity $(-1)$ raised to the number of transpositions remains the same. We call this invariant $\text{sgn}(\sigma).$

Now we have $\text{sgn}(\sigma _1 \sigma _2) = \text{sgn}(\sigma _1) \text{sgn}(\sigma _2)$ and $\text{sgn}((a _1 \text{ } \ldots \text{ } a _k)) = (-1) ^{k-1}.$