# The sign of a permutation is well-defined

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

Parents:

• Symmetric group

The symmetric groups form the fundamental link between group theory and the notion of symmetry.