Now we may compose a permutation with itself arbitrarily many times:

The **order** of is the smallest positive integer *n* for which is the identity map (question: why must such an *n* exist?). It is customary to denote the order by or . It is clear that a cycle of length *d* also has order *d*.

Example: how many riffle shuffles on a stack of 10 cards will bring it back to the original permutation?

[ *We assume that the shuffle cuts the deck {a, b, … , j} into two equal stacks of 6 cards each, given by {a, b, …, e} and {f, g, …, j}, then intersperse the two stacks alternately to give {a, f, b, g, … e, j}. *]

To answer this question, we label the cards by {1,2,…,10} and observe that after one riffle shuffle, we get {1, 6, 2, 7, 3, 8, 4, 9, 5, 10}, i.e. the corresponding permutation is:

We represent this in pictorial form:

Hence, the order of the permutation is clearly given by the LCM of the lengths of the disjoint cycles, i.e. LCM(2, 6) = 6.

Inspired by this example, we have the following result:

Every permutation can be uniquely written as a product of *disjoint* cycles. The order of the permutation is then given by the LCM of the lengths of these disjoint cycles.

After the previous example, the proof should be quite obvious: pick an element, trace it around by letting the permutation act on it, this would give a cycle; from the remaining elements, pick another one, rinse, lather, repeat… . Furthermore, the proof is completely constructive.

### Like this:

Like Loading...

*Related*

Hi Dr. Lim,

The discussion on the existence of order reminds me of a standard olympiad problem:

Does there exist a Fibonacci number that ends in ’99’? in ‘999999’? in 1 billion ‘9’s?

Both problems can be solved by the Pigeonhole Principle: for this one, consider the first 10001 pairs of consecutive Fibonacci numbers , modulo 100. Since there are only 10000 possible ordered pairs of residues mod 100, one of these pairs must be identical, say and . Since each term of the Fibonacci sequence is uniquely determined by the 2 terms before it and the 2 terms after it, respectively, we can prove that the sequence is periodic mod 100. The remainder of the problem is easy (and left as an exercise?).

The same idea can be applied to show the existence of the order here, although (as pointed out in the original post) this approach only gives an upper bound and is not constructive. Notice that this approach doesn’t require “true” bijectivity (the Fibonacci example is a mapping from to and hence is not a bijection), but just some form of “uniqueness”…

Perhaps someone else with more higher mathematics background can share more insights on this? (Or perhaps this entire discussion is trivial to more experienced eyes?…)

Hi Yan Sheng.

That’s right: pigeonhole principle provides a quick proof of the finiteness of , without providing any bound to its order.

But take care to differentiate between “periodic” and “eventually periodic”. Applying pigeonhole principle gives us for some positive integers m > n. Thus giving for i=0,1,2,… , i.e. eventual periodicity.

To prove it is periodic, we need to be bijective, thus giving and hence period = m-n.

Anyway, if you’re given an explicit permutation, writing it as a product of disjoint cycles is the quickest way to compute its order.