Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - How do I multiply permutations?

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    How do I multiply permutations?

    I have
    a=(1,3,5)(1,2)
    b=(1,5,7,9)

    and I have to calculate a^-1 * b * a

    How do I do it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by GIPC View Post
    I have
    a=(1,3,5)(1,2)
    b=(1,5,7,9)

    and I have to calculate a^-1 * b * a

    How do I do it?
    Actually I learned it from practice and a few observations. Computing the inverse of a is the only hurdle I see here:

    First of all,

    a = (1,3,5)(1,2) = (1,2,3,5)

    Fact *: (a,b,c,d)^{-1} = (a,d,c,b) (Prove it!)

    Using fact *, a^{-1}ba = (1,5,3,2)(1,5,7,9)(1,2,3,5) = (1,7,9,5)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2009
    Posts
    224
    Quote Originally Posted by Isomorphism View Post
    Actually I learned it from practice and a few observations. Computing the inverse of a is the only hurdle I see here:

    First of all,

    a = (1,3,5)(1,2) = (1,2,3,5)

    Fact *: (a,b,c,d)^{-1} = (a,d,c,b) (Prove it!)
    Is that really a fact? Because I have a solved example from my text-book which contradicts this:

    The inverse of \tau = (5, 4, 6, 2)(1, 3, 9, 10, 7)(8, 11)

    is \tau^{-1}= (2, 6, 4, 5)(7,10,9,3,1)(11, 8).

    We have to write the whole thing backward! I mean, if I used your method I would get

    \tau^{-1}= (5, 2,6,4)(1, 7,10,9,3)(8, 11), which is wrong.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Are you sure they aren't the the same
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91
    From a Google Search:

    "Inverses: Every permutation has an inverse that ``undoes'' the operation. In other words, if you apply a permutation to a set and then apply its inverse, the result is that the final order is unchanged from the original. If is a permutation and is its inverse, we can write .
    If you have a permutation written in cycle notation and you want to find its inverse, simply reverse all the cycles. For example, . To see why this works, multiply: . The result will be . "

    Numbers didn't come through with copy/paste.

    The link is: http://mathcircle.berkeley.edu/BMC3/perm/node4.html

    But I couldn't find the definition of multiplication of permutations anywhere. What is it please, I'm curious.
    Edit: Actually, the same link does explain multiplication of permutations but I couldn't understand it
    Last edited by Hartlw; September 5th 2010 at 10:20 AM. Reason: add link,
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2009
    Posts
    224
    Quote Originally Posted by Isomorphism View Post
    Are you sure they aren't the the same
    Oh I see. But I still don't understand why you gave that method in your first post. Isn't it easier to just write all the numbers in each cycle backward?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91

    algorithm for multiplication?

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

    is a permutation of 1 2 3 4 5 6 7. By definition of multiplication:

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

    p1xp2=p3. So far so good. 1to2 from p1 then 2to4 from p2 gives 1to4 for p3 etc

    In cyclic notation:
    [(1,2,4,3,6)(5,7)][(1,5,3)(2,4,7,6)]=(4721653)

    p1 says 1 goes to 2, 2 goes to 4, 4 goes to 3, 3 goes to 6, and 6 goes back to 1. and so on.

    BUT HOW DO YOU DO THE MULTIPLICATION IN CYCLIC NOTATION?

    How do you get (1,3,5)(1,2)=(1,2,3,5)?

    If I convert it to the p1xp2=p3 notation above I get:

    (1 2 3 4 5)(1 2 3 4 5)=(1 2 3 4 5)
    (3 2 5 4 1)(2 1 3 4 5)=(3 1 5 4 2)=(3152)

    for the first permutation p1, (1,3,5) says 1 goes to 3, 3 goes to 5, 5 goes to 1, 2 goes to 2, and 4 goes to 4, and so on. The answer is not (1,2,3,5), or a cyclic permutation of it: 3152, 1523, 5231, 2315
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91

    An Algorithm for cyclic multiplication

    OK. I can see a way to do the cyclic multiplication:
    p1xp2 = (1,3,5)(1,2) says, by first applying p1 then p2:

    1 to 3 then 3 to 3 = 1 to 3
    2 to 2 then 2 to 1 = 2 to 1
    3 to 5 then 5 to 5 = 3 to 5
    4 to 4 then 4 to 4 = 4 to 4
    5 to 1 then 1 to 2 = 5 to 2

    Which gives (1,3,5)(1,2) = (3,1,5,4,2) = (3,1,5,2) (4 goes to 4 so leave it out), which is same answer I got doing it the long way.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91
    The following is instructive. Consider the permutation (2,4,5,1,3), which is short-hand for:
    (1,2,3,4,5)
    (2,4,5,1,3)
    It says change 1 to 2, 2 to 4, 4 to 1, 1 to 4 etc cyclically, or, in short, (1,2,4) = (2,4,1) = (4,1,2) , which all say the same thing.
    Also change 3 to 5, 5 to 3, 3 to 5, etc cyclically, or, in short, (3,5) = (5,3)
    Then (1,2,4)(3,5) is the same prescription for creating the permutation as the original. In long hand it is:
    (1,2,3,4,5)(1,2,3,4,5)=(1,2,3,4,5)
    (2,4,3,1,5)(1,2,5,4,3) (2,4,5,1,3)
    which says:
    1 to 2 then 2 to 2 = 1 to 2
    2 to 4 then 4 to 4 = 2 to 4
    3 to 3 then 3 to 5 = 3 to 5
    4 to 1 then 1 to 1 = 4 to 1
    5 to 5 then 5 to 3 = 5 to 3
    The same prescription in cyclical notation is:
    (124)(35)=(2,4,5,1,3) which is word for word the same as above.

    Real quick then (1,3,2,4)(4,3,2)=(2,3,4,1) ((1,3,2,4) then (4,3,2))
    The thought process is, what happens to 1, then 2, then 3, etc.
    1>3 then 3>2 = 2
    2>4 then 4>3 = 3
    3>2 then 2>4 = 4 (remember cyclical pattern)
    4>1 then 1>1 = 1

    (5,2) says change 5 to 2 and 2 to 5 and leave everything else unchanged, so in long hand it is:
    (1,2,3,4,5,6,7...)
    (1,5,3,4,2,6,7...)

    The inverse of
    (1,2,3,4)
    (3,1,4,2)
    is
    (1,2,3,4)
    (2,4,1,3)

    The inverse of 1 to 3 is 3 to 1, etc. Also (2,4,1,3)=(4,1,3,2)=(1,3,2,4) =(3,2,4,1) =(2,4,1,3) because they all say the same thing. Take 3 to 2, 4 to 1, 1 to 3, 3 to 2, cyclically

    Which answers original post, "How do I multiply permutations?," which in my opinion wasn't answered yet.
    Last edited by Hartlw; September 7th 2010 at 05:31 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91
    The preceding post is right as far as it goes. A problem arises when you try to do abc in cyclical notation. To do it in cyclical notation, lets say you do ab first per last post, which gives a result WHICH IS NOT IN CYCLICAL NOTATION, so you have to change it to cyclical notation before multiplying by c.

    (1234)(1234) (1234)
    (3412)(2431)=(3124)
    p1xp2=p3 think of top and bottom parentheses as one parenthesis.
    to do the same multiplication in cyclical notation, both terms on left have to be in cyclical form:
    (1,3)(2,4)(1,2,4) = [3124] = (132)
    [XXX] means the actual permutation of 1234
    Now mutiply (p1xp2)xp4
    (1234)(1234) (1234)
    (3124)(1342)=(4132)=[4132]=(142)
    in cyclical notation:
    (132)(234)=[4132]=(142)
    if a = (1234) then the inverse is (3124) = (1234)
    (3124) (1234) (2314)
    [3124]=(132) [3124]^-1 = [2314] = (123)
    So let's try the post 1 problem
    a=(1,3,5)(1,2)
    b=(1,5,7,9)
    and I have to calculate a^-1 * b * a
    ba=(1579)(135)(12)=[215476983]=(12)(3579)
    a=(135)(12)=[31542], a^-1=[25143]=(1253)
    a^-1ba=(1253)(12)(3579)=[172456983]=(2793)

    I'm sure there is a way to multiply cyclics to get another cyclic. Isomorphism seems to know but he won't give us the rationale, rule, or reference.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Dec 2009
    Posts
    224
    Isomorphism,

    I have another example from my book: (1,2,3).(2,4)(1,3,5)=(1,4,2,5)

    So, what happened to 3?? This is how I've done it:

    1 \to 2 \to 4

    2 \to 3 \to 5

    3 \to 1 \to 3

    4 \to 2

    5 \to 1

    I would end up with (1,4,2,5)(3). But why did they omit the cycle (3)?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by demode View Post
    Isomorphism,

    I have another example from my book: (1,2,3).(2,4)(1,3,5)=(1,4,2,5)

    So, what happened to 3?? This is how I've done it:

    1 \to 2 \to 4

    2 \to 3 \to 5

    3 \to 1 \to 3

    4 \to 2

    5 \to 1

    I would end up with (1,4,2,5)(3). But why did they omit the cycle (3)?
    It's implied. Say I was working in S_{143567346245779566435341786267053257789}. Then writing (123) including all the fixed points would take...a long time. And multiplying would be awful - you'd have to make sure someone hadn't tucked in a sneaky (12345 12346) in the midst of it all! This is the power of cyclic notation over writing normal permutations.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91
    Quote Originally Posted by demode View Post
    Isomorphism,

    I have another example from my book: (1,2,3).(2,4)(1,3,5)=(1,4,2,5)

    So, what happened to 3?? This is how I've done it:

    1 \to 2 \to 4

    2 \to 3 \to 5

    3 \to 1 \to 3

    4 \to 2

    5 \to 1

    I would end up with (1,4,2,5)(3). But why did they omit the cycle (3)?

    Thanks for the example demode. In case somebody missed the crucial step, the above gives the permutation [45321] which results from applying the three cyclic permutations. It was put in cyclic form by noting 1->4->2->5->1 = (1425). It also says 3 doesn't change so leave it out, its extraneous. The cyclic form is just a recipe for getting the original permutation of 12345:
    It says change 1 to 4, 2 to 5, 3 to 3, 4 to 2, 5 to 1 = [45321]
    Last edited by Hartlw; September 8th 2010 at 06:49 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Aug 2010
    Posts
    886
    Thanks
    91
    At this point we have pretty much nailed it. Just to summarize and tie up loose ends:

    (3,27,85) means 1->1, 2->2, 3->27, 4->4, 5->5, ...., 26->26, 27->85, 28->28,....., 84->84, 85->3

    Ex 1: (remove arrow head to ease typing)
    (3,25,57)(6,83,25)= 1-1-1, 2-2-2, 3-25-6, 4-4-4,....,6-6-83,...,25-57-57,.....,
    57-3-3,....., 83-83-25. or
    3-6, 6-83, 25-57, 57-3, 83-25, which becomes in cyclic notation,
    3-6-83-25-57-3 = (3,6,83,25,57,3)

    Ex 2: check against example in link above, which only gives answer:
    (1345)(243)(163)
    (1345)(243)=1-3-2, 2-2-4, 3-4-3, 4-5-5 = 1-2-4-5-1 = (1245)
    (1245)(163)= 1-2, 2-4, 3-1, 4-5, 5-6, 6-3 = 1-2-4-5-6-3-1 = (124563)

    in one step:
    (1345)(243)(163)=1-3-2, 2-4, 3-4-3-1, 4-5, 5-1-6, 6-3 = 1-2-4-5-6-3-1 = (124563)

    Ex 3: illustrate with result with more than one cycle
    (2143)(5246)=1-6, 2-1, 3-4, 4-3, 5-2, 6-5=(1-6-5-2-1)(3-4-3)=(1652)(34)

    Cyclic Inverse:
    b^-1 = [(145)(342)]^-1 = (243)(541)
    bb^-1= (145)(342)(243)(541) = (145)(1)(541) = 1
    b^-1b= (243)(541)(145)(342) = 1

    b^-1 = [(145)(342)(2516)]^-1 = (6152)(243)(541)
    bb^-1 = (145)(342)(2516)(6152)(243)(541) =(145)(342)(1)(243)(541)

    (1) = 1-1, 2-2, 3-3, 4-4, 5-5,.......

    HW Do problem in post 1
    Last edited by Hartlw; September 8th 2010 at 10:54 AM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by demode View Post
    Oh I see. But I still don't understand why you gave that method in your first post. Isn't it easier to just write all the numbers in each cycle backward?
    Yes it is. Both are same anyway.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. multiply through with sin and cos
    Posted in the Trigonometry Forum
    Replies: 5
    Last Post: November 6th 2010, 07:57 AM
  2. Multiply
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 26th 2009, 03:20 AM
  3. Multiply
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 27th 2009, 06:01 PM
  4. multiply
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: November 29th 2008, 01:17 PM
  5. multiply
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 13th 2006, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum