A transposition is a 2-cycle.
For example, the only transpositions in are , , and .
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 in is to draw the numbers in a column, and then in another column to its right, and draw a line from each number in the first column to in the second. You get what looks like a lot of pieces of string tangled together.
Here is a diagram of the permutation . Think of the lines as pieces of string connecting on the left with 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
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 be distinct numbers. Then
For example, you should check by calculating the two row notation for both sides that
Let
so that we have to show for all integers . If is not one of the then , , and so . We only need to do the case when is equal to for some .
Let . Then , and and so .
Let , so . We have and , so .
Let , so, , , , so .
Finally , , , so . ∎
Every cycle equals a product of transpositions.
Let be a cycle. Lemma 2.15.1 tells us that
Using that lemma again on the cycle we get
Repeating this gives
which shows that can be written as a product of transpositions. ∎
To illustrate this result you should check by computing both sides that
Every permutation in is equal to a product of transpositions.
Let be a permutation. We have seen that every permutation can be written as a product of cycles, so there are cycles such that . The lemma above shows how to write each as a product of transpositions, which expresses as a product of transpositions too. ∎
Suppose we want to express
as a product of transpositions. A disjoint cycle decomposition for is
and applying the lemma above, we get
So