2 Sets and functions 2.14 Powers and orders 2.16 Sign

2.15 Transpositions

2.15.1 Definition of a transposition

Definition 2.15.1.

A transposition is a 2-cycle.

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

2.15.2 Every permutation is a product of transpositions

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,\ldots,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.

Figure 2.17: A string diagram of the permutation

(1,2,3,4,5)

. Two columns contain the numbers 1, 2, 3, 4, 5. Strings connect the numbers 1, 2, 3, 4, 5 in the left-hand column to 2, 3, 4, 5, 1 respectively in the right-hand column.

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

Figure 2.18: String diagrams for

(1,2)

and

(2,3)

are shown side by side, and then the right-hand column of the diagram for

(1,2)

is joined to the left-hand column for

(2,3)

. The resulting diagram represents

(2,3)(1,2)=(1,3,2)

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.

Figure 2.19: String diagram for

(1,2,3,4)

, with dotted vertical lines to divide the strings into sections with only one crossing. From left to right, the first crossing is between strings 3 and 4, then 2 and 3, then 1 and 2

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.

Lemma 2.15.1.

Let $a_{1},a_{2},\ldots,a_{m},a_{m+1}$ be distinct numbers. Then

(a_{1},a_{2})(a_{2},a_{3},\ldots,a_{m+1})=(a_{1},a_{2},\ldots,a_{m+1}).

For example, you should check by calculating the two row notation for both sides that

	$\displaystyle(1,2)(2,3)$	$\displaystyle=(1,2,3)$
	$\displaystyle(2,3)(3,1,4,5)$	$\displaystyle=(2,3,1,4,5)$
	$\displaystyle(7,2)(2,8,9,6,4)$	$\displaystyle=(7,2,8,9,6,4).$

Proof.

Let

	$\displaystyle r$	$\displaystyle=(a_{1},a_{2},\ldots,a_{m+1})$
	$\displaystyle t$	$\displaystyle=(a_{1},a_{2})$
	$\displaystyle s$	$\displaystyle=(a_{2},a_{3},\ldots,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\leqslant i\leqslant m+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 $3\leqslant i<m+1$ , 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})$ . ∎

Lemma 2.15.2.

Every cycle equals a product of transpositions.

Proof.

Let $a=(a_{1},\ldots,a_{m})$ be a cycle. Lemma 2.15.1 tells us that

a=(a_{1},a_{2})(a_{2},a_{3},\ldots,a_{m}).

Using that lemma again on the cycle $(a_{2},\ldots,a_{m})$ we get

a=(a_{1},a_{2})(a_{2},a_{3})(a_{3},a_{4},\ldots,a_{m}).

Repeating this gives

a=(a_{1},a_{2})(a_{2},a_{3})\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).

Theorem 2.15.3.

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

Proof.

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},\ldots,c_{k}$ such that $p=c_{1}\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. ∎

Example 2.15.1.

Suppose we want to express

s=\begin{pmatrix}1&2&3&4&5&6\\ 2&3&1&5&6&4\end{pmatrix}

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

	$\displaystyle(1,2,3)$	$\displaystyle=(1,2)(2,3)$
	$\displaystyle(4,5,6)$	$\displaystyle=(4,5)(5,6)$

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