Every $s\mathrm{\in}{S}_{n}$ equals a product of disjoint cycles.
Choose a number $i$ and form the sequence $i,s(i),{s}^{2}(i),\mathrm{\dots}$. Since these numbers belong to the set $\{1,2,\mathrm{\dots},n\}$ not all of them can repeat, that is, there exist $$ such that ${s}^{p}(i)={s}^{q}(i)$, and so ${s}^{q-p}(i)=i$. Choose the smallest positive number $r$ such that ${s}^{r}(i)=i$. Then all of the numbers
$$i,s(i),{s}^{2}(i),\mathrm{\dots},{s}^{r-1}(i)$$ | (2.4) |
are different, since if there were numbers $$ such that ${s}^{p}(i)={s}^{q}(i)$ then we’d have ${s}^{q-p}(i)=i$ and $$ contradicting $r$ being the smallest such power. Observe that, on the numbers (2.4), $s$ behaves exactly like the $r$-cycle $(i,s(i),\mathrm{\dots},{s}^{r-1}(i))$.
If there is a number $j\in \{1,2,\mathrm{\dots},n\}$ that doesn’t belong to this cycle, we can repeat the procedure above to get another cycle containing $j$ and such that $s$ does the same thing as the cycle to its elements. This will be disjoint from the previous one since if ${s}^{p}(j)={s}^{q}(i)$ for some $p,q$ then $j={s}^{q-p}(i)$ which belongs to the previous cycle, contradicting the choice of $j$.
By repeating this procedure until there are no longer any numbers between 1 and $n$ not contained in one of our disjoint cycles; the product of these is $s$. ∎
An expression for a permutation $s$ as a product of disjoint cycles ${c}_{1}$, ${c}_{2}$, …, ${c}_{r}$
$$s={c}_{1}{c}_{2}\mathrm{\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)=\mathrm{\cdots}$$ |
To find a disjoint cycle decomposition for an element of ${S}_{n}$:
Pick a number that doesn’t yet appear in a cycle.
Compute its image, and the image of that, and so on, until you have a cycle. Write down that cycle.
If all elements of $1,\mathrm{\dots},n$ are in one of your cycles, stop, else go back to step 1.
Let $s=\left(\begin{array}{ccccccc}1& 2& 3& 4& 5& 6& 7\\ 7& 6& 3& 1& 2& 5& 4\end{array}\right)$. 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.12.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)$.
Let’s work out a disjoint cycle decomposition for $\sigma \tau $ where
$\sigma $ | $=(4,2,6,1,5)$ | ||
$\tau $ | $=(5,4,7,3,8)$ |
are elements of ${S}_{8}$.
Remember that $\sigma \mathbf{}\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:
$\sigma (\tau (1))$ | $=\sigma (1)=5$ | ||
$\sigma (\tau (5))$ | $=\sigma (4)=2$ | ||
$\sigma (\tau (2))$ | $=\sigma (2)=6$ | ||
$\sigma (\tau (6))$ | $=\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
$\sigma (\tau (3))$ | $=\sigma (8)=8$ | ||
$\sigma (\tau (8))$ | $=\sigma (5)=4$ | ||
$\sigma (\tau (4))$ | $=\sigma (7)=7$ | ||
$\sigma (\tau (7))$ | $=\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 now find a disjoint cycle decomposition for $\tau \sigma $. You’ll find that it has two 4-cycles again, but isn’t the same as the decomposition we got for $\sigma \tau $.
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,
$a(b(1))$ | $=a(1)=2$ | ||
$a(b(2))$ | $=a(3)=4$ | ||
$a(b(4))$ | $=a(5)=5$ | ||
$a(b(5))$ | $=a(2)=3$ | ||
$a(b(3))$ | $=a(4)=1$ |
and so $ab=(1,2,4,5,3)$.