What are the properties of eigenvalues of permutation matrices? Up till now, the only things I was able to come up/prove are the following properties:


*

*$\prod\lambda_i = \pm 1$

*$ 0 \leq \sum \lambda_i \leq n$, where $n$ is the size of the matrix

*eigenvalues of the permutation matrix lie on the unit circle 


I am curious whether there exist some other interesting properties.
 A: 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.

A: 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.
