1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations. Help needed!

  1. Sep 11, 2008 #1
    1. The problem statement, all variables and given/known data

    Here are two problems that i am striving with:
    1.
    Let [tex]\theta[/tex] be the s-cycle (123...s).

    (i) what is the smallest positive integer m such that [tex] \theta^h=\theta^k[/tex] when

    h\equiv k(mod m)?

    NOte: This is not actually a homework problem, but since the other one that i am gonna write down, is i posted this one here two, because i feel that if i can get this one right, then i can get the next one too.

    2. Let [tex] \theta[/tex] be the s-cycle (123....s). what is the smallest integer r such that the set

    [tex] \{(1), \theta , \theta^2,........,\theta^{r-1}\}[/tex] is closed under multiplication?

    Well, i think the key problem that i am having here is to prove, or show that if

    [tex] \theta[/tex] is an s-cycle, then [tex] \theta^s=(1)[/tex] where (1) is the identity permutation in standard form.

    I am not sure whether this one comes directly from the def. of an s-cycle or there is a special way of prooving it.

    Anyways here are my first thoughts about this last one. i think that it somes directly as a result of the def. of an s-cycle.

    Let [tex] \theta =(a_1,a_2,.....,a_s)[/tex] be an s- cycle. Then

    since [tex] \theta (a_i)=a_{i+1},i=1,2,.....,s-1[/tex], and [tex] \theta(a_s)=a_1[/tex]

    SO, now the reason that [tex] \theta^s=(1)[/tex] i think is that, if we start operatin with [tex]\theta[/tex] in the firs element of the s-cycle [tex] a_1[/tex] then we get:

    [tex]\theta(a_1)=a_2, \theta(a_2)=a_3,=>\theta(\theta(a_1))=\theta^2(a_1)=a_3,......,\theta^{s-1}(a_1)=a_s[/tex] but since [tex] \theta(a_s)=a_1=>\theta^s(a_1)=a_1[/tex]

    And similarly with other elements of the cycle.

    This way we notice that [tex]\theta[/tex] has to opertate s times in each element of the cycle in order to go back to that same element. Hence i think that this is the reason that

    [tex] \theta^s=(1)[/tex] , or am i wrong? Anyways try to clarify this a lill bit for me please.


    So, now let's go back to the first problem. If what i just did holds, i mean if the proof is correct, then here it is how i tackled the first problem:

    [tex] \theta^h=\theta^k[/tex] when

    [tex] h\equiv k(mod m)[/tex]=> we get that

    [tex] h-k=nm, n\in Z=>h=k+nm[/tex] hence we get:

    [tex] \theta^h=\theta^{k+nm}=\theta^k\theta^{nm}=\theta^k(\theta^m)^n[/tex] so in order for [tex] \theta^h=\theta^k[/tex] we need to have m=s, since then we would get

    [tex] \theta^s\theta^k=(1)\theta^k=\theta^k[/tex] Is this even close to the right way of approaching this problem, or i am way off?

    SO, any advice?




    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Sep 12, 2008 #2
    So no input on this one?
     
  4. Sep 13, 2008 #3

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    You almost have the right idea. Proving that [itex]\theta^s =1[/itex] isn't enough (your proof is fine, by the way) - you also need to prove that if 0<r<s, then [itex]\theta^r \neq 1[/itex].
     
  5. Sep 13, 2008 #4
    Holy, crap!! hehe.. this is exactly what i did! Only that i proved that [tex] \theta^r \neq 1[/tex] for any other r. But basically this is what i did.
    I did this after i posted the problem here though, but before i turned in the hw.
     
    Last edited: Sep 13, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutations. Help needed!
  1. Permutations Help (Replies: 10)

  2. Help of permutations (Replies: 14)

  3. Permutation help. (Replies: 4)

Loading...