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},\mathrm{\dots},{a}_{m-1}$ be distinct positive integers. Then
$$a=({a}_{0},\mathrm{\dots},{a}_{m-1})$$ |
is defined to be the permutation such that
$a({a}_{i})={a}_{i+1}$ for $$,
$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$.
A permutation of the form $({a}_{0},\mathrm{\dots},{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\u2a7e3$. When it matters, we will make this clear.
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)=\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$.
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)=\left(\begin{array}{cccc}1& 2& 3& 4\\ 1& 4& 2& 3\end{array}\right)$.
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.
$$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& \mathrm{?}& \mathrm{?}& \mathrm{?}& \mathrm{?}\end{array}\right)$$ |
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:
$$\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 3& \mathrm{?}& \mathrm{?}& \mathrm{?}\end{array}\right)$$ |
You should continue this procedure and check that what you end up with is
$$s\circ t=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 3& 1& 4& 2\end{array}\right).$$ |
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.
In ${S}_{5}$,
$$(5,3,2)=(3,2,5)=(2,5,3).$$ |
Two cycles $({a}_{0},\mathrm{\dots},{a}_{m-1})$ and $({b}_{0},\mathrm{\dots},{b}_{k-1})$ are disjoint if no ${a}_{i}$ equals any ${b}_{j}$.
$(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\ne t\circ s$. You will prove this in the problem sets for MATH0005, but we’ll record it here for future use.
Let $a$ and $b$ be disjoint cycles. Then $a\mathit{}b\mathrm{=}b\mathit{}a$.
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,
$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}_{0},\mathrm{\dots},{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},\mathrm{\dots},{a}_{1},{a}_{0})$:
$${({a}_{0},\mathrm{\dots},{a}_{m-1})}^{-1}=({a}_{m-1},{a}_{m-2},\mathrm{\dots},{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.”
Not every permutation is a cycle.
The permutation $\sigma =\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 4& 3\end{array}\right)$ 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 \ne (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.