Properties of a permutation matrix

Question

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.

Answer 1

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$.

Answer 2

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$.

Answer 3

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.