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!

Conjugation of permutations

  1. Oct 5, 2011 #1
    1. The problem statement, all variables and given/known data
    Suppose A = (a1 a2 . . . ak) and B = (b1 b2 . . . bk) are two cycles of length k. Find a permutation C, such that CAC-1.

    Next, suppose A and B have the same cycle structure. The question is again the same. Find a permutation C, such that CAC-1.

    3. The attempt at a solution
    I've been looking at this for hours now, and I just don't seem to get it. I've also tried writing out examples, and it doesn't seem to click. I know what it's supposed to do, but I just can never find the proper permutation C. Can anyone offer any help? The homework's due tomorrow, so I'm really worried.
     
  2. jcsd
  3. Oct 5, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Hello Ryker!! :smile:

    I'm going to give you a hint. If [itex]A=(a_1~...~a_n)[/itex]. Can you prove that

    [tex]CAC^{-1}=(C(a_1)~...~C(a_n))[/tex]

    ??? Does this help you with what you need to prove?
     
  4. Oct 5, 2011 #3
    Hey there, and thanks for the quick reply. I actually already had that part, so I assumed C(a1) = b1, ... , C(ak) = bk. Is this correct?

    Is it then [itex]C = \begin{pmatrix} {a}_{1} & {a}_{2} & ... & {a}_{k} \\ {b}_{1} & {b}_{2} & ... & {b}_{k} \end{pmatrix} ?[/itex]

    But assuming it is, I'm having loads of trouble getting that into cycle form. I probably can't just leave C as stated above, can I?
     
  5. Oct 5, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I think that's ok. Getting it into cycle form will be very hard, so I don't expect that they want you to do this. If I was your professor and I would read the above post, then I would give you full marks :smile:

    You can try to get it into cycle form, but it won't be easy... (not easy = I don't think I know how to do it right now)
     
  6. Oct 5, 2011 #5
    But is it even possible to get it in cycle form when given unknown a's and b's? I mean, you're not even given which ai = bi, so how would you turn this into cycles?

    But what about the second part? I know we can decompose both A and B into cycles of same length and then we can apply C, such that, say A = CA1C-1 ° CA2C-1 ° ... ° CAkC-1, but again, how do I turn this into a characterization or description of C? The question namely asks to find such a permutation, so I figure I need to say more than just this. Any thoughts?
     
  7. Oct 6, 2011 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I don't actually think it is possible to find such an explicit C. It will be very hard to say the least.

    The thing is that the C can be basically everything. Every possible permutation occurs as a C. So I don't think that giving the disjoint cycle representation is really all that necessary. What you did is probably ok.
     
  8. Oct 6, 2011 #7
    Hmm, I see. I guess with stating only this, I kind of feel like cheating, because it seems I haven't really done anything to pinpoint that C! We've namely proven certain parts of the conjugate iff same cycle structure theorem, and these two are the remaining parts. And my elaboration then offers little additional value :smile: But I guess if you say that's fine, then I'll leave it at this. Because like I said, I've been struggling with this for hours trying to find a different way of describing C, but didn't have any success.

    Oh, one last thing. Would you happen to have any hints on how to find an order of a specific permutation WITHOUT using the least common denominator of cycle orders method, and WITHOUT just applying the permutation over and over again until you reach it again? I was thinking you can just look at the what the permutation does to specific elements and how many applications are needed for each of them to come back to the original one, and then just looking at the least number at which they all "line up", i.e. the number of applications of a permutation where all elements are in their original places. But then this again feels kind of the same thing as the least common denominator thing (even though it's not cycles), so I'm not sure whether there's another way. Supposedly, there's a really short solution, so I was just wondering whether there's any other trick to establish the order.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook