# 2.14 Products of disjoint cycles

## 2.14.1 Every permutation is a product of disjoint cycles

To prove the theorem in the section title, we need a lemma on multiplying permutations.

###### Lemma 2.14.1.

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

 $(a_{0},a_{1})(a_{1},a_{2},\ldots,a_{m})=(a_{0},a_{1},\ldots,a_{m}).$

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_{0},a_{1},\ldots,a_{m})$ $\displaystyle t$ $\displaystyle=(a_{0},a_{1})$ $\displaystyle s$ $\displaystyle=(a_{1},a_{2},\ldots,a_{m})$

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 $0\leqslant i\leqslant m$.

• Let $i=0$. Then $r(a_{0})=a_{1}$, and $s(a_{0})=a_{0}$ and $t(a_{0})=a_{1}$ so $t(s(a_{0}))=a_{1}=r(a_{0})$.

• Let $i=1$, so $r(a_{1})=a_{2}$. We have $s(a_{1})=a_{2}$ and $t(a_{2})=a_{2}$, so $t(s(a_{1}))=a_{2}=r(a_{1})$.

• Let $2\leqslant i, 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})=a_{0}$, $s(a_{m})=a_{1}$, $t(a_{1})=a_{0}$, so $t(s(a_{m}))=a_{0}=r(a_{m})$. ∎

###### Theorem 2.14.2.

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

###### Proof.

By induction on $n$. It is certainly true for $n=1$ when the only permutation in $S_{1}$ is the identity (which equals the one-cycle $(1)$) and for $n=2$ when the only two permutations are the identity and $(1,2)$.

Now let $s\in S_{n}$ and suppose that every permutation in $S_{n-1}$ is a product of disjoint cycles. If $s(n)=n$ then we can consider $s$ as a permutation of $1,2,\ldots,n-1$, so it equals a product of disjoint cycles by the inductive hypothesis. If $s(n)$ is equal to something other than $n$, say $s(n)=k$, then consider the permutation

 $t=(n,k)\circ s.$

$t(n)=n$, so we can consider $t$ as a permutation in $S_{n-1}$ and therefore by induction we can write $t$ as a product of disjoint cycles

 $t=c_{1}c_{2}\cdots c_{r}.$

where the cycles $c_{1},\ldots,c_{r}$ only contain the numbers $1,2,\ldots,n-1$.

Since $(n,k)(n,k)$ is the identity permutation, we can compose both sides of the previous equation on the left with $(n,k)$ to get

 $\displaystyle(n,k)(n,k)s$ $\displaystyle=(n,k)c_{1}c_{2}\cdots c_{r}$ $\displaystyle s$ $\displaystyle=(n,k)c_{1}c_{2}\cdots c_{r}.$

None of the cycles $c_{i}$ contain $n$. If none of them contain $k$ then this is an expression for $s$ as a product of disjoint cycles, so we are done. If one of them contains $k$, then because disjoint cycles commute by Theorem 2.13.1 we can assume that it is $c_{1}$. 44 4 For example, if $s=(n,k)c_{1}c_{2}c_{3}$ and $c_{2}$ was the cycle containing $k$, you could use the fact that $c_{1}c_{2}=c_{2}c_{1}$ to get $s=(n,k)c_{2}c_{1}c_{3}$ and then just renumber the cycles.

Recall from 2.13.3 that we can write $c_{1}$ starting with any one of its elements. We choose to write it starting with $k$, so that for some numbers $a_{1},\ldots,a_{m}$

 $c_{1}=(k,a_{1},\ldots,a_{m}).$

By Lemma 2.14.1,

 $\displaystyle(n,k)c_{1}$ $\displaystyle=(n,k)(k,a_{1},\ldots,a_{m})$ $\displaystyle=(n,k,a_{1},\ldots,a_{m})$

and therefore

 $s=(n,k,a_{1},\ldots,a_{m})c_{2}c_{3}\cdots c_{r}.$

This is a product of disjoint cycles since neither $k$ nor $n$ belongs to any of $c_{2},\ldots,c_{r}$, so we are done. ∎

###### Definition 2.14.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.14.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.14.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.13.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.14.3 Composing permutations given as products of disjoint cycles

###### Example 2.14.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 do $\tau\sigma$ now. You’ll find that your disjoint cycle decomposition has two 4-cycles again, but isn’t the same as the decomposition we got for $\sigma\tau$.

###### Example 2.14.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)$.