Question

Why must an exponent 'k' exist such that
P^k = I
for any permutation matrix P ?

Answer 1

If you don't like matrices, maybe consider an example :

Answer 2

Imagine four couples,
4 girls in first column
4 boys in second column.

Answer 3

Initially assume that they are all paired up correctly. (each boy adjacent to his correct girl)

Answer 4

Something something group theory

Answer 5

Next, change the positions of boys using some definite rule. For example :
g1 b1
g2 b2
g3 b3
g4 b4

changes to
g1 b2
g2 b1
g3 b4
g4 b3

(Girls 1 & 2 have swapped their boys, girls 3 & 4 have swapped their boys)

Answer 6

What happens if you apply the change again ?

Answer 7

Yeah it is group theory @HolsterEmission

Answer 8

Sorry, wasn't sure if you were asking or telling :)

Answer 9

Clearly the girls get their original boys back if we apply the same change one more time.

If we repeatedly apply the "same" change to the positions of the boys, will there occur a state in which all the girls are paired to their original boys ?

Answer 10

That is my attempt to translate the problem from matrices to something that more ppl can relate to haha

Answer 11

There are only a finite number of permutations (assuming P is finite). That should lead you to the answer

Answer 12

Awesome !
That means the initial permutation must repeat after a while.
P^a = P

The exponent a-1 yields identity
Thanks Zarkon :)

Answer 13

I would say that there is some n and m (WLOG assume n>m) such that

\[P^n=P^m\]

and thus

\[p^{n-m}=I\]

Answer 14

my \(p\) should be \(P\)...but you know that.

Answer 15

Much better!
But aren't we assuming that P is invertible ?

Answer 16

Nvm, it is invertible ..

Answer 17

;) all permutation matrices are invertable...proof is simple

Answer 18

Basically you're saying that there will be some repetition, not necessarily the P..

Answer 19

correct

Answer 20

I realised immediately after posting the reply haha

Answer 21

Here's some little extra stuff for fun. Permuting boys and girls around doesn't change the total number of kids, so the vector \(v\) holding a single kid in each of the components (wow!) should have the same length before and after a permutation \(P\).

\[|Pv| = |v|\]

Cool thing is once you accept that to be true, we can write that out in matrix notation as:

\[\sqrt{(Pv)^\top (Pv)} = \sqrt{v^\top v}\]
A little bit of algebra gets us to:

\[v^\top P^\top P v = v^\top I v\]

So right away we see

\[P^\top P = I\]
and that necessarily means the transpose of P is the inverse of P!
\[P^\top = P^{-1}\]

Useful to know!

Answer 22

That's really a cute way to show that the inverse of a permutation matrix is it's transpose !

Answer 23

This trick works for all orthogonal and unitary matrices, so like reflections and rotations and some other stuff too.

Answer 24

Fundamentally, the set of nxn permutation matrices is isomorphic to the symmetric group \(S_n\) and basically @Zarkon 's proof is the general argument for why any element of a finite group has a finite order.