2 Sets and functions 2.12 Inverses and composition 2.14 Products of disjoint cycles

2.13 Cycles

2.13.1 Cycle definition and notation

We’re going to introduce a more efficient way of writing permutations. This involves thinking about a special kind of permutation called a cycle.

Let $m>0$ , let $a_{0},\ldots,a_{m-1}$ be distinct positive integers. Then

a=(a_{0},\ldots,a_{m-1})

is defined to be the permutation such that

•

$a(a_{i})=a_{i+1}$ for $i<m-1$ ,
•

$a(a_{m-1})=a_{0}$ , and
•

$a(x)=x$ for any number $x$ which isn’t equal to one of the $a_{i}$ .

If we let $a_{m}$ be $a_{0}$ then we could just say $a(a_{i})=a_{i+1}$ for all $i$ .

Definition 2.13.1.

A permutation of the form $(a_{0},\ldots,a_{m-1})$ is called an $m$ -cycle. A permutation which is an $m$ -cycle for some $m$ is called a cycle.

There are two important things to note:

•

Any 1-cycle, e.g. $(1)$ or $(2)$ , is equal to the identity permutation.
•

If we just write down the cycle $(1,2,3)$ , say, it could be could be an element of $S_{3}$ , or $S_{4}$ , or $S_{5}$ , or any other $S_{n}$ with $n\geqslant 3$ . When it matters, we will make this clear.

Example 2.13.1.

•

In $S_{3}$ , the 2-cycle $(1,2)$ is the permutation that sends 1 to 2, 2 to 1, and 3 to 3. In two row notation $(1,2)=\begin{pmatrix}1&2&3\\ 2&1&3\end{pmatrix}$ .
•

In $S_{4}$ , the 3-cycle $(2,4,3)$ is the permutation that sends 1 to 1, 2 to 4, 4 to 3, and 3 to 2. In two row notation, $(2,4,3)=\begin{pmatrix}1&2&3&4\\ 1&4&2&3\end{pmatrix}$ .

The picture below is of the 5-cycle $(1,2,3,4,5)$ , illustrating why these permutations are called “cycles”.

Figure 2.14: Picture of the 5-cycle (1,2,3,4,5). The numbers 1, 2, 3, 4, 5 are arranged in a circle with an arrow pointing from 1 to 2, 2 to 3, 3 to 4, 4 to 5, 5 back to 1

2.13.2 Composing cycles

Let’s compose two cycles. Let $s=(1,2,3,4,5),t=(4,3,5,1)$ be elements of $S_{5}$ . We’ll work out the two row notation for $s\circ t$ . Remember that this is the permutation whose rule is to do $t$ then do $s$ .

$t(1)=4$ , so $s(t(1))=s(4)=5$ . Therefore the two row notation for $s\circ t$ looks like.

\begin{pmatrix}1&2&3&4&5\\ 5&?&?&?&?\end{pmatrix}

Next, $t(2)=2$ (as 2 doesn’t appear in the cycle defining $t$ ), so $s(t(2))=s(2)=3$ . Now we know the next bit of the two row notation:

\begin{pmatrix}1&2&3&4&5\\ 5&3&?&?&?\end{pmatrix}

You should continue this procedure and check that what you end up with is

s\circ t=\begin{pmatrix}1&2&3&4&5\\ 5&3&1&4&2\end{pmatrix}.

2.13.3 Multiple ways to write the same cycle

Example 2.13.2.

Consider the two cycles $a=(1,2,3,4)$ and $b=(2,3,4,1)$ . The permutation $a$ sends 1 to 2, 2 to 3, 3 to 4, 4 to 1, and any other number to itself. So does $b$ . So $a=b$ . Similarly if $c=(3,4,1,2)$ and $d=(4,1,2,3)$ then $a=b=c=d$ .

In general, every $m$ -cycle can be written $m$ different ways since you can put any one of the $m$ things in the cycle first.

Example 2.13.3.

In $S_{5}$ ,

(5,3,2)=(3,2,5)=(2,5,3).

2.13.4 Disjoint cycles

Definition 2.13.2.

Two cycles $(a_{0},\ldots,a_{m-1})$ and $(b_{0},\ldots,b_{k-1})$ are disjoint if no $a_{i}$ equals any $b_{j}$ .

Example 2.13.4.

•

$(1,2,7)$ is disjoint from $(5,4)$
•

$(1,2,3)$ and $(3,5)$ are not disjoint.

One reason disjoint cycles are important is that disjoint cycles commute, that is, if $a$ and $b$ are disjoint cycles then $a\circ b=b\circ a$ . This is special as you have seen that in general, for two permutations $s$ and $t$ , $s\circ t\neq t\circ s$ . You will prove this in the problem sets for MATH0005, but we’ll record it here for future use.

Theorem 2.13.1.

Let $a$ and $b$ be disjoint cycles. Then $ab=ba$ .

2.13.5 Non-uniqueness

There can be many different ways to write a given permutation as a product of disjoint cycles. For example, taking the permutation $s$ we’ve just seen,

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

It is important to remember are that an $m$ -cycle can be written in $m$ different ways, for example $(1,2,3)=(2,3,1)=(3,1,2)$ , and that disjoint cycles commute, for example $(1,2)(3,4)=(3,4)(1,2)$ .

2.13.6 Inverse of a cycle

For every permutation $s$ there is an inverse permutation $s^{-1}$ such that $s\circ s^{-1}=s^{-1}\circ s=\operatorname{id}$ . How do we find the inverse of a cycle? Let

a=(a_{0},\ldots,a_{m-1})

Then $a$ sends $a_{i}$ to $a_{i+1}$ for all $i$ (and every number not equal to an $a_{i}$ to itself), so $a^{-1}$ should send $a_{i+1}$ to $a_{i}$ for all $i$ (and every number not equal to an $a_{i}$ to itself). In other words, $a^{-1}$ is the cycle $(a_{m-1},a_{m-2},\ldots,a_{1},a_{0})$ :

(a_{0},\ldots,a_{m-1})^{-1}=(a_{m-1},a_{m-2},\ldots,a_{1},a_{0})

As a special case, the inverse of the 2-cycle $(i,j)$ is $(j,i)$ . But $(i,j)=(j,i)$ ! So every 2-cycle is its own inverse.

If we draw cycles as we did in Figure 2.14, their inverses are obtained by “reversing the arrows.”

Figure 2.15: On the left is a diagram showing the numbers 1, 2, and 3 in a cycle with an arrow from 1 to 2, 2 to 3, and 3 to 1 illustrating the 3-cycle

(1,2,3)

. On the right is its inverse

(3,2,1)

, the same picture with the arrows reversed

2.13.7 Not all permutations are cycles

Not every permutation is a cycle.

Example 2.13.5.

The permutation $\sigma=\begin{pmatrix}1&2&3&4\\ 2&1&4&3\end{pmatrix}$ is not a cycle. Suppose for a contradiction that it was. $\sigma$ sends 1 to 2, and 2 to 1, so if it were a cycle it would have to be $(1,2)$ . But $(1,2)$ sends 3 to 3, whereas $\sigma(3)=4$ , so $\sigma\neq(1,2)$ .

Here is a diagram of the permutation $\sigma$ from the previous example.

Figure 2.16: Picture of the permutation sending 1 to 2, 2 to 1, 3 to 4, and 4 to 3. Arrows indicate where each number is sent.

While $\sigma$ is not a cycle, it is the composition of two cycles: $\sigma=(1,2)\circ(3,4)$ . In fact, every permutation can be written this way, which we’ll prove in the next section.