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

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.

Parents:

• Symmetric group

The symmetric groups form the fundamental link between group theory and the notion of symmetry.