Powers of a permutation matrix.

[Dafe]

Homework Statement

If you take powers of a permutation matrix,
why is some P^k eventually equal to I?

Homework Equations

-

The Attempt at a Solution

From the solutions manual of the book:

There are n! permutation matrices of order n.

Eventually, two powers of P must be the same:
P^r = P^s

Miltiply (P^-1)^s to find P^{r-s}.

Certainly r-s \leq n!

I do not quite see how this answers the question.
I understand that there are n! permutation matrices.

That two powers of P must be the same is also understandable, since taking powers of P just rearranges the rows. Since there are a finite number of ways to rearrange the rows, two powers will eventually be the same.

The two other points, I do not understand.

Would someone be so kind to explain this to me in some detail?

Thanks

 

[D H]

Eventually, two powers of P must be the same:
P^r = P^s

Miltiply (P^{-1})^s to find P^{r-s}.

You are missing two key things here. Eventually two different powers of P must be the same:

P^r = P^s\quad, r \ne s

You can assume that r>s. The other thing you are missing is that you need to multiply both sides of the equality by the inverse of P^s.

See if you can take it from here.

 

[Dafe]

Hi D H,

Is this what you are leading me towards:
P^r(P^s)^{-1} = P^s(P^s)^{-1}

P^{(r-s)} = P^0

P^{(r-s)} = I

Thank you.