Group Theory I.3 (Order of a Permutation)

Now we may compose a permutation \sigma \in S_n with itself arbitrarily many times:

\sigma, \sigma^2, \sigma^3, \ldots \in S_n.

The order of \sigma is the smallest positive integer n for which \sigma^n is the identity map (question: why must such an n exist?). It is customary to denote the order by |\sigma| or o(\sigma). 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:

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 6 & 2 & 7 & 3 & 8 & 4 & 9 & 5 & 10\end{pmatrix}.

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.

This entry was posted in Group Theory Notes and tagged , , , , , . Bookmark the permalink.

2 Responses to Group Theory I.3 (Order of a Permutation)

  1. Ang Yan Sheng says:

    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 (F_0,F_1), (F_1,F_2), \ldots, (F_{10000}, F_{10001}), modulo 100. Since there are only 10000 possible ordered pairs of residues mod 100, one of these pairs must be identical, say (F_i,F_{i+1}) and (F_j,F_{j+1}). 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 (\mathbb{Z} / 100\mathbb{Z})^2 to (\mathbb{Z} / 100\mathbb{Z}) 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?…)

    • limsup says:

      Hi Yan Sheng.

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

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

      To prove it is periodic, we need \sigma to be bijective, thus giving \sigma^{m-n} = id 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s