# The sign of a permutation is well-defined

The sym­met­ric group $$S_n$$ con­tains el­e­ments which are made up from trans­po­si­tions (proof). It is a fact that if $$\sigma \in S_n$$ can be made by mul­ti­ply­ing to­gether an even num­ber of trans­po­si­tions, then it can­not be made by mul­ti­ply­ing an odd num­ber of trans­po­si­tions, and vice versa.

knows-req­ui­site(Cyclic group): Equiv­a­lently, there is a group ho­mo­mor­phism from $$S_n$$ to the cyclic group $$C_2 = \{0,1\}$$, tak­ing the value $$0$$ on those per­mu­ta­tions which are made from an even num­ber of per­mu­ta­tions and $$1$$ on those which are made from an odd num­ber.

# Proof

Let $$c(\sigma)$$ be the num­ber of cy­cles in the dis­joint cy­cle de­com­po­si­tion of $$\sigma \in S_n$$, in­clud­ing sin­gle­tons. For ex­am­ple, $$c$$ ap­plied to the iden­tity yields $$n$$, while $$c((12)) = n-1$$ be­cause $$(12)$$ is short­hand for $$(12)(3)(4)\dots(n-1)(n)$$. We claim that mul­ti­ply­ing $$\sigma$$ by a trans­po­si­tion ei­ther in­creases $$c(\sigma)$$ by $$1$$, or de­creases it by $$1$$.

In­deed, let $$\tau = (kl)$$. Either $$k, l$$ lie in the same cy­cle in $$\sigma$$, or they lie in differ­ent ones.

• If they lie in the same cy­cle, then

$$\sigma = \alpha (k a_1 a_2 \dots a_r l a_s \dots a_t) \beta$$
where $$\alpha, \beta$$ are dis­joint from the cen­tral cy­cle (and hence com­mute with $$(kl)$$). Then $$\sigma (kl) = \alpha (k a_s \dots a_t)(l a_1 \dots a_r) \beta$$, so we have bro­ken one cy­cle into two.

• If they lie in differ­ent cy­cles, then

$$\sigma = \alpha (k a_1 a_2 \dots a_r)(l b_1 \dots b_s) \beta$$
where again $$\alpha, \beta$$ are dis­joint 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 cy­cles into one.

There­fore $$c$$ takes even val­ues if there are evenly many trans­po­si­tions in $$\sigma$$, and odd val­ues if there are odd-many trans­po­si­tions in $$\sigma$$.

More for­mally, let $$\sigma = \alpha_1 \dots \alpha_a = \beta_1 \dots \beta_b$$, where $$\alpha_i, \beta_j$$ are trans­po­si­tions.

knows-req­ui­site(mod­u­lar ar­ith­metic): (The fol­low­ing para­graph is more suc­cinctly ex­pressed 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 in­te­ger $$1, 2, \dots, a$$; it also flips odd-to-even or even-to-odd for each in­te­ger $$1, 2, \dots, b$$. There­fore $$a$$ and $$b$$ must be of the same par­ity.

Parents:

• Symmetric group

The sym­met­ric groups form the fun­da­men­tal link be­tween group the­ory and the no­tion of sym­me­try.