2 Sets and functions 2.12 Cycles 2.14 Powers and orders

2.13 Products of disjoint cycles

2.13.1 Every permutation is a product of disjoint cycles

Theorem 2.13.1.

Every $s\in S_{n}$ equals a product of disjoint cycles.

Proof.

Choose a number $i$ and form the sequence $i,s(i),s^{2}(i),\ldots$ . Since these numbers belong to the set $\{1,2,\ldots,n\}$ not all of them can repeat, that is, there exist $p<q$ such that $s^{p}(i)=s^{q}(i)$ , and so $s^{q-p}(i)=i$ . Choose the smallest positive number $r$ such that $s^{r}(i)=i$ . Then all of the numbers

i,s(i),s^{2}(i),\ldots,s^{r-1}(i)

(2.4)

are different, since if there were numbers $0\leqslant p<q<r$ such that $s^{p}(i)=s^{q}(i)$ then we’d have $s^{q-p}(i)=i$ and $0<q-p<r$ contradicting $r$ being the smallest such power. Observe that, on the numbers (2.4), $s$ behaves exactly like the $r$ -cycle $(i,s(i),\ldots,s^{r-1}(i))$ .

If there is a number $j\in\{1,2,\ldots,n\}$ that doesn’t belong to this cycle, we can repeat the procedure above to get another cycle containing $j$ and such that $s$ does the same thing as the cycle to its elements. This will be disjoint from the previous one since if $s^{p}(j)=s^{q}(i)$ for some $p, q$ then $j=s^{q-p}(i)$ which belongs to the previous cycle, contradicting the choice of $j$ .

By repeating this procedure until there are no longer any numbers between 1 and $n$ not contained in one of our disjoint cycles; the product of these is $s$ . ∎

Definition 2.13.1.

An expression for a permutation $s$ as a product of disjoint cycles $c_{1}$ , $c_{2}$ , …, $c_{r}$

s=c_{1}c_{2}\cdots c_{r}

is called a disjoint cycle decomposition of $s$ .

We’ve just proved that every permutation has at least one disjoint cycle decomposition. In fact a permutation can have lots of disjoint cycle decompositions, e.g.

(1,2)(3,4)=(3,4)(1,2)=(4,3)(1,2)=\cdots

2.13.2 How to find a disjoint cycle decomposition

To find a disjoint cycle decomposition for an element of $S_{n}$ :

1.

Pick a number that doesn’t yet appear in a cycle.
2.

Compute its image, and the image of that, and so on, until you have a cycle. Write down that cycle.
3.

If all elements of $1,\ldots,n$ are in one of your cycles, stop, else go back to step 1.

Example 2.13.1.

Let $s=\begin{pmatrix}1&2&3&4&5&6&7\\ 7&6&3&1&2&5&4\end{pmatrix}$ . We pick a number not yet in a cycle, say 1. 1 goes to 7, 7 goes to 4, 4 goes to 1. We are back to the number we started with, so our first cycle is $(1,7,4)$ . Now we pick another number not in a cycle, say 2. $s$ sends 2 to 6, 6 to 5, and 5 to 2. That’s another cycle, so we have $(1,7,4)(2,6,5)$ . Now we pick another number not yet in a cycle — the only one left is 3. $s$ sends 3 to 3, so this is immediately a cycle. We have $s=(1,7,4)(2,6,5)(3)$ .

As we saw when we defined cycles in Definition 2.12.1, any 1-cycle is equal to the identity function. For that reason (and because 1-cycles look confusingly like what we write when we evaluate a function) we usually omit 1-cycles like $(3)$ from disjoint cycle decompositions, so we’d write the permutation $s$ of the previous example as $(1,7,4)(2,6,5)$ .

2.13.3 Composing permutations given as products of disjoint cycles

Example 2.13.2.

Let’s work out a disjoint cycle decomposition for $\sigma\tau$ where

	$\displaystyle\sigma$	$\displaystyle=(4,2,6,1,5)$
	$\displaystyle\tau$	$\displaystyle=(5,4,7,3,8)$

are elements of $S_{8}$ .

Remember that $\sigma\tau$ means do $\tau$ , then do $\sigma$ . Keeping that in mind, all we have to do is follow the instructions from before. Start with 1:

	$\displaystyle\sigma(\tau(1))$	$\displaystyle=\sigma(1)=5$
	$\displaystyle\sigma(\tau(5))$	$\displaystyle=\sigma(4)=2$
	$\displaystyle\sigma(\tau(2))$	$\displaystyle=\sigma(2)=6$
	$\displaystyle\sigma(\tau(6))$	$\displaystyle=\sigma(6)=1$

…and we have our first cycle, $(1,5,2,6)$ . Continuing with a number not yet in a cycle, say 3, we get

	$\displaystyle\sigma(\tau(3))$	$\displaystyle=\sigma(8)=8$
	$\displaystyle\sigma(\tau(8))$	$\displaystyle=\sigma(5)=4$
	$\displaystyle\sigma(\tau(4))$	$\displaystyle=\sigma(7)=7$
	$\displaystyle\sigma(\tau(7))$	$\displaystyle=\sigma(3)=3$

…and we have our next cycle, $(3,8,4,7)$ . There are no numbers left, so

\sigma\tau=(1,5,2,6)(3,8,4,7).

You should now find a disjoint cycle decomposition for $\tau\sigma$ . You’ll find that it has two 4-cycles again, but isn’t the same as the decomposition we got for $\sigma\tau$ .

Example 2.13.3.

Let’s find a disjoint cycle decomposition for $(1,2,3,4)(2,3,4,5)$ . Write $a=(1,2,3,4),b=(2,3,4,5)$ . Starting with 1 as usual,

	$\displaystyle a(b(1))$	$\displaystyle=a(1)=2$
	$\displaystyle a(b(2))$	$\displaystyle=a(3)=4$
	$\displaystyle a(b(4))$	$\displaystyle=a(5)=5$
	$\displaystyle a(b(5))$	$\displaystyle=a(2)=3$
	$\displaystyle a(b(3))$	$\displaystyle=a(4)=1$

and so $ab=(1,2,4,5,3)$ .