A transposition is a 2-cycle.

For example, the only transpositions in ${S}_{3}$ are $(1,2)$, $(2,3)$, and $(1,3)$.

In this section we’re going to prove that every permutation can be written as a product of transpositions. Before we do so, here is some motivation for why we should expect this to be true.

One way we’ve already seen of illustrating a permutation $s$ in ${S}_{n}$ is to draw the numbers $1,2,\mathrm{\dots},n$ in a column, and then in another column to its right, and draw a line from each number $i$ in the first column to $s(i)$ in the second. You get what looks like a lot of pieces of string tangled together.

Here is a diagram of the permutation $s=(1,2,3,4,5)$. Think of the lines as pieces of string connecting $i$ on the left with $s(i)$ on the right.

Composing two permutations drawn in this way corresponds to placing their diagrams side-by-side:

Imagine taking such a diagram and stretching it out. You could divide it up into smaller diagrams, each of which contains only one crossing of strings.

A diagram with a single string crossing is a transposition, since only two numbers change place. The diagram above illustrates the fact that

$$(1,2,3,4)=(1,2)(2,3)(3,4).$$ |

Now we’re ready for a formal proof of the result that every permutation equals a product of transpositions. We first do it for cycles:

Every cycle equals a product of transpositions.

Let $a=({a}_{0},\mathrm{\dots},{a}_{m-1})$ be a cycle. Lemma 2.14.1 tells us that

$$a=({a}_{0},{a}_{1})({a}_{1},{a}_{2},\mathrm{\dots},{a}_{m-1}).$$ |

Using that lemma again on the cycle $({a}_{1},\mathrm{\dots},{a}_{m-1})$ we get

$$a=({a}_{0},{a}_{1})({a}_{1},{a}_{2})({a}_{2},{a}_{3},\mathrm{\dots},{a}_{m-1}).$$ |

Repeating this gives

$$a=({a}_{0},{a}_{1})({a}_{1},{a}_{2})\mathrm{\cdots}({a}_{m-2},{a}_{m-1})$$ |

which shows that $a$ can be written as a product of transpositions. ∎

To illustrate this result you should check by computing both sides that

$$(1,2,3,4)=(1,2)(2,3)(3,4).$$ |

Every permutation in ${S}_{n}$ is equal to a product of transpositions.

Let $p$ be a permutation. We have seen that every permutation can be written as a product of cycles, so there are cycles ${c}_{1},\mathrm{\dots},{c}_{k}$ such that $p={c}_{1}\mathrm{\cdots}{c}_{k}$. The lemma above shows how to write each ${c}_{i}$ as a product of transpositions, which expresses $p$ as a product of transpositions too. ∎

Suppose we want to express

$$s=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 2& 3& 1& 5& 6& 4\end{array}\right)$$ |

as a product of transpositions. A disjoint cycle decomposition for $s$ is

$$s=(1,2,3)(4,5,6)$$ |

and applying the lemma above, we get

$(1,2,3)$ | $=(1,2)(2,3)$ | ||

$(4,5,6)$ | $=(4,5)(5,6)$ |

So

$$s=(1,2,3)(4,5,6)=(1,2)(2,3)(4,5)(5,6).$$ |