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

https://arbital.com/p/symmetric_group_is_generated_by_transpositions

by Patrick Stevens Jun 15 2016

This fact can often simplify arguments about permutations: if we can show that something holds for transpositions, and that it holds for products, then it holds for everything.


Given a permutation $~$\sigma$~$ in the Symmetric group $~$S_n$~$, there is a finite sequence $~$\tau_1, \dots, \tau_k$~$ of transpositions such that $~$\sigma = \tau_k \tau_{k-1} \dots \tau_1$~$. Equivalently, symmetric groups are generated by their transpositions.

Note that the transpositions might "overlap". For example, $~$(123)$~$ is equal to $~$(23)(13)$~$, where the element $~$3$~$ appears in two of the transpositions.

Note also that the sequence of transpositions is by no means uniquely determined by $~$\sigma$~$.

Proof

It is enough to show that a cycle is expressible as a sequence of transpositions. Once we have this result, we may simply replace the successive cycles in $~$\sigma$~$'s disjoint cycle notation by the corresponding sequences of transpositions, to obtain a longer sequence of transpositions which multiplies out to give $~$\sigma$~$.

It is easy to verify that the cycle $~$(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)$~$. Indeed, that product of transpositions certainly does not move anything that isn't some $~$a_i$~$; while if we ask it to evaluate $~$a_i$~$, then the $~$(a_1 a_r)$~$ does nothing to it, $~$(a_2 a_r)$~$ does nothing 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 resulting $~$a_r$~$ to $~$a_{i+1}$~$; then all subsequent transpositions $~$(a_{i+2} a_r), \dots, (a_{r-1} a_r)$~$ do nothing to the resulting $~$a_{i+1}$~$. So the output when given $~$a_i$~$ is $~$a_{i+1}$~$.

Why is this useful?

It can make arguments simpler: if we can show that some property holds for transpositions and that it is closed under products, then it must hold for the entire symmetric group.