Given an $n\times n$ matrix A with rows that are some permutation of $I_n$, find the smallest integer $m$ such that $A^m = I_n$

Question

Basically as the title says: Given an $n\times n$ matrix A with rows that are some permutation of $I_n$, find the smallest integer $m$ such that $A^m = I_n$. In other words, given a matrix that is the identity matrix with its columns rearranged, how many times do we have to multiply A by itself to recover the identity matrix?

I suppose we can just apply he same permutation $m$ times but how to find the answer more elegantly?

Also curious how to solve this for $m \times n$ matrices and not just square matrices? Edit: obviously not possible

Answer 1

You want to translate the permutation matrix $A$ into a permutation $\sigma$, then proceed. Let me do one example, and you should be able to see how to do it for other permutation matrices too. So let's say $$A=\begin{bmatrix}0&0&1&0&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&0&1&0\\1&0&0&0&0\end{bmatrix}.$$ Then, notice that for any $(x_1,x_2,x_3,x_4,x_5)$ (don't worry about which vector space this vector belongs to, as that's not important here). We have $$A(x_1,x_2,x_3,x_4,x_5)^T=\begin{bmatrix}x_3\\x_2\\x_5\\x_4\\x_1\end{bmatrix}.$$ So we may associate $A$ to a permutation $\sigma:\{1,2,3,4,5\}\rightarrow\{1,2,3,4,5\}$ defined by $$\sigma(1)=3,\sigma(2)=2,\sigma(3)=5,\sigma(4)=4,\sigma(5)=1.$$ I hope the correspondence is clear to you. Now for permutations it is convenient to express them in disjoint cycle notation. The way this is done is by noticing that

1. The number $1$ is mapped to $3$ which is mapped to $5$, which is finally mapped back to $1$.
2. The numbers $2$ and $4$ are mapped to themselves.

So we can write $\sigma=(1\enspace 3\enspace 5)(2)(4)$. Again, I hope the correspondence is clear. Now, a fact about permutations is that the smallest positive integer $m$ such that $\sigma^m$ is the identity function is $$\text{lcm}(\text{cycle lengths}).$$

In our case, the cycle lengths are $3$, $1$, and $1$, so $m=\text{lcm}(3,1,1)=3$. So, the smallest integer such that $\sigma^m$ equals the identity function is $m=3$. Translating back to matrices, we have $A^3=I$.

I also should have clarified that by $\sigma^m$ I mean function composition: $$\sigma^m=\underbrace{\sigma\circ\cdots\circ\sigma}_{m\text{ times}}$$

I hope this example helps with your question in general.