Even and Odd Cycles

Recall that if we have the finite $n$-element set $\{ 1, 2, ..., n \}$ and $\alpha$ is a permutation of the elements in this set then $\alpha$ is said to be an even permutation if it can be written as the product of an even number of transpositions and $\alpha$ is said to be an odd permutation if it can be written as the product of and odd number of transpositions. Since cycles are permutations by definition, we can define each cycle to be either even or odd.

We will now look at some basic results regarding even and odd cycles.

Proposition 1: If $\alpha = (a_1a_2...a_s)$ is a cycle of length $s$ from the set $\{ 1, 2, ..., n \}$ then: 1. $\alpha$ is an even permutation if $s$ is odd. 2. $\alpha$ is an odd permutation if $s$ is even.

• Proof: On the Decomposition of Permutations as Products of Transpositions page we remarked that any cycle $\alpha = (a_1a_2...a_s)$ can be written as:

(1)

\begin{align} \quad \alpha = (a_1a_2...a_s) = \underbrace{(a_sa_{s-1}) \circ (a_sa_{s-2}) \circ ... \circ (a_sa_1)}_{s - 1 \: \mathrm{many \: transpositions}} \end{align}

• If $s$ is even, then $s - 1$ is odd, and so $\alpha$ can be written as the product of an odd number of transpositions, so $\alpha$ is odd. If $s$ is odd, then $s - 1$ is even, and so $\alpha$ can be written as the product of an even number of transpositions, so $\alpha$ is even. $\blacksquare$

Proposition 2: If $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_t)$ are cycles from the set $\{ 1, 2, ..., n \}$ then: 1. If $\alpha$ and $\beta$ are both even cycles then $\alpha \circ \beta$ is an even cycle. 2. If $\alpha$ and $\beta$ are both odd cycles then $\alpha \circ \beta$ is an even cycle. 3. If one of $\alpha$ or $\beta$ is an even cycle and the other is an odd cycle then $\alpha \circ \beta$ is an odd cycle.

• Proof: First suppose that $\alpha$ and $\beta$ are both cycles of $\{ 1, 2, ..., n \}$. Then for transpositions $t_1, t_2, ..., t_k, u_1, u_2, ..., u_j$ we have that $\alpha$ and $\beta$ can be written as:

(2)

\begin{align} \quad \alpha = t_1 \circ t_2 \circ ... \circ t_k , \quad \beta = u_1 \circ u_2 \circ ... \circ u_j \end{align}

• The composition of $\alpha \circ \beta$ is given by:

(3)

\begin{align} \quad \alpha \circ \beta = \underbrace{(t_1 \circ t_2 \circ ... \circ t_k) \circ (u_1 \circ u_2 \circ ... \circ u_j)}_{k+j \: \mathrm{many \: transpositions}} \end{align}

• Suppose that $\alpha$ and $\beta$ are both even cycles. Then $k$ and $j$ are even. So $k + j$ is even, and hence $\alpha \circ \beta$ is an even cycle.

• Suppose that $\alpha$ and $\beta$ are both odd cycles. Then $k$ and $j$ are odd. So $k + j$ is even, and hence $\alpha \circ \beta$ is an even cycle.

• Suppose that one of $\alpha$ or $\beta$ is even and the other cycle is odd. Then $k + j$ is odd, and hence $\alpha \circ \beta$ is an odd cycle. $\blacksquare$