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.