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}.
$$
 A: 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\}.
$$
