📂Abstract Algebra

Proof that a Permutation Cannot Be Both Even and Odd

Definition

A permutation of a finite symmetric group is called even if it can be written as a product of an even number of transpositions, and odd if it can be written as a product of an odd number of transpositions.

Define the sign of a permutation $\sgn (\sigma)$ by

$$ \sgn (\sigma) = \begin{cases} +1 & \text{if $\sigma$ is even} \\ -1 & \text{if $\sigma$ is odd} \end{cases} $$

Explanation

The definition of even and odd is quite natural, but the definition alone does not show the exclusivity that a permutation must be either even or odd (and not both). We verify this by the following theorem.

Theorem ¹

There is no permutation that is both even and odd.

Proof

Consider the transposition $\tau : = ( i , j )$ and the permutation $\sigma$ in the finite symmetric group $S_{n}$.

Every permutation in a finite symmetric group can be expressed as a product of disjoint cycles.

---

Case 1. $i$ and $j$ are elements of two distinct orbits of $\sigma$

Since $i$ and $j$ are not elements of the same orbit, there exists some $r, m \in \mathbb{Z}$ for which it can be written as the product $\sigma = (i , i_{1} , \cdots , i_{m}) (j , j_{1} , \cdots , j_{r})$ of two disjoint cycles. Then, by properties of transpositions, $$ \begin{align*} \tau \sigma =& (i , j) \sigma \\ =& (i , j) (i , i_{1} , \cdots , i_{m}) (j , j_{1} , \cdots , j_{r}) \\ =& (i , i_{1} , \cdots , i_{m} , j ) ( j , j_{1} , \cdots , j_{r}) \\ =& ( j , i , i_{1} , \cdots , i_{m} ) ( j , j_{1} , \cdots , j_{r}) \\ =& ( j , j_{1} , \cdots , j_{r} , i , i_{1} , \cdots , i_{m} ) \end{align*} $$ Therefore $\tau \sigma$ places $i$ and $j$ into the same orbit, and the number of orbits of $\sigma$ and $\tau \sigma$ differ by $1$.

---

Case 2. $i$ and $j$ are elements of the same orbit of $\sigma$

Because $i$ and $j$ belong to the same orbit, for some $r, m \in \mathbb{Z}$ it can be expressed as $\sigma = ( i , i_{1} , \cdots , i_{m}, j , j_{1} , \cdots , j_{r} )$. Then, by the properties of transpositions, $$ \begin{align*} \tau \sigma =& (i , j) \sigma \\ =& (i , j) (i , i_{1} , \cdots , i_{m} , j , j_{1} , \cdots , j_{r}) \\ =& (i , j) \left( i , j_{r} \right) (i , i_{1} , \cdots , i_{m} , j , j_{1} , \cdots , j_{r-1}) \\ =& (i , j) \left( i , j_{r} \right) \left( i , j_{r-1} \right) (i , i_{1} , \cdots , i_{m} , j , j_{1} , \cdots , j_{r-2}) \\ =& (i , j) \left( i , j_{r} \right) \cdots \left( i , j_{1} \right) \left( i , j \right) (i , i_{1} , \cdots , i_{m} ) \\ =& (i , j) (i , j , j_{1} , \cdots , j_{r}) (i , i_{1} , \cdots , i_{m} ) \\ =& (i , j) (j , j_{1} , \cdots , j_{r} , i) (i , i_{1} , \cdots , i_{m} ) \\ =& (i , j) (j , i) ( j , j_{1} , \cdots , j_{r} ) (i , i_{1} , \cdots , i_{m} ) \\ =& ( j , j_{1} , \cdots , j_{r} ) (i , i_{1} , \cdots , i_{m} ) \end{align*} $$ Hence $\tau \sigma$ places $i$ and $j$ into different orbits, and the number of orbits of $\sigma$ and $\tau \sigma$ differ by $1$.

---

Thus we have confirmed that the difference in the number of orbits between $\sigma$ and $\tau \sigma = (i , j ) \sigma$ is $1$ regardless of the choice of $i$ and $j$. In other words, multiplying any permutation by a transposition changes the number of orbits by $1$ each time.

On the other hand, the identity map — i.e. $\iota = \begin{bmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{bmatrix}$ — has $n$ orbits.

Lemma: Every permutation in a finite symmetric group with at least two elements can be expressed as a product of transpositions.

Express any permutation $\sigma$ as a product of transpositions $\tau_{k}$, i.e. $\sigma = \tau_{1} \tau_{2} \cdots \tau_{m} \iota$. The number of orbits then changes from $n$ by increments or decrements of 1 until it reaches some integer. Since an integer cannot be both even and odd at the same time, the permutation $\sigma$ cannot be both even and odd.

■

Revision history

• 2023-09-04, Dae-sik Ryu, revised and supplemented the development of Case 2
• 2026-04-28, Dae-sik Ryu, revised the concluding part