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

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.