The Symmetric group $S_n$ contains elements which are made up from transpositions (proof). It is a fact that if $\sigma \in S_n$ can be made by multiplying together an even number of transpositions, then it cannot be made by multiplying an odd number of transpositions, and vice versa.

%%%knows-requisite(Cyclic group): Equivalently, there is a Group homomorphism from $S_n$ to the Cyclic group $C_2 = \{0,1\}$, taking the value $0$ on those permutations which are made from an even number of permutations and $1$ on those which are made from an odd number. %%%

Proof

Let $c(\sigma)$ be the number of cycles in the disjoint cycle decomposition of $\sigma \in S_n$, including singletons. For example, $c$ applied to the identity yields $n$, while $c((12)) = n-1$ because $(12)$ is shorthand for $(12)(3)(4)\dots(n-1)(n)$. We claim that multiplying $\sigma$ by a transposition either increases $c(\sigma)$ by $1$, or decreases it by $1$.

Indeed, let $\tau = (kl)$. Either $k, l$ lie in the same cycle in $\sigma$, or they lie in different ones.

• If they lie in the same cycle, then $$\sigma = \alpha (k a_1 a_2 \dots a_r l a_s \dots a_t) \beta$$ where $\alpha, \beta$ are disjoint from the central cycle (and hence commute with $(kl)$). Then $\sigma (kl) = \alpha (k a_s \dots a_t)(l a_1 \dots a_r) \beta$, so we have broken one cycle into two.
• If they lie in different cycles, then $$\sigma = \alpha (k a_1 a_2 \dots a_r)(l b_1 \dots b_s) \beta$$ where again $\alpha, \beta$ are disjoint from $(kl)$. Then $\sigma (kl) = \alpha (k b_1 b_2 \dots b_s l a_1 \dots a_r) \beta$, so we have joined two cycles into one.

Therefore $c$ takes even values if there are evenly many transpositions in $\sigma$, and odd values if there are odd-many transpositions in $\sigma$.

More formally, let $\sigma = \alpha_1 \dots \alpha_a = \beta_1 \dots \beta_b$, where $\alpha_i, \beta_j$ are transpositions. %%%knows-requisite(Modular arithmetic): (The following paragraph is more succinctly expressed as: "$c(\sigma) \equiv n+a \pmod{2}$ and also $\equiv n+b \pmod{2}$, so $a \equiv b \pmod{2}$.") %%% Then $c(\sigma)$ flips odd-to-even or even-to-odd for each integer $1, 2, \dots, a$; it also flips odd-to-even or even-to-odd for each integer $1, 2, \dots, b$. Therefore $a$ and $b$ must be of the same [even_odd_parity parity].