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.