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!

Can someone please check this proof involving permutations and cycles?

  1. May 7, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove: If σ is a cycle of odd length, then σ2 is a cycle.


    2. Relevant equations

    N/A

    3. The attempt at a solution

    Proof: Assume σ is a cycle of odd length. Then let us model σ as (1 2 3 4 ... 2k +1) for some integer k [assuming here that the fixed elements of σ are those such that 2k + 1 < i]. Note then that σ2 = (1 2 3 4 ... 2k +1)(1 2 3 4 ... 2k +1), which we may otherwise define as σ2(i) = {i + 2, i ≤ 2k - 1; 1, i = 2k; 2, i = 2k + 1; i, 2k + 1 < i}. Hence, the elements 1,2,3,4,...,2k + 1 of σ remain fixed in a cycle, and so σ2 is indeed also a cycle.
     
  2. jcsd
  3. May 7, 2012 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Syrus! :smile:
    How does that prove it's a cycle (and not eg 2 cycles)?

    Doesn't your proof also apply to even lengths?
     
  4. May 8, 2012 #3
    I think i understand what you're implying. I have now taken into account the fact that σ is odd- does this seem acceptalbe?

    Proof: Assume σ is a cycle of odd length. Then let us model σ as (1 2 3 4 ... 2k + 1) for some integer k [assuming here that the fixed elements of σ are those n such that 2k + 1 < n]. Note then that σ2 = (1 2 3 4 ... 2k +1)(1 2 3 4 ... 2k + 1). Then σ2 can be alternatively represented by (1 3 5 7 ... 2k + 1 2 4 6 8 ... 2k). Since σ(2k) = 2k + 1, σ(2k + 1) = 1, and σ(1) = 2, it follows that σ2(2k) =1 and σ2(2k + 1) = 2. Hence, the elements 1,2,3,4,...,2k + 1 of σ remain fixed in a cycle, and so σ2 is indeed also a cycle.
     
  5. May 8, 2012 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Syrus! :smile:

    You could have stopped here
    … you've actually specified the cycle whose existence you had to prove (with all the elements distinct). :wink:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Can someone please check this proof involving permutations and cycles?
Loading...