📂Abstract Algebra

Proof that a Permutation Cannot Be Both Even and Odd

Definition

A permutation of a finite symmetric group can be expressed as a product of an even number of transpositions, making it even, or as a product of an odd number of transpositions, making it odd.

The sign of a permutation $\sgn (\sigma)$ is defined as follows:

$$ \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 appears quite natural, but from the definition alone, there is no exclusivity that states a permutation must be either even or odd. We shall verify this with the following theorem.

Theorem ¹

There exist no permutations that are both even and odd.

Proof

Consider a transposition $\tau : = ( i , j )$ and a permutation $\sigma$ of a 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 different orbits of $\sigma$

Since $i$ and $j$ are not elements of the same orbit, for some $r, m \in \mathbb{Z}$, they can be represented as a product of two disjoint cycles $\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 , 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*} $$ Hence, $\tau \sigma$ indicates that $i$ and $j$ belong to 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$

Since $i$ and $j$ are elements of the same orbit, for some $r, m \in \mathbb{Z}$, they can be represented 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*} $$ Therefore, $\tau \sigma$ indicates that $i$ and $j$ belong to 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 what $i$ and $j$ are. This means that with each transposition applied to any permutation, the number of orbits increases by $1$.

Meanwhile, the identity function, i.e., $\iota = \begin{bmatrix} 1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{bmatrix}$ 의 궤도의 갯수는 $n$.

Auxiliary Theorem: In finite symmetric groups with more than one element, every permutation can be expressed as a product of transpositions.

Expressing an arbitrary permutation $\sigma$ as transpositions $\tau_{k}$ yields $\sigma = \tau_{1} \tau_{2} \cdots \tau_{N} \iota$, and the number of orbits is $(N + n)$. A natural number $(N+n)$ cannot be both even and odd simultaneously, hence the permutation $\sigma$ cannot be both even and odd.

■

Renewal

• September 4, 2023, Ryu Dae-sik, Modified and reinforced Case 2 development