• Support PF! Buy your school textbooks, materials and every day products Here!

Show that the order of a cycle is the length of the cycle

  • #1
1,456
44

Homework Statement


Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \{1,2, \dots , m \}##, ##\sigma^i (a_k) = a_{k+i}##. Deduce that ##\sigma^m (a_k) = a_k##

Homework Equations




The Attempt at a Solution


I will try to do this by induction. Clearly, ##\sigma (a_k) = a_{k+1}##, as that is how ##\sigma## is defined. Now, suppose that for some ##n \in \mathbb{N}## ##\sigma^n (a_k) = a_{k+n}##. Then ##\sigma^{n+1} (a_k) = \sigma( \sigma^n (a_k) ) = \sigma (a_{k+n}) = \sigma_{a + k + 1} ##.

So I feel like I'm done, but I also feel that I've proved this statement for all ##i \in \mathbb{N}##, rather than for all ##i \in \{1,2, \dots , m \}##. How do I modify it to get it correct?
 

Answers and Replies

  • #2
12,643
9,161

Homework Statement


Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \{1,2, \dots , m \}##, ##\sigma^i (a_k) = a_{k+i}##. Deduce that ##\sigma^m (a_k) = a_k##

Homework Equations




The Attempt at a Solution


I will try to do this by induction. Clearly, ##\sigma (a_k) = a_{k+1}##, as that is how ##\sigma## is defined. Now, suppose that for some ##n \in \mathbb{N}## ##\sigma^n (a_k) = a_{k+n}##. Then ##\sigma^{n+1} (a_k) = \sigma( \sigma^n (a_k) ) = \sigma (a_{k+n}) = \sigma_{a + k + 1} ##.

So I feel like I'm done, but I also feel that I've proved this statement for all ##i \in \mathbb{N}##, rather than for all ##i \in \{1,2, \dots , m \}##. How do I modify it to get it correct?
It is correct and you've proven it for all ##n \in \mathbb{N}##. However, the question is poorly worded. It should have been ##\sigma^i (a_k) = a_{k+i~\operatorname{mod}m}## since ##\sigma(a_m)=a_1## and not ##a_{m+1}##. Hence the induction basis is already wrong without the modulo on the index.
 
  • #3
1,456
44
It is correct and you've proven it for all ##n \in \mathbb{N}##. However, the question is poorly worded. It should have been ##\sigma^i (a_k) = a_{k+i~\operatorname{mod}m}## since ##\sigma(a_m)=a_1## and not ##a_{m+1}##. Hence the induction basis is already wrong without the modulo on the index.
I see what you mean. But I'm still a little confused. Why was my induction where ##i \in \mathbb{N}## valid if it is states that ##i \in \{1,2, \dots , m \}##?
 
  • #4
12,643
9,161
I see what you mean. But I'm still a little confused. Why was my induction where ##i \in \mathbb{N}## valid if it is states that ##i \in \{1,2, \dots , m \}##?
If it's true for all natural numbers, then it's true for a few of them. The restriction to ##1 \leq i \leq m## comes into play as we don't have other indices. The modulo solves this problem. There is simply no ##a_{m+1}## in our cycle, so ##a_{k+i}## doesn't make sense if it exceeds ##m##. To place a modulo ##m## behind the index is the shortest way of saying ##\in \{\,1,\ldots ,m\,\}##. It's simply a sloppiness by whoever has written the text. Your induction is equally wrong without the modulo, as in case ##i=1## and ##k=m## we have ##\sigma^1(a_m) \neq a_{m+1}##. And with the modulo, we only need the numbers up to ##m##.
 
  • #5
1,456
44
If it's true for all natural numbers, then it's true for a few of them. The restriction to ##1 \leq i \leq m## comes into play as we don't have other indices. The modulo solves this problem. There is simply no ##a_{m+1}## in our cycle, so ##a_{k+i}## doesn't make sense if it exceeds ##m##. To place a modulo ##m## behind the index is the shortest way of saying ##\in \{\,1,\ldots ,m\,\}##. It's simply a sloppiness by whoever has written the text. Your induction is equally wrong without the modulo, as in case ##i=1## and ##k=m## we have ##\sigma^1(a_m) \neq a_{m+1}##. And with the modulo, we only need the numbers up to ##m##.
So would a less sloppy problem statement be

Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \mathbb{N}##, ##\sigma^i (a_{k \mod m}) = a_{k+i \mod m}##. Deduce that ##\sigma^m (a_{k \mod m}) = a_{k \mod m}## and so ##| \sigma | = m##.
 
  • #6
12,643
9,161
So would a less sloppy problem statement be

Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \mathbb{N}##, ##\sigma^i (a_{k \mod m}) = a_{k+i \mod m}##. Deduce that ##\sigma^m (a_{k \mod m}) = a_{k \mod m}## and so ##| \sigma | = m##.
Yes and no. Yes, because the index problem is solved, no because there is no need for the modulo in the notation as a variable of ##\sigma## since ##\sigma## is only defined modulo ##m##. To write ##\sigma^m (a_{k \mod m})## creates unnecessary confusion. But for the results, we have to make sure that the formula is defined! So the index of the result has to be wrapped around. For ##a_k## in the role of a variable, it has already been done the moment you wrote ##\sigma=(a_1,\ldots,a_m)##.
 
  • #7
1,456
44
Yes and no. Yes, because the index problem is solved, no because there is no need for the modulo in the notation as a variable of ##\sigma## since ##\sigma## is only defined modulo ##m##. To write ##\sigma^m (a_{k \mod m})## creates unnecessary confusion. But for the results, we have to make sure that the formula is defined! So the index of the result has to be wrapped around. For ##a_k## in the role of a variable, it has already been done the moment you wrote ##\sigma=(a_1,\ldots,a_m)##.
I think this is the last thing. What is the difference between the following two wordings of the question:

1) Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \{1,2, \dots , m \}##, ##\sigma^i (a_k) = a_{k+i}##, where ##k+i## is replaced by its least positive residue mod m.

2) Prove that if ##\sigma## is the m-cycle ##(a_1 ~a_2~ \dots ~ a_m)##, then for all ##i \in \mathbb{N}##, ##\sigma^i (a_k) = a_{k+i}##, where ##k+i## is replaced by its least positive residue mod m.
 
  • #8
12,643
9,161
Formally: the second implies the first; within the context: none. As ##\sigma^m=1##, with this information the two are equivalent, because all other exponents, even the negative ones, can be reduced to the case ##1\leq i \leq m##.
 
  • #9
1,456
44
Formally: the second implies the first; within the context: none. As ##\sigma^m=1##, with this information the two are equivalent, because all other exponents, even the negative ones, can be reduced to the case ##1\leq i \leq m##.
So if we were given problem statement 1), would the best thing be to prove 2) using induction and say clearly this implies 1 is true?

I ask this because it doesn't seem like you could do induction on ##i## formally if the variable isn't defined for all natural numbers.
 
  • #10
12,643
9,161
I ask this because it doesn't seem like you could do induction on ##i## formally if the variable isn't defined for all natural numbers.
But you did the induction on the exponent which is defined for all numbers!
 
  • #11
1,456
44
But you did the induction on the exponent which is defined for all numbers!
Doesn't the original statement say that ##i## only varies from 1 to m?
 
  • #12
12,643
9,161
Doesn't the original statement say that ##i## only varies from 1 to m?
O.k. in this case, it isn't an induction, but an "and so on". Or you use the induction and show it for all ##n##. The "and so on" case goes with dots: Let ##i \in \{\,1,\ldots ,m\,\}##, then
$$
\sigma^i(a_k)=\underbrace{\sigma(\sigma(\sigma(\ldots (\sigma}_{i \text{ times }}(a_k)\ldots )= \underbrace{\sigma(\sigma(\sigma(\ldots (\sigma}_{i-1 \text{ times }}(a_{k+1})\ldots )= \ldots = \underbrace{(\sigma)}_{1 \text{ times }}(a_{k+i-1})=a_{k+i}
$$
but the induction is nicer and covers the ##i## stated as it covers all ##n \in \mathbb{N}_0##.
 

Related Threads on Show that the order of a cycle is the length of the cycle

Replies
3
Views
510
  • Last Post
Replies
1
Views
9K
Replies
4
Views
414
Replies
3
Views
4K
  • Last Post
Replies
8
Views
2K
Replies
6
Views
418
Replies
1
Views
5K
  • Last Post
Replies
4
Views
4K
Replies
2
Views
751
  • Last Post
Replies
0
Views
824
Top