1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Permutation Multiplication

  1. Oct 8, 2009 #1
    1. The problem statement, all variables and given/known data

    Multiply the permutation (246)(12)(47)

    3. The attempt at a solution

    This has got to be so easy yet I cannot figure it out on my own. I understand that for (246) it means that [tex] 2 \mapsto 4, 4 \mapsto 6, 6 \mapsto 2 [/tex]. Could anyone lead me on what I should do next with (12)? Do I do something with [tex]1 \mapsto 2[/tex] and multiplication?
  2. jcsd
  3. Oct 8, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi DEMJ! :smile:

    (just type -> for "goes to" :wink:)

    Just start at the right, and try each number separately.

    For example, where does 7 go? Where does 4 go? etc … :smile:
  4. Oct 8, 2009 #3
    If I start at the right 7 -> 4 then 4 goes back to 7. Then 2 -> 1 then 1 goes back to 2.

    or should I think of it as 7 -> 4 then 4 -> 2 then 2 -> 1 then 1 -> 6 and so on. Which is

    the correct way to think for permutation multiplication?
  5. Oct 8, 2009 #4


    User Avatar
    Science Advisor
    Homework Helper

    You have to do each bracket in turn:

    Where does (47) send 7 to? Then where does (12) send that to? Then where does (246) send that to?
  6. Oct 8, 2009 #5
    I am doing awful with this, but I understand (47) sends 7 to 4, but I do not understand where (12) sends 7 -> 4 to? If it sends it (246) does it change (246) to (276) ?
  7. Oct 8, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    A cycle (a bracket) only moves the elements around, it doesn't move other cycles around.
    (12) only affects 1 and 2 … it leaves 4 where it is. :wink:

    Now can you see what (246) does? :smile:
  8. Oct 8, 2009 #7


    User Avatar
    Science Advisor
    Homework Helper

    hmm … a friend of mine has just suggested I should ask whether your book multiplies different brackets from right to left or from left to right …

    I've been assuming right to left (that's the usual algebraic way, I didn't know there was any other), so that (47) is used first

    does your book do it that way, or does it use left to right, so that (246) is used first?
  9. Oct 8, 2009 #8


    User Avatar
    Science Advisor
    Gold Member

    You can use the following rules (cycles act from the left on sequences and the notation for their action is defined so that these rules hold)

    * A cycle: (a,b,c...,y,z) can be written as a product of 2-cycles via:
    (a,b,c,....,y,z) = (ab)(bc)(c .) ... (. y)(yz)

    * The terms in a cycle can be cycled and it's the same cycle:
    (a,b,c,...y,z) = (b,c,...y,z,a) = (c,...y,z,a,b) = ... = (z,a,b,c,...,y)

    ( in particular (ab)=(ba) )

    * Disjoint cycles commute:
    (abcd)(pqr) = (pqr)(abcd) where none of p,q,r equal any of a,b,c,d.

    Add to this that 2-cycles square to the identity (ab)(ab)=1 and you can always simplify permutation products.

    There is a short cut you can derive from the above base rules. You can always split off a transpose (2-cycle) from either end of a general cycle (or recombine going the other way)
    (a,b,c,...x,y)(y,z) = (abc...xyz) = (ab)(bc...xyz).
    When combining a 2-cycle with a general cycle you must make sure here that the 2-cycle and general cycle have only one term in common and cycle both so it is positioned on the adjacent ends of each.

    This is correct: (ab)(bcd) = (abcd)
    but do not use: (ab)(bcad) != (abcad) as cycles with repeated terms are forbidden!!!
    In such a case you want to factor and recombine cycle and combine again:
    (ab)(bcad) = (ab)(bc)(cad) = (abc)(cad) = (bca)(cad) = (bc)(ca)(ca)(ad)=(bc)(ad).

    More generally:
    ** you can split a cycle into a product of two cycles with one common term or append two cycles with one common term:
    (abcd)(defgh...) = (abcdefgh....)

    With some practice you can get quite efficient at this permutation arithmetic. You can always continue until any common terms have been combined and you have a product of disjoint cycles.

    Note the action of a cycle notated to obey these rules is for example:
    =(12)[acbd] {(23) swapped 2nd and 3rd elements.}
    =[cabd] {then (12) swapped first and 2nd elements.}
    The net result is that the cycle (123) maps positions: 1-->2-->3-->1
    Similarly for general cycles (abcd...z) maps a-->b-->c-->...-->z-->a.
    (This is the notation you indicted.)

    If the notion being used is the reverse of this then use a dot or star to distinguish the two notations
    (123)* = (321)
    and then just reverse to this notation solve and reverse back.

    Example. Simplify:
    =(24)(1245)(24)(35) {commuting disjoint cycles}
    =(42)(2451)(24)(35) {cycle to get 2's adjacent ***}
    =(42)(24)(451)(24)(35) {split off 24 transpose from 4-cycle since 2 terms in common.}
    =(451)(24)(35) {square 2-cycle to identity}
    =(514)(42)(35) {cycle to get 4's adjacent}
    =(5142)(35) {combine cycles since only one common term}
    =(1425)(53) {cycle to get 5's adjacent}
    =(14253) {combine since only one common term.}
    P = (14253)

    *** you could have cycled to get 4's adjacent but since two terms are in common and adjacent you want to pull off both together. If two are in common but not adjacent that's fine. It will work out either way pulling out one at a time.

    Some exercises:
    Work out that (ax)(abcd)(ax) = (xbcd)
    Work out that (ax)(abxyz)(xa) = (xbayz) (adjoint action of a transpose)
    Work out that (abcd...z)(z...dcba) = 1 (reversed cycles are inverses)
    Work out: (abc)(xaybzc)(cba)=? (adjoint action of a 3-cycle)
    Work out: (123)(123) = (321)

    Have fun.
    Last edited: Oct 8, 2009
  10. Oct 8, 2009 #9


    User Avatar
    Science Advisor
    Gold Member

    Here's an interesting aside.

    The algebra of permutations can be extended by appending signs and allowing (ab)= -(ba) and (ab)(ab) = -1. This central extension is how one defines projective representations of the permutation group. This relates to projective and gauge statistics for theoretical particles.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook