# 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 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 such that $s^{p}(i)=s^{q}(i)$ then we’d have $s^{q-p}(i)=i$ and $0 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. 1.

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

2. 2.

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

3. 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)$.