The order of a cycle in a symmetric group is its length

Prove that if \sigma is the m-cycle (a_1 a_2 \ldots a_m), then for all i \in \{ 1, 2, \ldots, m \}, \sigma^i(a_k) = a_q, where q is the least positive residue of k+i mod m. Deduce that |\sigma| = m.


We proceed by induction on i. Note that the least positive residue of a mod b is precisely the (unique) remainder r satisfying 0 \leq r < |b|, given a = qb + r by the Division Algorithm.

The base case i = 1 follows from the definition of cycle notation; either k+1 < m, so \sigma(a_k) = a_{k+1} and we have k+1 = 0 \cdot m + (k+1), or k+1 = m, so that \sigma(a_k) = a_1 and we have k+1 = 1 \cdot m + 0.

Now suppose the conclusion holds for 1 and for some n with 1 \leq n < m. Then we have \sigma^{n+1}(a_k) = \sigma(\sigma^n(a_k)) = \sigma(a_p) = a_q, where p is the least positive residue of k+n mod m, and q the least positive residue of p+1 mod m; say k+n = g \cdot m + p with 0 \leq p < |m| and p+1 = h \cdot m + q with 0 \leq h < |m|. Solving the second equation for p and substituting into the first, we have k+n+1 = (h-g) \cdot m + q, and by the uniqueness part of the Division Algorithm, q is in fact the least positive residue of k+n+1 mod m. Thus, by induction, the conclusion holds for all 1 \leq n \leq m.

Note in particular that \sigma^m(a_k) = a_k for all 1 \leq k \leq m; hence \sigma^m = 1. Moreover, if 1 \leq i < m, \sigma^i \neq 1 since in particular, \sigma^i(a_1) = a_{1+i}; if a_1 = a_{1+i} then we have i = 0 mod m, a contradiction. Hence |\sigma| = m.

Post a comment or leave a trackback: Trackback URL.

Comments

  • Shreya Sharma  On September 30, 2010 at 3:39 am

    How is k+1 = 1.m + 1, when k+1 = m?

    • nbloomf  On September 30, 2010 at 7:35 am

      Oops- that was a typo. Thanks!

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: