Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook