Diagonalize a permutation matrix with roots of unity So I have this linear transformation:
$f\left( e_{i}\right) =\begin{cases}e_{i+1} & 1\leq i <n\\ e_{1}&i=n\end{cases}$
over ℂ, with ε = ($e_{1}$, $e_{2}$, ... , $e_{n}$) the standard basis for $\mathbb{C} ^{n}$.
I already showed that $f^{n}$ = $Id_{\mathbb{C} ^{n}}$, which also means that $\left[ f\right] _{\varepsilon }^{n}$ = $I_{n}$.
In addition, the characteristic polynomial is obvious: $p(x) = x^{n}-1$, which means that the eigenvalues are Nth root of unity, more specifically: $cis\left( \dfrac{2\pi k}{n}\right)$.
Now Iv'e been asked to diagonalize $\left[ f\right] _{\varepsilon }$, meaning finding invertible $P$, and $P^{-1}$, and $D$ such that $D$ = $P^{-1}$$\left[ f\right] _{\varepsilon }$$P$.
Obviously, D is the diagonal matrix with the eigenvalues on it's main diagonal, but I'm not sure how can I find $P$ and $P^{-1}$
 A: Note that $\mathrm{cis}(t)=\exp(it)$, so in the following, all occurrences of $\exp$ can be replaced with $\mathrm{cis}$. I use the exponential as it's more common.
The matrix of $f$ in the canonical basis is:
$$A=\begin{bmatrix}
0 & 0 & 0 & \dots & 0 & 1\\
1 & 0 & 0 & \dots & 0 & 0\\
0 & 1 & 0 & \dots & 0 & 0\\
0 & 0 & 1 & \dots & 0 & 0\\
\vdots  & \vdots  &  & \ddots &  & \vdots \\
0 & 0 & 0 & \dots & 1&0
\end{bmatrix}$$
You have found that the characteristic polynomial is $x^n-1$, and that the eigenvalues are thus $\exp(\frac{2ik\pi}{n})$, with $i^2=-1$ and $1\le k\le n$. Since the eigenvalues all have multiplicity $1$, the matrix $A$ is diagonalizable. Define the matrix $P$ by $P_{jk}=\exp(\frac{2ijk\pi}{n})$, and consider $v$, the $k$-th column of $P$.
Then $v_j=\exp(\frac{2ijk\pi}{n})$, and $Av=w$, with $w_j=\exp(\frac{2i(j+1)k\pi}{n})$ for $j<n$, and $w_n=\exp(\frac{2ik\pi}{n})$. But, because $\exp(2i\pi)=1$, $w_n=\exp(\frac{2i(1+n)k\pi}{n})$. Therefore, for all $j$,
$$w_j=\exp(\frac{2i(j+1)k\pi}{n})=\exp(\frac{2ik\pi}{n})\cdot\exp(\frac{2ijk\pi}{n})=\exp(\frac{2ik\pi}{n})v_j$$
That is $Av=\lambda v$, with $\lambda=\exp(\frac{2ik\pi}{n})$.
So the columns of $P$ are eigenvectors of $A$ for the corresponding eigenvalues, and we have the eigendecomposition of $A$:
$$A=P^{-1}DP$$
Where $D$ is diagonal, and $D_{kk}=\exp(\frac{2ik\pi}{n})$.
