2 Sets and functions 2.13 Cycles 2.15 Powers and orders

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<m$ , 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}$ . ⁴⁴ 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.

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