2.12 Cycles

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,\mathrm{\dots },a_m$ be distinct positive integers. Then

$$a=(a_1,\mathrm{\dots },a_m)$$

is defined to be the permutation such that

• •

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

• •

  $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⩽i⩽m$.

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⩾3$. When it matters, we will make this clear.

The picture below is of the 5-cycle $(1,2,3,4,5)$, illustrating why these permutations are called “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

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:

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

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.

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\ne t\circ s$. You will prove this in the problem sets for MATH0005, but we’ll record it here for future use.

There can be many different ways to write a given permutation as a product of disjoint cycles. For example, letting ,

	$s$	$=(1,7,4)(2,3)(5)(6,9,8)$
		$=(7,4,1)(2,3)(6,9,8)$
		$=(2,3)(6,9,8)(7,4,1)$
		$=\mathrm{\dots }$

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

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

$$a=(a_1,\mathrm{\dots },a_m)$$

Then $a$ sends $a_i$ to $a_{i+1}$ for all $1⩽i⩽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⩽i⩽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},\mathrm{\dots },a_2,a_1)$:

$${(a_1,\mathrm{\dots },a_m)}^{-1}=(a_m,a_{m-1},\mathrm{\dots },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.”

Not every permutation is a cycle.

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.