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 Inverses

  1. Jul 28, 2014 #1
    1. The problem statement, all variables and given/known data
    Prove that there is a permutation sigma, such that sigma * (1 2 3) * sigma inverse= (4 5 6).

    2. Relevant equations



    3. The attempt at a solution
    I know that since the order of the two cycles is the same there must be a sigma such that the two permutations are equal but I am stumped as to how to derive a specific one. Would I have to do proof by contradiction using identity as was done in an earlier problem I completed or am I way off?

    Thank you!
     
  2. jcsd
  3. Jul 28, 2014 #2

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't see how to make sense of the product ##\sigma(1\ 2\ 3)\sigma^{-1}## unless I interpret (1 2 3) as a permutation (not as an element of the domain of ##\sigma##). Is (x y z) your notation for the permutation f such that f(1)=x, f(2)=y, f(3)=z? In that case, (1 2 3) is the identity map, and the product is equal to (1 2 3) no matter what ##\sigma## is.
     
  4. Jul 28, 2014 #3
    In an introductory abstract algebra course, and in the proper context, ##(a_1\dots a_n)## is standard notation denoting the cyclic permutation mapping ##a_i## to ##a_{i+1}## for ##i<n## and ##a_n## to ##a_1##.
     
    Last edited: Jul 28, 2014
  5. Jul 28, 2014 #4
    If the problem just asks you to prove the existence of such a permutation, then you can just invoke whatever theorem it is that is allowing you to make the above statement. You don't necessarily need to construct a permutation.
     
  6. Jul 28, 2014 #5

    pasmith

    User Avatar
    Homework Helper

    Hint: (1 4)(1 2 3)(1 4) = (2 3 4). Can you now see how to construct your sigma as a product of disjoint transpositions?
     
  7. Jul 28, 2014 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    OK, but what does ##(1\,2\,3)## stand for when the permutations go over the numbers ##1, \ldots, 6## ?
     
  8. Jul 28, 2014 #7
    I am actually having a difficulty understanding how to construct permutations into disjoint cycles, and I am trying to read various sources but it still does not make sense. My book works from right to left for disjoint cycles. Can someone please explain it to me? Thank you.
     
  9. Jul 29, 2014 #8

    pasmith

    User Avatar
    Homework Helper

    The permutation which cyclically permutes 1, 2 and 3 and fixes 4, 5, and 6. By convention elements which are fixed are omitted from the cycle notation.
     
  10. Jul 29, 2014 #9

    That helped me understand cycle notation a bit better, thank you.

    So am I correct in making this assumption now?
    (1 2 3 4 5 6
    2 3 1 4 5 6) times sigma times sigma inverse equals:

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

    Am I allowed to simplify this?
     
  11. Jul 30, 2014 #10
    Shameless bump... sorry!
     
  12. Jul 30, 2014 #11

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Gopher and pasmith explained the (x ... y) notation, but no one has explained what it means when it's broken up over two lines. Can I assume that
    (1 2 3 4 5 6
    2 3 1 4 5 6)
    is the permutation that takes 1 to 2, 2 to 3, 3 to 1, and the other numbers to themselves? In other words, it means exactly the same as (1 2 3)? Then you're asking if ##(1\ 2\ 3)\sigma\sigma^{-1}=(4\ 5\ 6)##? The left-hand side is obviously equal to (1 2 3), so no, this equality doesn't hold.
     
  13. Jul 30, 2014 #12
    Hi Fredrik, yes I believe (1 2 3) is just the shortened form of the cycle that takes 1 to 2, 2 to 3, 3 to 1, and maps 4, 5, 6 to themselves.
    I was confused as to how that would hold too, and I am still not sure if I understood the meaning correctly.
     
  14. Jul 30, 2014 #13

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Groups of permutations aren't commutative (Abelian), so you don't have xy=yx for all x,y. This means that you need to keep your factors in the correct order.
     
  15. Jul 30, 2014 #14
    So I should not expand the permutations and just keep them as they are written in the question? I do not understand how that will allow me to conclude anything, though.
     
  16. Jul 30, 2014 #15

    Fredrik

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    pasmith gave you a huge hint in post #5. It would be hard to tell you more without completely solving the problem.
     
  17. Jul 30, 2014 #16
    I do not wish to get the answer from others, nor do I want it to seem like that.
    I am simply confused on how to make disjoint transpositions (from right to left) and I would appreciate it if I could get a detailed example and explanation, so I can understand this concept before attempting the problem. I've looked in various sources for explanations but I can't quite wrap my head around it.
     
  18. Jul 30, 2014 #17

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    One way to transform (1 2 3) to (4 5 6) is to transpose 1 and 4, transpose 2 and 5, and transpose 3 and 6. Can you combine this fact with the hint given by pasmith?
     
  19. Jul 30, 2014 #18

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, that's exactly what it means. This so-called two-line notation is due to Cauchy, according to Wikipedia:

    http://en.wikipedia.org/wiki/Permutation#Definition_and_usage
     
  20. Jul 31, 2014 #19
    Is the transposition you described equivalent to (1 4) (2 5) (3 6)?

    And in that case would (1 2 3)= (1 3) (1 2)? Also, (4 5 6)= (4 6) (4 5)?
     
  21. Jul 31, 2014 #20

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, technically it's not a transposition (which interchanges exactly two elements and leaves the rest unchanged), but a composition of transpositions.

    Now how can you use (1 4) (2 5) (3 6) to map (1 2 3) to (4 5 6)?

    Hint: if ##\sigma## is any permutation, then ##\sigma (x_1 x_2 \ldots x_n)\sigma^{-1} = (\sigma(x_1) \sigma(x_2) \ldots \sigma(x_n))##
     
  22. Jul 31, 2014 #21
    So, sigma *((1 4) (2 5) (3 6)) * sigma^-1 = sigma(1 4) sigma (2 5) sigma (3 6).
    There is one operation that transforms these to be equal to each other; is it a matter of guess and check to determine this, or can I systematically eliminate?
     
  23. Jul 31, 2014 #22

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, that's not quite right. The goal is to transform (1 2 3) to (4 5 6). So let's start by writing what we hope to achieve:
    $$\sigma (1 2 3) \sigma^{-1} = (4 5 6) = (\sigma(1) \sigma(2) \sigma(3))$$
    Now we need to find a permutation ##\sigma## which makes this equation true. Let's do this in three steps, and then at the end, we will conclude what ##\sigma## must be.

    If you take a look back at pasmith's hint, we have
    $$(1 4) (1 2 3) (1 4) = (2 3 4)$$
    I will rewrite the cycle on the right hand side in a more suggestive but equivalent way:
    $$(1 4) (1 2 3) (1 4) = (4 2 3)$$
    What this shows is that if we start with (1 2 3), and multiply on both sides by (1 4), we get (4 2 3). In other words, the 1 is replaced by 4 and everything else stays the same. So we have achieved one step out of three. Can you see what the next step is, to obtain (4 5 3) on the right hand side?
     
  24. Jul 31, 2014 #23
    So can one do (1 4) (1 5 3) (1 4) to obtain (4 5 3)?
    And then to obtain (4 5 6) do (1 4) (1 6 3) (1 4)?
     
  25. Jul 31, 2014 #24

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    One can do that, but you didn't have (1 5 3) to start with, so this doesn't help. In the first step, we got as far as (4 2 3). How can we transform (4 2 3) to (4 5 3)?
    No... (1 4)(1 6 3)(1 4) would be (4 6 3).
     
  26. Jul 31, 2014 #25
    To get from (4 2 3) to (4 5 3) replace 2 with 5. So (1 4) (1 2 5) (1 4)?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted