Here's what I have right now:

The order of a $k$-cycle in $S_n$ is $k$.

Proof. Let $\sigma$ represent the $k$-cycle $$\sigma=(x_1 \ x_2 \ \cdots \ x_k)$$with distinct elements $x_i$. Note that the cycle of distinct $x_i$ implies $k \leq n$. There are two cases to consider: $k$ even and $k$ odd. Suppose $k$ is even. It follows that $$\sigma^2=(x_1 \ x_2 \ \cdots \ x_k)(x_1 \ x_2 \ \cdots \ x_k)=(x_1 \ x_3 \ \cdots \ x_{k-1})(x_2 \ x_4 \ \cdots \ x_k)$$ $$\sigma^3=(x_1 \ x_2 \ \cdots \ x_k)\left[(x_1 \ x_3 \ \cdots \ x_{k-1})(x_2 \ x_4 \ \cdots \ x_k) \right]$$ $$=(x_1 \ x_4 \ \cdots \ x_{k-2})(x_2 \ x_5 \ \cdots \ x_{k-1})(x_3 \ x_6 \ \cdots \ x_k).$$ Thus, we can construct the general formula as a product of disjoint cycles $$\sigma^j=\prod_{i=1}^{j} (x_i \ x_{i+j} \ x_{i+2j}\ \cdots \ x_{k-j+i})$$ where $k$ is even. Now suppose $k$ is odd. Then $$\sigma^2=(x_1 \ x_2 \ \cdots \ x_k)(x_1 \ x_2 \ \cdots \ x_k)=(x_1 \ x_3 \ \cdots \ x_{k-2} \ x_k \ x_2 \ x_4 \ \cdots \ x_{k-1})$$ which differs from the case when $k$ is even. Interestingly, $$\sigma^3=(x_1 \ x_2 \ \cdots \ x_k)\left[(x_1 \ x_3 \ \cdots \ x_{k-2} \ x_k \ x_2 \ x_4 \ \cdots \ x_{k-1}) \right]$$ $$=(x_1 \ x_4 \ \cdots \ x_{k-2})(x_2 \ x_5 \ \cdots \ x_{k-1})(x_3 \ x_6 \ \cdots \ x_k)$$ which gives the same result as $k$ even. The reader can verify that all $\sigma^{j>2}$ are equal for $k$ even and $k$ odd. Thus, the general formula can be revised: $$\sigma^{j>2}=\prod_{i=1}^{j} (x_i \ x_{i+j} \ x_{i+2j} \ \cdots \ x_{k-j+i})$$ where $k>2$. For the case $k=2$, the $k$-cycle is a transposition which, by definition, has order 2. For the case $k=1$, the permutation is trivially the identity which has order 1. Thus, the theorem holds for $k=1,2$. For $k>2$, we know $$\sigma^{k}=\prod_{i=1}^{k} (x_i \ x_{i+k} \ x_{i+2k}\ \cdots \ x_{(k-k)+i}).$$ But for $n>0$ we see that $i+nk>k$ so it is not in the permutation. Thus, we simplify the above equation to $$\sigma^{k}=\prod_{i=1}^{k} (x_i)=e$$ We conclude that the order of a $k$-cycle in $S_n$ is $k$. QED.

The glaring problem seems to be my poor construction of the general case$$\sigma^{j>2}=\prod_{i=1}^{j} (x_i \ x_{i+j} \ x_{i+2j}\ \cdots \ x_{k-j+i})$$ which I considered replacing with$$\sigma^{j>2}=\prod_{i=1}^{j} (x_{i \bmod{j}})$$ but then I thought using this form is just as unenlightening as my original representation. I am just trying to convey that each disjoint cycle can only contain the elements $x_{i\leq k}$. A problem with using the $(x_{i \bmod{j}})$ notation is that we can run into a problem where elements of the form $x_{k<i\leq n}$ start appearing. Can you offer an elegant solution to this?

Also, I would appreciate advice on improving vague statements like this: "But for $n>0$ we see that $i+nk>k$ so it is not in the permutation." There are several lame statements like that in my proof that I just couldn't improve. I need help rewriting this proof in the most clear and concise manner.

Thank you!

  • $\begingroup$ I don't think disjoint cycles are all that useful, here, as any given $k$ could have many divisors, making the cycle types of powers of $\sigma$ hard to express "universally". $\endgroup$ – David Wheeler Feb 25 '15 at 10:49

Unfortunately, I can't quite grasp where $i + nk$ is coming from, as I thought we were manipulating subscripts modulo $k$. If subscripts are computed modulo $k$, then the cycle $(x_i, x_{i + k}, \ldots, x_{i + (k-k)})$ must be the 1-cycle $(x_i)$, since $i \equiv_k i + k$. In this case, you can conclude that $\sigma^k = e$, without mentioning $i + nk$.

You had me up to there, but I'm just not sure how you bring it all together. You definitely figured out a lot about the structure of $\sigma^m$, which means there's a more direct route find the order of the $k$-cycle $\sigma$.

Personally, I would use the fact that your permutation $\sigma = (x_1 x_2 \ldots x_k)$ is in the symmetric group $S_n$, which acts on the set $[n] = \{1, 2, \ldots, n\}$.

So, we could show that if we apply the map $\sigma: [n] \to [n]$ exactly $k$ times to any $i \in [n]$, then we wind up back at $i$; that is, $\sigma^k(i) = i$, and that $\sigma^m \neq e$ when $m < k$ and $k > 1$.

For $i \notin \{x_1, \ldots, x_k\}$, $\sigma^k(i)$ is clearly $i$, since $\sigma(i) = i$.

Otherwise, we know that $\sigma(x_j) = x_{j+1}$, with subscripts computed mod $k$, as you pointed out. It follows that $\sigma^m(x_i) = x_{i + m}$, which will be $x_i$ only when $m = k$, since the subscripts are computed mod $k$ and $x_i \neq x_j$ whenever $i \not\equiv_k j$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.