Permutation matrix/Cycle/C/Eigenvalues/Fact/Proof

Proof

We have

${}{\begin{aligned}M_{\rho }(v_{\zeta })&=M_{\rho }(\zeta ^{k-1}e_{i_{1}}+\zeta ^{k-2}e_{i_{2}}+\cdots +\zeta e_{i_{k-1}}+e_{i_{k}})\\&=\zeta ^{k-1}M_{\rho }(e_{i_{1}})+\zeta ^{k-2}M_{\rho }(e_{i_{2}})+\cdots +\zeta M_{\rho }(e_{i_{k-1}})+M_{\rho }(e_{i_{k}})\\&=\zeta ^{k-1}e_{i_{2}}+\zeta ^{k-2}e_{i_{3}}+\cdots +\zeta e_{i_{k}}+e_{i_{1}}\\&=e_{i_{1}}+\zeta ^{k-1}e_{i_{2}}+\zeta ^{k-2}e_{i_{3}}+\cdots +\zeta e_{i_{k}}\\&=\zeta (\zeta ^{k-1}e_{i_{1}}+\zeta ^{k-2}e_{i_{2}}+\cdots +\zeta e_{i_{k-1}}+e_{i_{k}})\\&=\zeta v_{\zeta }.\end{aligned}}$

Since there are ${}k$ different ${}k$-th roots of unity in ${}\mathbb {C}$, these vectors are linearly independent due to fact, and they generate a ${}k$-dimensional linear subspace ${}U$ of ${}K^{n}$. In fact, we have

${}U=\langle e_{i_{j}},\,j=1,\ldots ,k\rangle \,.$

Since the vectors ${}e_{i}$, ${}i\neq {i_{j}}$, are fixed vectors, the ${}v_{\zeta }$ together with the ${}e_{i}$, ${}i\neq {i_{j}}$, form a basis consisting of eigenvectors of ${}M_{\rho }$. Hence, ${}M_{\rho }$ is diagonalizable.

To fact