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

Permutations Question

  1. Sep 29, 2004 #1
    I am trying to read through and understand about permutations, and I have a couple of questions.

    First, How do you write a permutation as a transposition?

    The example that I have is (3, 10, 1, 4, 5, 7, 2, 8, 6, 9), and I said that it is equal to (3, 10)(10, 1)(1, 4)(4, 5)(5, 7)(7, 2)(2, 8)(8, 6)(6, 9). I think I followed how the book showed to do this, so I think my answer is corect (right?), but I have no idea WHY this works.

    Am I correct in assuming that I use the (3, 10, 1, 4, 5, 7, 2, 8, 6, 9), since the original question writes this as (1 2 3 4 5 6 7 8 9 10
    (3, 10, 1, 4, 5, 7, 2, 8, 6, 9).

    Also, if you could answer Why this works, it would be very helpful.

    Also, how exactly do I compute this long composition problem? I don't understand how it works. I understand that I work from right to left, but if I know that 6 goes to 9 and 9 goes to 6, how do I go backwards to where I started? (Hopefully that question makes sense).

    Also, why is the order of two cycles equal to the least common multiple of elements in each cycle?

    Am I correct in assuming that in the following cycle:
    (1, 3, 10)(2, 4, 5, 7)(6, 8)(9), the order is lcm[3, 4, 2, 1] = 12?

    Again, explaining why would be extremely helpful.

  2. jcsd
  3. Sep 30, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    you don't. a permutation may be written as a product of transpositions, not a transposition.

    it works because it's the right answer. the left hand side and righthand side are the same permutation. the way you figure it out is to notice early one that


    then you wonder in general, is


    well, it certainly is (123)(34) and that's equal to (1234), so that's well and good, then you prove it in generaly. induction looks like a good idea here so try it.

    hopefully you see why it works (it's a proof, not an algorithm), but the first part i don't understand. perhaps becaue you think the justification from the imput box is preserved in the output? it isn't.

    sadly it doesn't. what long composition problem? do you mean 'how do i simplify large permutations into easier to read ones?

    eg simplify (123)(235)(57) into a product of disjoint cycles?

    i#ll assume so, it's a usual question.

    pick any element in the swap, say 7 and write down
    read wheree 7 goes to (from right to left)
    7 goes to 5 in the first cycle, then that 5 is sent to 2 in the second cycle, then that 2 is sent to 3 in the first cycle so we have


    now put 3 in. the first cylce leaves it alone, the second sends 3 to 5, the last one leaves 5 alone so we write


    now put 5 in. 5 is sent to 7 by the first cycle, then 7 is left alone by all the others. 7 is what we started with so we can close off that bracket and write:


    now pick some element that we've not written down and start a new bracket, say, 1:


    1 is left alone by the first cycle,a nd the second, and sent to 2 in the last one so we write:


    put 2 back in and see where it goes, etc when it returns to 1 close off the bracket and start a new one with any remaining unused elements.

    it isn't. that is only true if the cycles are disjoint, that is have no common elements in either cycle.

    because the cycles are disjoint they commute. in *any* group if you have two elements x and y and xy=yx, then ord(xy)=lcm(ord(x),ord(y))
    that is just a property of commutative groups, nothing to do with permutations.

    remember cycles must be disjoint for this to work, eg

    (12)(23) does not have order lcm(2,2), its order is 3.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook