If $\sigma = (a_1,a_2,\ldots,a_k)$, then the order of $\sigma$ is $k$ because $\sigma^k = Id$. I've tried finding a proof on the internet, but all sources just say "it's clear that", etc. I'm probably missing something really obvious. Can anyone tell me why this is?

Edit: I understand the intuition --- what I'm struggling with is a proof, a formal understanding of why this is true.

  • 2
    $\begingroup$ Can you write down what $\sigma^2,\,\sigma^3$ do? $\endgroup$ – Daniel Fischer Feb 12 '14 at 12:31
  • $\begingroup$ Sure, and I intuitively know why $\sigma^k = Id$, but what I'm struggling with is a formal proof or understanding of why this works. $\endgroup$ – Newb Feb 12 '14 at 12:34
  • $\begingroup$ I'd personally draw a picture. Have The elements $a_1,\ldots, a_k$ at the top and the bottom and draw lines between the $a_i$ at the top and $\sigma(a_i)$ at the bottom. Now repeat this for $k$ rows of connecting intervals. If you follow any path, you will see that you end up back at the start. This is for intuition, not so much a formal proof. $\endgroup$ – Dan Rust Feb 12 '14 at 12:38
  • 2
    $\begingroup$ You prove by induction that $\sigma^n(a_{r}) = a_{r+n}$ for $1 \leqslant r \leqslant k$, where the addition is done modulo $k$. And of course that $\sigma^n(b) = b$ for $b\notin \{ a_r : 1\leqslant r \leqslant k\}$. Then you see that $\sigma^n \neq \operatorname{id}$ for $1 \leqslant n \leqslant k$. $\endgroup$ – Daniel Fischer Feb 12 '14 at 12:39

Denote $\sigma=(a_0,a_1,\ldots,a_{k-1})$ (to simplify notation later on).

Proposition: for all $n\in\Bbb N$ and $j\in\Bbb Z/k\Bbb Z$ it holds that $\sigma^n(a_j)=a_{j+n\pmod{k}}$.

Proof: by induction, since trivally $\sigma(a_{j+n\pmod{k}})=a_{j+n+1\pmod{k}}$.

Now note that by our proposition $\sigma^k=\mathrm{Id}$, and for all $j<k$ we have $\sigma^j\ne\mathrm{Id}$.

  • $\begingroup$ @DanielFischer: you got there first (yet again! ;)) $\endgroup$ – Jonathan Y. Feb 12 '14 at 12:47

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.