Decomposition of Permutations as Products of Transpositions
Recall from the Transposition Permutations page that if we have the $n$-element set $\{ 1, 2, ..., n \}$ then a transposition for this set is a cycle $\sigma$ of length $2$.
Also recall from the Decomposition of Permutations as Products of Disjoint Cycles page that if $\sigma$ is a permutation of the $n$-element set $\{ 1, 2, ..., n \}$ and if $\sigma$ is not the identity bijection then $\sigma$ can be written as a single cycle or a finite product of disjoint cycles.
Once again consider the set $\{ 1, 2, 3, 4, 5 \}$ and the transpositions $(12)$ and $(13)$ given by:
(1)Now consider the compositions $(12) \circ (13)$ and $(13) \circ (12)$. We have that:
(2)Notice that $(12) \circ (13) = (132)$ and $(13) \circ (12) = (123)$. The composition of these two transpositions is actually a cycle. Conveniently enough, if $(a_1a_2...a_s)$ is a cycle of length $s$ of $\{ 1, 2, ..., n \}$ then:
(3)Let's verify the formula above using the previous example. Using the formula for the composition of $(12)$ and $(13)$ in this particular order gives us $(12) \circ (13) = (321)$. Note that $(321)$ implies that $\sigma(3) = 2$, $\sigma(2) = 1$, and $\sigma(1) = 3$. Rearranging these equations gives us $\sigma(1) = 3$, $\sigma(3) = 2$, and $\sigma(2) = 1$, and hence $(321) = (132)$, so $(12) \circ (13) = (132)$.
Similarly, using the formula for the composition of $(13)$ and $(12)$ in this particular order and we get that $(13) \circ (12) = (231)$. Therefore $\sigma(2) = 3$, $\sigma(3) = 1$, and $\sigma(1) = 2$, which when rearranged gives us $\sigma(1) = 2$, $\sigma(2) = 3$, and $\sigma(3) = 1$, so $(231) = (123)$ and therefore $(13) \circ (12) = (123)$.
Consequentially, since every permutation can be written as a product of (disjoint) cycles, then we can take all of these cycles and rewrite them as a product of transpositions to get that every permutation can be written as a product of transpositions. It is important to note that though every permutation can be written as a product of transpositions that the product is not necessary unique.