Multiplying permutation matrix by itself to get identity What is rigorous proof that any permutation matrix $P$ raised to some power $k$ equals identity matrix i.e. $P^k= I_n$?
Is there any way to find the smallest $k$ other than looking at the matrix, finding all its cycles and then calculating least common multiple?
Thank You!
 A: The group of permutation matrices of size $n$ is isomorphic to the symmetric group $S_n$. Any permutation $\sigma$ has finite order, hence any permutation matrix also has finite order.
Added: decomposition of a permutation as  a product of disjoint cycles (example)
Let's take the permutation of $S_8$:
$$\sigma=\begin{pmatrix}1&2&3&4&5&6&7&8\\5&4&6&3&1&7&8&2\end{pmatrix}$$
We also can represent this permutation in the following way: starting with $1$, we compute its image by $\sigma$, then the image of $\sigma(1)$, and so on, until we get back to $1$. When this is done, we have obtained a cycle. If there remains elements in $\{1,2,\dots,8\}$, we do the same starting from the smallest element.
Here we obtain:
$$\sigma=(1\,5)(2\,4\,3\,6\,7\,8)$$
Thus $\sigma$ is the product of a $2$-cycle (a ‘transposition’) and a $6$-cycle.
Now a cycle of length $\ell$ has order $\ell$: indeed
\begin{align*}
\sigma^2&=(2\,3\,7)(4\,6\,8)& \sigma^3&=(2\,6)(3\,8)(4\,7)\\
\sigma^4&=(2\,7)(3)(4\,8)(6)& \sigma^5&=(2\,8\,7\,6\,3\,4) \\
\sigma^6&=\operatorname{id}
\end{align*}
Also, the order of the product of disjoint cycles is the l.c.m. of the orders (lengths) of the cycles.
