Given a permutation in the symmetric group $S_{n}$ , there is a finite sequence $τ_{1}, \dots, τ_{k}$ of transpositions such that $σ = τ_{k} τ_{k - 1} \dots τ_{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 $σ$ .

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 $σ$ 's disjoint cycle notation by the corresponding sequences of transpositions, to obtain a longer sequence of transpositions which multiplies out to give $σ$ .

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.