Every equals a product of disjoint cycles.
Choose a number and form the sequence . Since these numbers belong to the set not all of them can repeat, that is, there exist such that , and so . Choose the smallest positive number such that . Then all of the numbers
(2.4) |
are different, since if there were numbers such that then we’d have and contradicting being the smallest such power. Observe that, on the numbers (2.4), behaves exactly like the -cycle .
If there is a number that doesn’t belong to this cycle, we can repeat the procedure above to get another cycle containing and such that does the same thing as the cycle to its elements. This will be disjoint from the previous one since if for some then which belongs to the previous cycle, contradicting the choice of .
By repeating this procedure until there are no longer any numbers between 1 and not contained in one of our disjoint cycles; the product of these is . ∎
An expression for a permutation as a product of disjoint cycles , , …,
is called a disjoint cycle decomposition of .
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.
To find a disjoint cycle decomposition for an element of :
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 are in one of your cycles, stop, else go back to step 1.
Let . 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 . Now we pick another number not in a cycle, say 2. sends 2 to 6, 6 to 5, and 5 to 2. That’s another cycle, so we have . Now we pick another number not yet in a cycle — the only one left is 3. sends 3 to 3, so this is immediately a cycle. We have .
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 from disjoint cycle decompositions, so we’d write the permutation of the previous example as .
Let’s work out a disjoint cycle decomposition for where
are elements of .
Remember that means do , then do . Keeping that in mind, all we have to do is follow the instructions from before. Start with 1:
…and we have our first cycle, . Continuing with a number not yet in a cycle, say 3, we get
…and we have our next cycle, . There are no numbers left, so
You should now find a disjoint cycle decomposition for . You’ll find that it has two 4-cycles again, but isn’t the same as the decomposition we got for .
Let’s find a disjoint cycle decomposition for . Write . Starting with 1 as usual,
and so .