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!
Best Answer
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.