Results 1 to 7 of 7

Math Help - Permutation with non-disjoint cycles

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    79

    Permutation with non-disjoint cycles

    Let π=(1 2 5 7)(2 3 4)(1 3 5)(2 3 7 8 9)

    I need to write π in the standard form where 1,2,...,9 is on top and then the image of these numbers is below them.

    I realize that these cycles are non-disjoint, and that's what's throwing me off. It seems like 1 connects with 2 and 1 connects with 3. But I know that 1 can only have one image. So I'm kind of lost here. Help please!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by steph3824 View Post
    Let π=(1 2 5 7)(2 3 4)(1 3 5)(2 3 7 8 9)

    I need to write π in the standard form where 1,2,...,9 is on top and then the image of these numbers is below them.

    I realize that these cycles are non-disjoint, and that's what's throwing me off. It seems like 1 connects with 2 and 1 connects with 3. But I know that 1 can only have one image. So I'm kind of lost here. Help please!


    Read the cycles from right to left (this is, I believe, the standard for most mathematicians), then:


    1 goes to 3, then 3 goes to 4, so 1 goes to 4

    2 goes to 3, 3 goes to 5, 5 goes to 7, so 2 goes to 7, etc.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    79
    Ok, I understand that method. But I thought that that is what you want to do when you want to write π as a product of disjoint cycles. Writing π as a product of disjoint cycles would be (1 4 5 2 7 8 9 3).

    SO, back to my original question, if I want to write π like π=1 2 ....9 with the images underneath, I'm guessing the images come from my product of disjoint cycles above? In other words, would π written in standard form be...
    π=1 2 3 4 5 7 8 9
    ...4 7 1 5 2 8 9 3
    ??

    Also, I know that the order for a disjoint permutation is ord(π1, π2...)=lcm(ord(π1), ord(π2),...), but I don't know how to find the order for a non-disjoint permutation. I would appreciate an explanation of how to find it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591
    the procedure goes like this: in the product, what is the image of 1? well 1 isn't moved in the cycle (2 3 7 8 9), so we move to the next one in the compositional order, (1 3 5). in this cycle, 1 is moved, and has image 3. so in the NEXT cycle, we check to see if 3 is moved or not. and it is, 3 is moved to 4 in (2 3 4). since 4 is not moved by (1 2 5 7), we are done calculating the image of 1. whew! only 8 more images to check. now, assuming your disjoint cycle is correct (i haven't checked, but it looks like it may be), then the "standard" way of writing it as a 1-1 function by listing the image set under the domain set is correct.

    in general, it is easier to write a permutation as a product of disjoint cycles to find its order. given the standard form, you just write (1 f(1) f(f(1))....f^-1(1)) and then start the second cycle with the first element not moved by the first cycle, until you've exhausted the numbers involved.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by steph3824 View Post
    Ok, I understand that method. But I thought that that is what you want to do when you want to write π as a product of disjoint cycles. Writing π as a product of disjoint cycles would be (1 4 5 2 7 8 9 3).

    SO, back to my original question, if I want to write π like π=1 2 ....9 with the images underneath, I'm guessing the images come from my product of disjoint cycles above? In other words, would π written in standard form be...
    π=1 2 3 4 5 7 8 9
    ...4 7 1 5 2 8 9 3
    ??


    Yes, but don't forget 6 which is mapped to itself.


    Also, I know that the order for a disjoint permutation is ord(π1, π2...)=lcm(ord(π1), ord(π2),...), but I don't know how to find the order for a non-disjoint permutation. I would appreciate an explanation of how to find it.
    Once you have the permutation as above write it now as disjoint cycles and evaluate its order...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2009
    Posts
    79
    Ok, thank you Tonio and Deveno! Also, I am not positive about finding the sign. I am thinking that my πΔ is...(x_4-x_2)(x_4-x_6)(x_4-x_8)(x_4-x_9)(x_4-x_3)(x_7-x_9)(x_7-x_3)....and continue on in this fashion?? Can someone verify if this is correct?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by steph3824 View Post
    Ok, thank you Tonio and Deveno! Also, I am not positive about finding the sign. I am thinking that my πΔ is...(x_4-x_2)(x_4-x_6)(x_4-x_8)(x_4-x_9)(x_4-x_3)(x_7-x_9)(x_7-x_3)....and continue on in this fashion?? Can someone verify if this is correct?

    Written as a product of disjoint cycles, your permutation is even iff the number of even-length cycles is even.

    In this case it is particularly simple since the given permutation is a cycle of length 8...

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Disjoint Union of Cycles
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 31st 2011, 07:25 AM
  2. Prove that Disjoint cycles commute
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 16th 2010, 09:47 PM
  3. Disjoint cycles of generalized eigenvectors
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 3rd 2009, 09:32 PM
  4. Disjoint cycles
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 3rd 2009, 01:00 PM
  5. Disjoint cycles...
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: July 1st 2008, 07:41 PM

Search Tags


/mathhelpforum @mathhelpforum