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.