Properties of a permutation matrix 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.
 A: 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$.
A: I suggest constructing a group homomorphism $S_n\rightarrow GL_n$ whose image is permutation matrices. However if you want to avoid using group theory, here is an alternate proof.

First $P$ is diagonalizable over $\mathbb C$ since it is orthogonal (see here). Suppose $x$ is an eigenvector of $P$ with eigenvalue $\lambda$. Let $X\subseteq\mathbb C$ be the set of components of $x$, so $|X|\leq n$. Each component of $\lambda x=Px$ is also a component of $x$, so $\lambda X\subseteq X$. Since $x\neq0$, we can choose some nonzero $a\in X$. Then
$$
  a,\lambda a,\ldots,\lambda^n a\in X.
$$
Since $|X|\leq n$, two of these values must be equal. Suppose $\lambda^ia=\lambda^ja$ where $0\leq i<j\leq n$. Then $\lambda^{j-i}=1$. Thus $\lambda^{n!}=1$. This holds for each eigenvalue, so $P^{n!}=I$.
A: Here is an outline of how you can reason through the proof.
Lemma: A permutation matrix is invertible (hint, consider $P^T$)
Corollary: A permutation matrix is the same as an invertible matrix where every column is a standard basis vector.
Lemma: The product of two permutation matrices is a permutation matrix.
By the pigeonhole principle, since there are only finitely many $n\times n$ permutation matrices ($n!$ of them), and since there are infinitely many powers of $P$, we can find $i,j$ (different, but at most $n!$ such that $P^i=P^j$.  Now, use the fact that $P$ is invertible.  
