The sign of a permutation is well-defined

by Patrick Stevens Jun 17 2016 updated Jun 28 2016

This result is what allows the alternating group to exist.

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. %%%


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.

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].