# Every member of a symmetric group on finitely many elements is a product of transpositions

Given a per­mu­ta­tion $$\sigma$$ in the sym­met­ric group $$S_n$$, there is a finite se­quence $$\tau_1, \dots, \tau_k$$ of trans­po­si­tions such that $$\sigma = \tau_k \tau_{k-1} \dots \tau_1$$. Equiv­a­lently, sym­met­ric groups are gen­er­ated by their trans­po­si­tions.

Note that the trans­po­si­tions might “over­lap”. For ex­am­ple, $$(123)$$ is equal to $$(23)(13)$$, where the el­e­ment $$3$$ ap­pears in two of the trans­po­si­tions.

Note also that the se­quence of trans­po­si­tions is by no means uniquely de­ter­mined by $$\sigma$$.

# Proof

It is enough to show that a cy­cle is ex­press­ible as a se­quence of trans­po­si­tions. Once we have this re­sult, we may sim­ply re­place the suc­ces­sive cy­cles in $$\sigma$$’s dis­joint cy­cle no­ta­tion by the cor­re­spond­ing se­quences of trans­po­si­tions, to ob­tain a longer se­quence of trans­po­si­tions which mul­ti­plies out to give $$\sigma$$.

It is easy to ver­ify that the cy­cle $$(a_1 a_2 \dots a_r)$$ is equal to $$(a_{r-1} a_r) (a_{r-2} a_r) \dots (a_2 a_r) (a_1 a_r)$$. In­deed, that product of trans­po­si­tions cer­tainly does not move any­thing that isn’t some $$a_i$$; while if we ask it to eval­u­ate $$a_i$$, then the $$(a_1 a_r)$$ does noth­ing to it, $$(a_2 a_r)$$ does noth­ing to it, and so on up to $$(a_{i-1} a_r)$$. Then $$(a_i a_r)$$ sends it to $$a_r$$; then $$(a_{i+1} a_r)$$ sends the re­sult­ing $$a_r$$ to $$a_{i+1}$$; then all sub­se­quent trans­po­si­tions $$(a_{i+2} a_r), \dots, (a_{r-1} a_r)$$ do noth­ing to the re­sult­ing $$a_{i+1}$$. So the out­put when given $$a_i$$ is $$a_{i+1}$$.

# Why is this use­ful?

It can make ar­gu­ments sim­pler: if we can show that some prop­erty holds for trans­po­si­tions and that it is closed un­der prod­ucts, then it must hold for the en­tire sym­met­ric group.

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.