What are the properties of eigenvalues of permutation matrices?

Solution 1:

A permutation matrix is an orthogonal matrix (orthogonality of column vectors and norm of column vectors = 1).

As such, because an orthogonal matrix "is" an isometry

$$\tag{1}\|PV\|=\|V\|$$

If $V$ is an eigenvector associated with eigenvalue $\lambda$, substituting $PV=\lambda V$ in (1) we deduce

$$|\lambda|=1.$$

Moreover, as $P^p=I_n$ ($p$ is the order of the permutation) these eigenvalues are such that $\lambda^p=1$; therefore

$$\lambda=e^{i k 2\pi/p}$$

for some $k \in \mathbb{Z}$.

Let us take an example: consider the following permutation decomposed into the product of two disjoint support cycles

a cycle $\color{red}{(5 4 3 2 1)}$ of order $5$ and a cycle $\color{blue}{(6 7 8)}$ of order $3$.

Its associated matrix is:

$$\left(\begin{array}{ccccc|ccc} 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & \color{red}{1} & 0 & 0 & 0\\ \color{red}{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{blue}{1}\\ 0 & 0 & 0 & 0 & 0 & \color{blue}{1} & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & \color{blue}{1} & 0\end{array}\right)$$

Its cycle structure is reflected (see picture) into the five eigenvalues $\color{red}{e^{2i k\pi/5}}$ and the three eigenvalues $\color{blue}{e^{2i k\pi/3}}$.

Please note that eigenvalue $1$ is - in a natural way - a double eigenvalue, and more generally with multiplicity $m$ if the permutation can be decomposed into $m$ disjoint cycles.

Solution 2:

A permutation may be written as a unique product of primitive cycles $\pi = (c_1)\cdots(c_k)$. This corresponds to writing the matrix in block form with each cycle representing a block. Each cycle of length $|c_i|$ has precisely the $|c_i|$'th roots of unity as eigenvalues. This tells you at least precisely when a collection of eigenvalues (with multiplicity) may correspond to a permutation matrix.