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)

\begin{align} \quad (12) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 1 & 3 & 4 & 5 \end{pmatrix} , \quad (13) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 2 & 1 & 4 & 5 \end{pmatrix} \end{align}

Now consider the compositions $(12) \circ (13)$ and $(13) \circ (12)$. We have that:

(2)

\begin{align} \quad (12) \circ (13) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 1 & 2 & 4 & 5 \end{pmatrix} , \quad (13) \circ (12) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 1 & 4 & 5 \end{pmatrix} \end{align}

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)

\begin{align} \quad (a_1a_2...a_s) = (a_sa_{s-1}) \circ (a_sa_{s-2}) \circ ... \circ (a_sa_2) \circ (a_sa_1) \end{align}

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.