how to find the eigenvalues of permutation matrices?

I searched online but didnt find a clear explanation to how can I find the eigenvalues and eigenvectors of permutation matrices.

can someone help?

for example: $$ \begin{pmatrix} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ \end{pmatrix}. $$

Solution 1:

Since orthogonal matrices are unitary, they are in particular normal and so they admit an orthogonal basis of eigenvectors. This means they can be unitarily diagonalized; what we will use here is block-diagonalization.

I'll work in the concrete case of your example. The permutation, acting on the canonical basis, is $$ Se_1=e_4, Se_2=e_5, Se_3=e_2, Se_4=e_1, Se_5=e_3. $$ The cycles are $$ (1\ 4)(2\ 5\ 3). $$ This means that reordering the basis as $e_1, e_4, e_2, e_5, e_3$, the permutation $S$ will be represented as $$ \begin{bmatrix} 0&1&0&0&0\\ 1&0&0&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&1&0&0 \end{bmatrix} $$ At this point, the eigenvalues of $S$ are given by the eigenvalues of $\begin{bmatrix} 0&1\\1&0\end{bmatrix}$ and $\begin{bmatrix}0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix} $. They will always be cyclic matrices. So they are matrices $S_k$ such that $S_k^k=I$. This implies that the eigenvalues are the $k^{\rm th}$ roots of unity.

In your example the eigenvalues (counting multiplicities) are $$ 1,-1, 1, \frac{-1+i\sqrt3}2, \frac{-1-i\sqrt3}2. $$

In general, if your permutation is a product of cycles of length $n_1,\ldots,n_r$, then the eigenvalues will be $$ \bigoplus_{j=1}^r\{e^{\ell 2\pi i / n_j}:\ \ell=0,\ldots,n_j-1\}. $$