How Do You Calculate the Square of a Permutation Matrix?

[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.

 

[mfb]

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.

 

[ilyas.h]

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.

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.

 

[mfb]

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

No, 1->6 is a part of sigma². This specific example happens to have some mappings common with its inverse because sigma³ keeps several elements unchanged, but that is pure coincidence.

 

[ilyas.h]

No, 1->6 is a part of sigma². This specific example happens to have some mappings common with its inverse because sigma³ keeps several elements unchanged, but that is pure coincidence.

but isn't that method you suggested the exact same algorithm for finding the inverse of a permutation? maybe I am getting mixed up.

how would you find the inverse of the permutation then?

 

[mfb]

how would you find the inverse of the permutation then?

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.

 

[ilyas.h]

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.

thank you, very helpful. I understand everything now.