📂Abstract Algebra

Proof that a Permutation Cannot Be Both Even and Odd

Definition

If a permutation of a finite symmetric group can be expressed as the product of an even number of transpositions, it is called Even, and if it can be expressed as the product of an odd number of transpositions, it is called Odd.

Description

Although the definitions of even and odd are quite natural, by the definitions alone, there’s no apparent exclusivity that something must be either even or odd. Let’s verify this through the following theorem.

Theorem ¹

A permutation that is both even and odd does not exist.

Proof

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

Every permutation of a finite symmetric group can be expressed as the composition of disjoint cycles.

---

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

Since $i$ and $j$ are not elements of the same orbit, for some $r, m \in \mathbb{Z}$, it can be expressed as the product of disjoint two cycles, $\sigma = (i , i_{1} , \cdots , i_{m}) (j , j_{1} , \cdots , j_{r})$. Hence, by the property 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$ results in $i$ and $j$ becoming elements of the same orbit, and the number of orbits in $\sigma$ and $\tau \sigma$ differs by $1$.

---

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

Since $i$ and $j$ are elements of 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} )$. Hence, by the property 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*} $$ it results in $\tau \sigma$ making $i$ and $j$ become elements of different orbits, and the number of orbits in $\sigma$ and $\tau \sigma$ differs by $1$.

---

Thus, we have confirmed that the difference in the number of orbits of $\sigma$ and $\tau \sigma = (i , j ) \sigma$ is $1$, regardless of what $i$ and $j$ might be. In other words, no matter what permutation, the addition of a transposition increases the number of orbits by $1$.

Meanwhile, the number of orbits of the identity function, or $\iota = \begin{bmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{bmatrix}$, is $n$.

Auxiliary Theorem: Every permutation of a finite symmetric group with more than one element can be expressed as a product of transpositions.

If we express an arbitrary permutation $\sigma$ in terms of transpositions $\tau_{k}$, it comes out to $\sigma = \tau_{1} \tau_{2} \cdots \tau_{N} \iota$, and the number of orbits is $(N + n)$. Since a natural number $(N+n)$ cannot be both even and odd at the same time, the permutation $\sigma$ also cannot be both even and odd.

■

Renewal

• September 4, 2023, by Daesik Ryu, Modification and reinforcement of Case 2 development