Square of a permutation matrix

1. Feb 14, 2015

ilyas.h

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. Feb 14, 2015

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.

3. Feb 14, 2015

ilyas.h

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.

4. Feb 14, 2015

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.

5. Feb 14, 2015

ilyas.h

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?

6. Feb 14, 2015

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.

7. Feb 14, 2015

ilyas.h

thank you, very helpful. I understand everything now.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook