# 2.12 Cycles

## 2.12.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_{1},\ldots,a_{m}$ be distinct positive integers. Then

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

is defined to be the permutation such that

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

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

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

Remember that a permutation is a speical kind of function, so the notation $a(a_{i})$ means ‘apply the function $a$ to the number $a_{i}$.’ If we let $a_{m+1}$ be $a_{1}$ then we could just say $a(a_{i})=a_{i+1}$ for all $1\leqslant i\leqslant m$.

###### Definition 2.12.1.

A permutation of the form $(a_{1},\ldots,a_{m})$ 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 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.12.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”.

## 2.12.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.12.3 Multiple ways to write the same cycle

###### Example 2.12.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.12.3.

In $S_{5}$,

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

## 2.12.4 Disjoint cycles

###### Definition 2.12.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.12.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.12.1.

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

## 2.12.5 Non-uniqueness

There can be many different ways to write a given permutation as a product of disjoint cycles. For example, letting $s=\begin{pmatrix}1&2&3&4&5&6&7&8&9\\ 7&3&2&1&7&9&4&6&8\end{pmatrix}$,

 $\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.12.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_{1},\ldots,a_{m})$

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

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

As a special case, the inverse of the 2-cycle $(i,j)$ is $(j,i)$. But $(i,j)=(j,i)$, so in fact 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.”

## 2.12.7 Not all permutations are cycles

Not every permutation is a cycle.

###### Example 2.12.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.

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.