Finding the order of element of symmetric group

  • #1
1,462
44

Homework Statement


Let ##n## be a natural number and let ##\sigma## be an element of the symmetric group ##S_n##. Show that if ##\sigma## is a product of disjoint cycles of orders ##m_1 , \dots , m_k##, then ##|\sigma|## is the least common multiple of ##m_1 , \dots , m_k##.

Homework Equations




The Attempt at a Solution


So if I suppose that ##\sigma = c_1 c_2 \dots c_k## where ##|c_i| = m_i##, and ##|\sigma| = n##, then ##\sigma ^n = c_1^n \dots c_k^n = 1##. Now, if I could show that this implies that ##c_i^n = 1## then I would basically be done, but I am not sure how to do this. It's kind of "obvious" to me since after taking powers we still have disjoint cycles, and also since they're disjoint none of the disjoint cycles can be inverses of other possible compositions of other disjoint cycles, so they must all be the identity.
 

Answers and Replies

  • #2
14,413
11,726

Homework Statement


Let ##n## be a natural number and let ##\sigma## be an element of the symmetric group ##S_n##. Show that if ##\sigma## is a product of disjoint cycles of orders ##m_1 , \dots , m_k##, then ##|\sigma|## is the least common multiple of ##m_1 , \dots , m_k##.

Homework Equations




The Attempt at a Solution


So if I suppose that ##\sigma = c_1 c_2 \dots c_k## where ##|c_i| = m_i##, and ##|\sigma| = n##, then ##\sigma ^n = c_1^n \dots c_k^n = 1##.
Here you use the fact that disjoint cycles commute, and that for every element ##g## of a finite group ##G## we have ##g^{|G|}=1\,.## But why does ##n## has to be the order of ##\sigma\,?## Conversely if you define ##n:=\operatorname{ord}\sigma ## you shouldn't use the same letter as for ##G=S_n\,.##
Now, if I could show that this implies that ##c_i^n = 1## then I would basically be done, but I am not sure how to do this. It's kind of "obvious" to me since after taking powers we still have disjoint cycles, and also since they're disjoint none of the disjoint cycles can be inverses of other possible compositions of other disjoint cycles, so they must all be the identity.
I would start with ##m := \operatorname{lcm}(m_1,\ldots,m_k)## and show ##\sigma^m=1##, and that for any other ##k##, that is one which isn't a multiple of (w.l.o.g.) ##m_1##, i.e. ##k=qm_1+r_1## has a remainder, ##\sigma^k \neq 1\,.##
 
  • #3
1,462
44
Here you use the fact that disjoint cycles commute, and that for every element ##g## of a finite group ##G## we have ##g^{|G|}=1\,.## But why does ##n## has to be the order of ##\sigma\,?## Conversely if you define ##n:=\operatorname{ord}\sigma ## you shouldn't use the same letter as for ##G=S_n\,.##

I would start with ##m := \operatorname{lcm}(m_1,\ldots,m_k)## and show ##\sigma^m=1##, and that for any other ##k##, that is one which isn't a multiple of (w.l.o.g.) ##m_1##, i.e. ##k=qm_1+r_1## has a remainder, ##\sigma^k \neq 1\,.##
Why does being any other ##k## imply that ##k## is not a multiple of ##m_1##?
 
  • #4
14,413
11,726
Why does being any other ##k## imply that ##k## is not a multiple of ##m_1##?
You're right one has to be more careful here. Assume ##k<m## with ##\sigma^k=1.## Then what is ##c_i^k\,?##
 
  • #5
1,462
44
You're right one has to be more careful here. Assume ##k<m## with ##\sigma^k=1.## Then what is ##c_i^k\,?##
I don't see what I can say about ##c_i^k## in general. It would seem that it depends on which ##c_i## we're talking about. For example, say we have ##m = \operatorname{lcm} (2,3,5)= 30## where ##m_1=2,m_2=3,m_3=5##. Then, if we take ##k=2<30## ##c_1^2 = 1## but ##c_3^2 \ne 1##
 
  • #6
14,413
11,726
I don't see what I can say about ##c_i^k## in general. It would seem that it depends on which ##c_i## we're talking about. For example, say we have ##m = \operatorname{lcm} (2,3,5)= 30## where ##m_1=2,m_2=3,m_3=5##. Then, if we take ##k=2<30## ##c_1^2 = 1## but ##c_3^2 \ne 1##
I meant, still assume a ##k## with ##\sigma^k=1## and ##k<m##. Compute it and see what it does with the numbers shuffled by ##c_i##. They are still disjoint, which allows to sort the powers by the ##c_i## and all other ##c_j\; , \;(i\neq j)## don't affect the numbers permuted by ##c_i##.
 
  • #7
1,462
44
I meant, still assume a ##k## with ##\sigma^k=1## and ##k<m##. Compute it and see what it does with the numbers shuffled by ##c_i##. They are still disjoint, which allows to sort the powers by the ##c_i## and all other ##c_j\; , \;(i\neq j)## don't affect the numbers permuted by ##c_i##.
So am I trying to prove that if the cycles are disjoint, then ##c_1^n c_2^n \dots c_k^n = 1## implies that ##c_i^n = 1##? This is what I'm seeing is necessary, and how I see it in most proofs online. And it seems obvious because the cycles are disjoint, but I don;t see how to make it rigorous...
 
  • #8
14,413
11,726
The formula ##(c_1\ldots c_k)^r = c_1^r\ldots c_k^r## is of general interest. For this you only need to show ##c_1c_2=c_2c_1## and the rest is either by induction or a so forth argument. Given that, you have ##c_1^r\ldots c_k^r=1 \Longrightarrow c_1^r=c_{k}^{-r}\ldots c_2^{-r}##. Now evaluate both sides at an ##a\in c_1##.
 
  • #9
1,462
44
The formula ##(c_1\ldots c_k)^r = c_1^r\ldots c_k^r## is of general interest. For this you only need to show ##c_1c_2=c_2c_1## and the rest is either by induction or a so forth argument. Given that, you have ##c_1^r\ldots c_k^r=1 \Longrightarrow c_1^r=c_{k}^{-r}\ldots c_2^{-r}##. Now evaluate both sides at an ##a\in c_1##.
Well since the RHS consists of compositions of permutations that are disjoint with ##c_1##, the RHS will evaluate to ##a##. So ##c_1^r (a) = a##? And so ##c_1^r = 1##?
 
  • #10
14,413
11,726
Yes. That's the idea. And thus ##m_1\,|\,r##. And at last note that you can do this for any index thanks to commutativity.
 
  • Like
Likes Mr Davis 97
  • #11
1,462
44
Yes. That's the idea. And thus ##m_1\,|\,r##. And at last note that you can do this for any index thanks to commutativity.
Alright, I think I see it all coming together. Last thing: Suppose that we have the disjoint cycles ##c_1, \dots, c_k##. Do I need to show that ##\forall r \in \mathbb{Z}## ##c_1^r ,\dots, c_k^r## are still disjoint? Once again, it seems obvious since when you compose a permutation with itself, numbers can leave the cycle but additional ones will never be added, so all the permutation remain disjoint.
 
  • #12
14,413
11,726
Alright, I think I see it all coming together. Last thing: Suppose that we have the disjoint cycles ##c_1, \dots, c_k##. Do I need to show that ##\forall r \in \mathbb{Z}## ##c_1^r ,\dots, c_k^r## are still disjoint? Once again, it seems obvious since when you compose a permutation with itself, numbers can leave the cycle but additional ones will never be added, so all the permutation remain disjoint.
They cannot even leave the cycle, they are only shifted by ##r## places. Again, this depends on how deep you want to get. I'd say a remark will do. At a closer look, you don't need commutativity after they are arranged as ##c_1^r\ldots c_k^r##, which I mistakenly stated. It's only used for this arrangement. And thus I don't think you need that they are still disjoint, only that numbers of one cycle aren't touched by any other.
 

Related Threads on Finding the order of element of symmetric group

Replies
3
Views
792
Replies
5
Views
3K
Replies
1
Views
4K
  • Last Post
Replies
7
Views
1K
Replies
4
Views
6K
Replies
4
Views
5K
  • Last Post
Replies
1
Views
839
  • Last Post
Replies
4
Views
4K
  • Last Post
2
Replies
34
Views
1K
Replies
3
Views
8K
Top