Results 1 to 7 of 7

Math Help - Permutations, groups, cycles

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    England
    Posts
    3

    Permutations, groups, cycles

    Hi.

    I want to achieve this permutation:


    1 2 3 4 5 6 7 8 9
    7 3 6 2 8 4 9 5 1

    That is two line notation.




    But I can't get it right, here's my best permutation, I mean effort:


    1 7 2 3 6 4 8 5 9




    But...with that I get these cycles;


    1 -> 7
    2 -> 3
    3 -> 6
    4 -> 8 wrong
    5 -> 9 wrong
    6 -> 4
    7 -> 2 wrong
    8 -> 5
    9 -> 1


    I have 3 cycles wrong. I have tried many variations, for example;


    (1 7 2) (3 6 4 8 5 9)
    (1 7 3 6 4 2 8 5 9)
    (1 7 2 3 6 ) (4 8 5 9)


    But no, I just can't get it right.




    And this shorter one is really close:


    I want to achieve this:


    1 2 3 4 5
    2 1 4 3 5


    Here is my best permutation:


    (1 2) (3 4 ) ( 5 ) and that will be:


    1 2 3 4
    2 1 4 3


    But 5 is missing after 4. How I get that 5 so that will be;

    1 2 3 4 5
    2 1 4 3 5



    I would really appreciate help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    Re: Permutations, groups, cycles

    Quote Originally Posted by RiverAlex View Post
    Hi.

    I want to achieve this permutation:


    1 2 3 4 5 6 7 8 9
    7 3 6 2 8 4 9 5 1

    That is two line notation.




    But I can't get it right, here's my best permutation, I mean effort:


    1 7 2 3 6 4 8 5 9




    But...with that I get these cycles;


    1 -> 7
    2 -> 3
    3 -> 6
    4 -> 8 wrong
    5 -> 9 wrong
    6 -> 4
    7 -> 2 wrong
    8 -> 5
    9 -> 1


    I have 3 cycles wrong. I have tried many variations, for example;


    (1 7 2) (3 6 4 8 5 9)
    (1 7 3 6 4 2 8 5 9)
    (1 7 2 3 6 ) (4 8 5 9)


    But no, I just can't get it right.




    And this shorter one is really close:


    I want to achieve this:


    1 2 3 4 5
    2 1 4 3 5


    Here is my best permutation:


    (1 2) (3 4 ) ( 5 ) and that will be:


    1 2 3 4
    2 1 4 3


    But 5 is missing after 4. How I get that 5 so that will be;

    1 2 3 4 5
    2 1 4 3 5



    I would really appreciate help.
    Try to follow the diagram. There should be three disjoint cycles. The order of the cycles does not matter because disjoint cycles commute.

    Attachment 24957

    Follow each color until you get back to its starting point.
    Attached Thumbnails Attached Thumbnails Permutations, groups, cycles-capture.png  
    Last edited by TheEmptySet; September 28th 2012 at 09:13 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Permutations, groups, cycles

    let's write your permutation as a function f: {1,2,3,4,5,6,7,8,9} → {1,2,3,4,5,6,7,8,9}. so

    f(1) = 7
    f(2) = 3
    f(3) = 6
    f(4) = 2
    f(5) = 8
    f(6) = 4
    f(7) = 9
    f(8) = 5
    f(9) = 1.

    it should be clear that our cycle decomposition should start:

    (1 7......) since f(1) = 7. what should be the next number? f(7). what is f(7)? looking above, we see that f(7) = 9. so we continue:

    (1 7 9 ....)

    now, we need to find f(9). and f(9) = 1, so we have our first "cycle" (a 3-cycle), so we have:

    (1 7 9)(2......

    and what is f(2)? f(2) = 3, so our 2nd cycle begins like this:

    (1 7 9)(2 3 ....)

    we have to look up f(3), now, and we find that f(3) = 6. next will be f(6), and we see that f(6) = 4. finally, we see that f(4) = 2, which "closes" our 2nd cycle:

    (1 7 9)(2 3 6 4)

    so...which numbers aren't listed? 5 and 8, right? so we start out 3rd cycle as:

    (1 7 9)(2 3 6 4)(5 ....)

    now f(5) = 8, and f(8) = 5, so we finish with a 2-cycle, and we're done:

    (1 7 9)(2 3 6 4)(5 8).

    *************

    for your 2nd problem:

    (1 2)(3 4) = (1 2)(3 4)(5), since all 1-cycles are the identity (why?)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2012
    From
    England
    Posts
    3

    Re: Permutations, groups, cycles

    Thank you TheEmptySet. But Great thanks to Deveno!
    That was really good explanation, and
    it helped me to understand. I tried, before your answer, those three disjoint cycles, but
    they were wrong.

    You asked why all 1-cycles are the identity. Well, because 1-cycle build its own cycle, for example (5).


    I have one more question.

    First;
    Sign of a permutation s can be defined from its decomposition into the product of transpositions as
    sgn(s) = (-1)^m

    (-1)^m, where m means the number of transpositions in the decomposition. I am sure you know.


    so, I wonder that how many changes ( and what they are ) are in this same permutation:

    1 2 3 4 5 6 7 8 9
    7 3 6 2 8 4 9 5 1


    I have thought this over many times and this is my solution:

    (2 7), (1 2), (2 3), (3 6), (4 5), (7 9).

    I believe those are correct and that there are six changes. ? Thus, (-1)^6.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Permutations, groups, cycles

    -----------------------
    I believe you're reading right to left. So 4->5 according to your product of transpositions, but 4->2 according to your permutation.

    -----------------------
    A useful fact is that (a_1 \ a_2 \ ... \ a_n) = (a_1 \ a_n)(a_1 \ a_{n-1})(a_1 \ a_{n-2}) \ ... \ (a_1 \ a_3)(a_1 \ a_2).

    Thus once you've broken a permutation into cycles (which might seem confusing now, but becomes very easy with a bit of experience), you can use that fact to break each of those cycles into transpositions, and hence the whole permutation into a product of transpositions. It also means that a cycle's parity is one different than its length, which makes detemining the sign of the permutation easy once you've broken it down into cycles.

    -----------------------
    An important observations is that, when a permutation is written as a product of transpoitions, the number of transpositions is *NOT* fixed. What IS fixed is the parity (i.e. even or odd) of the number of transpositions (that's a theorem). You said you thought your permutation was a product of 6 transpositions. The number 6 doesn't matter there - what matters is that 6 is EVEN. The immediate content of saying you've written a permutation as a product of 6 transpositions is that your permutation is EVEN.

    And that's why you see, and it's meaningful, this: (-1)^{(number \ of \ transpositions)}

    A permutation might be written as a product of 5, or 213, transpositions. What matters is that number is odd, so you get the same result, -1, when you raise -1 to a power that's the number of transpositions, no matter which of the many ways you discover to write it as a product of transpositions.

    -----------------------
    Another methodical way to write a permutation as a product of transpositions is to "send each one home" via a transposition. This is easiest to explain by showing an example:
    Let p = your permutation. Then p sends 1 to 7, so send 1 back home by mutliplying after p by the transposition (1 7):
    Then (1 7)p sends 1 to 1.
    Now send 2 home. See that (1 7)p sends 2 to 3, so (2 3)(1 7)p sends 2 to 2.
    Now send 3 home. See that (2 3)(1 7)p sends 3 to 6, so (3 6)(2 3)(1 7)p sends 3 to 3.
    Now send 4 home. See that (3 6)(2 3)(1 7)p sends 4 to 6, so (4 6)(3 6)(2 3)(1 7)p sends 4 to 4.
    Now send 5 home. See that (4 6)(3 6)(2 3)(1 7)p sends 5 to 8, so (5 8)(4 6)(3 6)(2 3)(1 7)p sends 5 to 5.
    Now send 6 home. See that (5 8)(4 6)(3 6)(2 3)(1 7)p sends 6 to 6, so no change required, as 6 is already home.
    Now send 7 home. See that (5 8)(4 6)(3 6)(2 3)(1 7)p sends 7 to 9, so (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p sends 7 to 7.
    Now send 8 home. See that (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p sends 8 to 8, so no change required, as 8 is already home.
    Now send 9 home. See that (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p sends 9 to 9, so no change required, as 9 is already home.
    (Whew - If 9, the last one, weren't already home, it would mean that I screwed up - because there's nothing left for 9 to switch with. Everything else is already home. If this has been done without any blunders, then the last one at the last stage is guaranteed to already be home.)

    So it should be that (7 9)(5 8)(4 6)(3 6)(2 3)(1 7)p = identity. You can mentally check for yourself as I just did that it is.

    Thus p = inverse of [ (7 9)(5 8)(4 6)(3 6)(2 3)(1 7) ] = (1 7)(2 3)(3 6)(4 6)(5 8)(7 9). Again, you can mentally check that it equals p.
    Last edited by johnsomeone; September 29th 2012 at 09:34 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Permutations, groups, cycles

    if you have a permutation p expressed as a product of DISJOINT cycles, there is a trick you can use to easily calculate sgn(p).

    first of all, sgn is a homomorphism, which means that:

    sgn(ps) = sgn(p)sgn(s).

    next, note we can write any k-cycle:

    (a_1\ a_2\ \dots\ a_k) = (a_1\ a_k)\dots(a_1\ a_3)(a_1\ a_2)

    thus if s is a k-cycle, sgn(s) = (-1)k-1.

    so if k is ODD, s is an EVEN permutation, if k is EVEN, s is an ODD permutation

    (the easy way to remember this is that 1-cycles (the identity) and 3-cycles are even, and single transpositions (2-cycles) are odd).

    ok, so if p = (1 7 9)(2 3 6 4)(5 8), we have:

    sgn(p) = sgn((1 7 9))sgn((2 3 6 4))sgn((5 8)) = even*odd*odd = even, or more explicitly:

    sgn((1 7 9)) = (-1)2 = 1
    sgn((2 3 6 4)) = (-1)3 = -1
    sgn((5 8)) = -1, so

    sgn(p) = (1)(-1)(-1) = 1, so p is even.

    explicitly, we can write p as a product of transpositions (one way out of many possible other ways):

    p = (1 7 9)(2 3 6 4)(5 8) = (1 9)(1 7)(2 4)(2 6)(2 3)(5 8).

    counting the transpositions in the decomposition above, we have 6, so p is even.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2012
    From
    England
    Posts
    3

    Re: Permutations, groups, cycles

    Thank you Johnsomeone and Deveno! You both explained things really well! Yes, indeed. Many thanks to you.
    Your answers are really useful. I also found 20 inversions and that is (-1)^20 = 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutations and cycles
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 25th 2011, 02:19 PM
  2. Permutations, cycles
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 12th 2010, 04:41 PM
  3. Permutations & Cycles
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 12th 2010, 03:19 PM
  4. Permutations cycles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 4th 2008, 03:59 PM
  5. groups of permutations
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: December 6th 2007, 06:10 AM

Search Tags


/mathhelpforum @mathhelpforum