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

Square of a permutation matrix

  1. Feb 14, 2015 #1
    say i have the matrix (4,2,5,6,3,1) and on top I have (1,2,3,4,5,6) i.e. a 2x6 permutation matrix. Let's call it sigma.

    how would I calculate (sigma)^2?

    I can break it down into cycles:

    sigma = <1,4,6>compose<3,5>

    thanks.
     
  2. jcsd
  3. Feb 14, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You can do it element by element. For example, 4 gets mapped to 6. What does 6 get mapped to? That will give you one entry in your matrix for sigma^2.
    Alternatively, do it cycle by cycle with a similar approach.
     
  4. Feb 14, 2015 #3
    sigma=

    1 2 3 4 5 6
    4 2 5 6 3 1

    1 gets mapped to 4, 4 gets mapped to 6 => 1 gets mapped to 6.

    This is the wrong approach because by doing this, you're calculating (sigma)^-1, that's the inverse.
     
  5. Feb 14, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    No, 1->6 is a part of sigma2. This specific example happens to have some mappings common with its inverse because sigma3 keeps several elements unchanged, but that is pure coincidence.
     
  6. Feb 14, 2015 #5
    but isn't that method you suggested the exact same algorithm for finding the inverse of a permutation? maybe im getting mixed up.

    how would you find the inverse of the permutation then?
     
  7. Feb 14, 2015 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Swap the two lines and sort the columns to make the first line "1 2 3 4 5 6" again.
    This is equivalent to "for 1, look where it appears in the bottom line, find which elements gets mapped to 1, map 1 to this element" and so on.
     
  8. Feb 14, 2015 #7
    thank you, very helpful. I understand everything now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Square of a permutation matrix
Loading...