6
$\begingroup$

Let $\sigma$ be a cycle with length $n$ where $\sigma \in S_m$.

How do i prove that $|\langle \sigma \rangle |$ is $n$?

$\endgroup$
  • $\begingroup$ Induction...? And then you may want to subdivide in odd and even lenghts... $\endgroup$ – DonAntonio Apr 20 '14 at 23:31
  • $\begingroup$ @DonAntonio Yes, I have tried to apply induction, but i can't find where to fix and do induction. $\endgroup$ – John. p Apr 20 '14 at 23:36
  • $\begingroup$ @DonAntonio Note that $(123)$ is a cycle of length 3 but $(123)^2$ is again a cycle of length 3 $\endgroup$ – John. p Apr 20 '14 at 23:38
  • $\begingroup$ Might be worth adding a clarifying note that "order" here means its order in the permutation group, i.e. the smallest $n$ such that $\sigma^n$ is the identity permutation. (Someone had proposed an edit to the question with wording like "order of the cycle generator", which I find even more confusing.) $\endgroup$ – ShreevatsaR Apr 20 '14 at 23:38
  • $\begingroup$ I know that, @John.p...and that's why I proposed to check odd and even ones separatedly. $\endgroup$ – DonAntonio Apr 20 '14 at 23:43
13
$\begingroup$

The order of a permutation $\sigma$ is the smallest positive integer $n$ such that $\sigma^n$ is the identity permutation. (This is sometimes a definition, sometimes a consequence of a different definition; I will assume it is known).

Now suppose we have an $n$-cycle $\sigma=(a_0\;a_1\;a_2\;a_3\ldots a_{n-1})$. Its order cannot be less than $n$, because if $0<k<n$ then $\sigma^k(a_0)=a_k$ and it's implicit in the concept of a cycle that $a_0\ne a_k$.

On the other hand, $\sigma^n$ is certainly the identity permutation, because it acts on each element of the cycle by moving it around the entire cycle one time. Formally one can prove (by induction) that $\sigma^k(a_j) = a_{(j+k)\bmod n}$, and since $n\equiv 0\pmod n$ we have $(j+n)\bmod n=j$ whenever $0\le j < n$. And elements that are not in the cycle at all are left alone by $\sigma$ and therefore also by $\sigma^n$.

Since $\sigma^n=e$ and $\sigma^k\ne e$ when $0<k<n$, the order of $\sigma$ is $n$.

(There's no need to divide into odd and even cases as Don Antonio suggests).

$\endgroup$
  • $\begingroup$ ''because it acts on each element of the cycle by moving it around the entire cycle one time.'' Aren't we assuming that $σ^k$ is one cycle for any k. Which is not the case ! What I'm missing? I just can't see how this observation is independent of whether the power and the number of elements are even or odd. $\endgroup$ – yousef magableh Nov 2 at 14:31
  • $\begingroup$ Although I did the induction proof and it doesn't require any assumption as you said, but I just feel it's just too easy to be true, where did the complexity of the problem go! Depending on the power you rais the permutation to you could have 1 or 2 or more disjoint cycles how is all that didn't appear in the induction proof! $\endgroup$ – yousef magableh Nov 2 at 15:16
  • 1
    $\begingroup$ @yousefmagableh: Each step in the iteration just applies the original cycle. In this part of the argument we don't worry about precisely what the grand-scale nature of $\sigma^k$ is, just that it brings everything back to its original position when $k=n$. $\endgroup$ – Henning Makholm Nov 2 at 18:17
1
$\begingroup$

For example: even length, so that we know that transpositions have order $\;2\;$ and any cycle of length less than $\;2n\;$ has the appropiate order, so that:

$$\sigma=(i_1\,i_2\,\ldots\,i_{2n})\implies \sigma^2=(i_1\,i_3\,\ldots\,i_{2n-1})(i_2\,i_4\,\ldots\,i_{2n})$$

But by the Inductive Hypothesis (IH), we have that

$$\text{ord}(i_1\,i_3\,\ldots\,i_{2n-1})=n=\text{ord}(i_2\,i_4\,\ldots\,i_{2n})$$

and since both $\;n$-cycles are disjoint (and thus they commute), we get

$$\sigma^{2n}=(\sigma^2)^n=(i_1\,i_3\,\ldots\,i_{2n-1})^n(i_2\,i_4\,\ldots\,i_{2n})^n=1$$

But...why can't the order be less than $ \;2n\;$ above? Because that'd mean one of the two $\;n$-cycles above has order less than $\;n\;$ ...

Try now a similar argument for the odd length case (I think it is simpler as you always get, upon exponentiation, again a cycle of the same length...!)

$\endgroup$
  • $\begingroup$ "I think it is simpler as you always get, upon exponentiation, again a cycle of the same length" - you don't. Try a cycle of length 9, taken to the third power. $\endgroup$ – user2357112 Apr 21 '14 at 11:26
  • $\begingroup$ Your argument that the order can't be less than $2n$ only shows that it can't be an even number less than $2n$. If the order were to be odd, then you wouldn't be able to convert $\sigma^{order}$ to a power of $\sigma^2$. Similarly, I don't think the argument generalizes to the odd-length case, especially the prime-length case, since no power of $\sigma$ will allow you to apply the inductive hypothesis. $\endgroup$ – user2357112 Apr 21 '14 at 11:33
  • $\begingroup$ I don't get the argument for 'why can't the order be less than $2n$ above? ' please someone explain me. $\endgroup$ – ramanujan Jun 30 '18 at 19:28

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.