Powers of Cycles

Because the associative law holds, it makes sense to write something like $P^n$ where $P$ is a permutation and $n$ is a positive integer. $P^4 = PPPP$, 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 $P^3$, where $P = (1 3 4)(2 5)$.

$$P^3 = PPP = (1 3 4)(2 5)(1 3 4)(2 5)(1 3 4)(2 5) = (2 5).$$

In fact, it's easy to see how powers work on cycles. Let's look at $P = (1 2 3 4 5 6)$, for example. Here are the various powers of $P$:

$P^1 = (1 2 3 4 5 6)$	$P^2 = (1 3 5)(2 4 6)$	$P^3 = (1 4)(2 5)(3 6)$
$P^4 = (1 5 3)(2 6 4)$	$P^5 = (1 6 5 4 3 2)$	$P^6 = (1)$

When raising a cycle to a power $k$, each elements ``steps forward'' by $k$ steps, cycling back to the beginning, if necessary. It's just like modular (clock) arithmetic. Clearly if the cycle $P$ is $n$ items long, then $P^n = (1) = e$.

It's a great exercise to calculate $P^k$ for all powers of $k$, where $P$ is a cycle whose length is a prime number. Try it with $P = (1 2 3 4 5 6 7)$ and calculate $P^1$, $P^2$, $P^3$, $P^4$, $P^5$, $P^6$, and $P^7$.

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,

$$[(1 2 3)(4 5)]^3 = (1 2 3)(4 5)(1 2 3)(4 5)(1 2 3)(4 5),$$

but the $(1 2 3)$ and the $(4 5)$ cycles commute, so the right hand side can be rearranged to be:

$$\begin{eqnarray*}[(1 2 3)(4 5)]^3 &=& (1 2 3)(1 2 3)(1 2 3)(4 5)(4 5)(4 5) \\ &=& (1 2 3)^3(4 5)^3. \end{eqnarray*}$$

Clearly, if $P$ is a cycle of length $n$, then $P^n = e$ 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 $P$ 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 $P$ is not a cycle, but is written in proper cycle form, then the order of $P$ is the least common multiple of the cycle lengths. This is pretty obvious--consider the permutation $P = (1 2 3 4 5)(6 7 8)$. If we consider that $P^n = (1 2 3 4 5)^n(6 7 8)^n$, then to make $P^n = e$, we must have that both $(1 2 3 4 5)^n = e$ and $(6 7 8)^n = e$. The first will be true if $n$ is a multiple of 5; the second if $n$ is a multiple of $3$. For both to be true, $n$ 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.