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, for which we need a lemma.
Let ${a}_{\mathrm{1}}\mathrm{,}{a}_{\mathrm{2}}\mathrm{,}\mathrm{\dots}\mathrm{,}{a}_{m}\mathrm{,}{a}_{m\mathrm{+}\mathrm{1}}$ be distinct numbers. Then
$$({a}_{1},{a}_{2})({a}_{2},{a}_{3},\mathrm{\dots},{a}_{m+1})=({a}_{1},{a}_{2},\mathrm{\dots},{a}_{m+1}).$$ |
For example, you should check by calculating the two row notation for both sides that
$(1,2)(2,3)$ | $=(1,2,3)$ | ||
$(2,3)(3,1,4,5)$ | $=(2,3,1,4,5)$ | ||
$(7,2)(2,8,9,6,4)$ | $=(7,2,8,9,6,4).$ |
Let
$r$ | $=({a}_{1},{a}_{2},\mathrm{\dots},{a}_{m+1})$ | ||
$t$ | $=({a}_{1},{a}_{2})$ | ||
$s$ | $=({a}_{2},{a}_{3},\mathrm{\dots},{a}_{m+1})$ |
so that we have to show $r(s)=t(s(x))$ for all integers $x$. If $x$ is not one of the ${a}_{i}$ then $r(x)=x$, $s(x)=x$, and $t(x)=x$ so $r(x)=t(s(x))=x$. We only need to do the case when $x$ is equal to ${a}_{i}$ for some $1\u2a7di\u2a7dm+1$.
Let $i=1$. Then $r({a}_{1})={a}_{2}$, and $s({a}_{1})={a}_{1}$ and $t({a}_{1})={a}_{2}$ so $t(s({a}_{1}))={a}_{2}=r({a}_{1})$.
Let $i=2$, so $r({a}_{2})={a}_{3}$. We have $s({a}_{2})={a}_{3}$ and $t({a}_{3})={a}_{3}$, so $t(s({a}_{2}))={a}_{3}=r({a}_{2})$.
Let $$, so, $r({a}_{i})={a}_{i+1}$, $s({a}_{i})={a}_{i+1}$, $t({a}_{i+1})={a}_{i+1}$, so $t(s({a}_{i}))=t({a}_{i+1})={a}_{i+1}=r({a}_{i})$.
Finally $r({a}_{m+1})={a}_{1}$, $s({a}_{m+1})={a}_{2}$, $t({a}_{2})={a}_{1}$, so $t(s({a}_{m+1}))={a}_{1}=r({a}_{m+1})$. ∎
Every cycle equals a product of transpositions.
Let $a=({a}_{1},\mathrm{\dots},{a}_{m})$ be a cycle. Lemma 2.15.1 tells us that
$$a=({a}_{1},{a}_{2})({a}_{2},{a}_{3},\mathrm{\dots},{a}_{m}).$$ |
Using that lemma again on the cycle $({a}_{2},\mathrm{\dots},{a}_{m})$ we get
$$a=({a}_{1},{a}_{2})({a}_{2},{a}_{3})({a}_{3},{a}_{4},\mathrm{\dots},{a}_{m}).$$ |
Repeating this gives
$$a=({a}_{1},{a}_{2})({a}_{2},{a}_{3})\mathrm{\cdots}({a}_{m-1},{a}_{m})$$ |
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).$$ |