Next: The Befuddler'' Notation Up: Combining Permutations Previous: Combining Permutations

## Powers of Cycles

Because the associative law holds, it makes sense to write something like where is a permutation and is a positive integer. , and because the operation of permutation multiplication is associative, you get the same answer no matter how you choose to multiply them together.

For example, let's compute , where .

In fact, it's easy to see how powers work on cycles. Let's look at , for example. Here are the various powers of :

When raising a cycle to a power , each elements steps forward'' by steps, cycling back to the beginning, if necessary. It's just like modular (clock) arithmetic. Clearly if the cycle is items long, then .

It's a great exercise to calculate for all powers of , where is a cycle whose length is a prime number. Try it with and calculate , , , , , , and .

If a permutation is written in proper cycle form where there is possibly more than one cycle, but there are no items that appear in more than one cycle, then taking powers of such a permutation is easy--just raise the individual cycles to the power and combine the results. This is because individual cycles that do not share items do commute, so, for example,

but the and the cycles commute, so the right hand side can be rearranged to be:

Clearly, if is a cycle of length , then because each application of the cycle moves all the elements in the cycle one step forward. For any permutation, we say that the order of the permutation is the smallest power of that permutation that is the identity. Thus if is a cycle of 17 elements, it will have order 17, since 17 applications of it will return every ball to its original box.

If is not a cycle, but is written in proper cycle form, then the order of is the least common multiple of the cycle lengths. This is pretty obvious--consider the permutation . If we consider that , then to make , we must have that both and . The first will be true if is a multiple of 5; the second if is a multiple of . For both to be true, must be a multiple of both 5 and 3, and the smallest number that is both is the least common multiple of the two: 15 in this case.

Next: The Befuddler'' Notation Up: Combining Permutations Previous: Combining Permutations
Zvezdelina Stankova-Frenkel 2000-10-04