Let $P$ be a permutation matrix, i.e. an $n \times n$ matrix consisting of
$0$ and $1$ such that there is exactly one $1$ in every row and every column.
I want to prove that there exists some $N > 0$ such that $P^N = I.$
I was given the recommendation that I should consider how there is only
finitely many permutations. This suggests to me that I should consider
the fact that if $N$ does exist, $N$ must be finite. However, I am considering
going about this proof using an assumption for the sake of contradiction,
such that
$P^N = Q, Q \neq I$.
I think the first step is proving that if $P$ is a permutation matrix, then
$P^N$ is a permutation matrix for $N > 0.$ I imagine that I can do this
inductivity by showing that $P^2$ is a permutation matrix. However, is
this a bit of an unnecessary way to prove our lemma? Any suggestions would be
appreciated.
Best Answer
Hint: By the pigeonhole principle, there exist integers $m<n$ such that $P^m=P^n$. Conclude that we necessarily have $P^{n-m}=I$.