If $P$ is a $n$-by-$n$ full rank permutation matrix (i.e., its characteristic polynomial is $x^n - 1 = 0$), is it true that the eigenvalues of $P + P^T$ are exactly $x^k + \overline{x^k}$, where $x^k$ is a $n$th root of unity?
(In case it matters, I'm most interested in the case $n \geq 4$)
Your writing is not clear (what is a full rank permutation ?).
Let $P$ be a permutation. If $P$ decomposes in a product of disjoint cycles of length $k_i$: $P=c_{k_1}\cdots c_{k_j}$ where $c_{k_1}+\cdots +c_{k_j}=n$, then its characteristic polynomial is $(x^{c_{k_1}}-1)\cdots(x^{c_{k_j}}-1)$, the roots of which, are roots of $x^p-1$, where $p=lcm((c_{k_i}))$. In particular, the eigenvalues of $P$ are roots of unity. For instance, if $n=10$, then the order of the permutation $P=(1,2)(3,4,5),(6,7,8,9,10)$ is $30$ and each eigenvalue $\lambda$ satisfies $\lambda^{30}=1$.
Since $P$ is orthogonal, it can be diagonalized in an orthonormal complex basis. Thus there is a unitary $Q$ s.t.
$P=Qdiag(e^{i\theta_1},\cdots, e^{i\theta_n})Q^*, P^T=Qdiag(e^{-i\theta_1},\cdots, e^{-i\theta_n})Q^*$ and
$P+P^T=Qdiag(2\cos(\theta_1),\cdots,2\cos(\theta_n))Q^*$.
Of course, if $P$ is a cycle, then its characteristic polynomial is $x^n-1$ and $\theta_k=2k\pi/n$.