# Endomorphism/Finite order/Permutation matrices/Eigenvalues/Section

We consider linear mappings
    $\varphi \colon V\longrightarrow V$
with the property that some power of it is the identity, say
    $\varphi ^{k}=\operatorname {Id} _{V}\,,$
that is, $\varphi$ has finite order. Typical examples are rotations around an angle of the form ${\frac {360}{k}}$ degree. The polynomial $X^{k}-1$ annihilates this endomorphism, and is, therefore, a multiple of the minimal polynomial.

## Definition

Let $K$ be a field, and $n\in \mathbb {N}$ A zero of the polynomial
    $X^{n}-1$
in $K$ is called an $n$-th root of unity
$K$

## Lemma

Let $n\in \mathbb {N} _{+}$. The zeroes of the polynomials $X^{n}-1$ over $\mathbb {C}$ are
    $e^{2\pi {\mathrm {i} }k/n}=\cos {\frac {2\pi k}{n}}+{\mathrm {i} }\sin {\frac {2\pi k}{n}},k=0,1,\ldots ,n-1.$
$\mathbb {C} [X]$
    $X^{n}-1=(X-1){\left(X-e^{2\pi {\mathrm {i} }/n}\right)}\cdots {\left(X-e^{2\pi {\mathrm {i} }(n-1)/n}\right)}\,.$

### Proof

The proof uses some basic facts about the complex exponential function. We have
    ${\left(e^{2\pi {\mathrm {i} }k/n}\right)}^{n}=e^{2\pi {\mathrm {i} }k}={\left(e^{2\pi {\mathrm {i} }}\right)}^{k}=1^{k}=1\,.$
Hence, the given complex numbers are indeed zeroes of the polynomial $X^{n}-1$. These zeroes are all different, because
    $e^{2\pi {\mathrm {i} }k/n}=e^{2\pi {\mathrm {i} }\ell /n}\,$
with $0\leq k\leq \ell \leq n-1$ implies, by considering the fraction, $e^{2\pi {\mathrm {i} }(\ell -k)/n}=1$ that
    $\ell -k=0\,$
holds. Therefore, there exist $n$ explicit zeroes and these are all the zeroes of the polynomial. The explicit description in coordinates follows from the Euler's formula.
$\Box$

## Definition

For a permutation $\pi$ on $\{1,\ldots ,n\}$, the $n\times n$-matrix
    $M_{\pi }={\left(a_{ij}\right)}\,,$
where
    $a_{\pi (j),j}=1\,$
and all other entries are $0$, is called a
We want to determine the characteristic polynomial of a permutation matrix. Here, we use that a permutation is a product of cycles. For a cycle of the form $1\mapsto 2\mapsto 3\mapsto \ldots \mapsto k\mapsto 1$, the corresponding permutation matrix is
    ${\begin{pmatrix}0&0&\ldots &0&1\\1&0&0&\ldots &0\\0&1&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&1&0\end{pmatrix}}.$
Every cycle can be brought (by renumbering) into this form.

## Lemma

The characteristic polynomial of a permutation matrix $M_{\rho }$ for a cycle $\rho \in S_{n}$ of
order $k$ is
    $\chi _{M}=(X-1)^{n-k}(X^{k}-1)\,.$

### Proof

We may assume that the cycle has the form $1\mapsto 2\mapsto 3\mapsto \ldots \mapsto k\mapsto 1$. The corresponding permutation matrix $M_{\rho }$ looks with respect to $e_{k+1},\ldots ,e_{n}$ like the identity matrix and has, with respect to the first $k$ standard vectors, the form
    ${\begin{pmatrix}0&0&\ldots &0&1\\1&0&0&\ldots &0\\0&1&0&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&1&0\end{pmatrix}}.$
The determinant of $XE_{n}-M_{\rho }$ is $(X-1)^{n-k}$ multiplied with the determinant of
    ${\begin{pmatrix}X&0&\ldots &0&-1\\-1&X&0&\ldots &0\\0&-1&X&\ldots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\ldots &0&-1&X\end{pmatrix}}.$
The expansion with respect to the first row yields
    $X^{k}+(-1)^{k+1}(-1)(-1)^{k-1}=X^{k}-1\,.$
$\Box$

## Lemma

For a permutation matrix $M_{\rho }$ over $\mathbb {C}$ for a cycle $\rho \in S_{n}$ with $\rho :1\mapsto 2\mapsto \ldots \mapsto k\mapsto 1$ and a $k$-th root of unity $\zeta$, the vectors
    $v_{\zeta }:=\zeta ^{k-1}e_{1}+\zeta ^{k-2}e_{2}+\cdots +\zeta e_{k-1}+e_{k}\,$
are eigenvectors of $M_{\rho }$ for the eigenvalue $\zeta$. In particular, a permutation matrix of a cycle over $\mathbb {C}$ is

### Proof

We have
    ${\begin{aligned}M_{\rho }(v_{\zeta })&=M_{\rho }(\zeta ^{k-1}e_{1}+\zeta ^{k-2}e_{2}+\cdots +\zeta e_{k-1}+e_{k})\\&=\zeta ^{k-1}M_{\rho }(e_{1})+\zeta ^{k-2}M_{\rho }(e_{2})+\cdots +\zeta M_{\rho }(e_{k-1})+M_{\rho }(e_{k})\\&=\zeta ^{k-1}e_{2}+\zeta ^{k-2}e_{3}+\cdots +\zeta e_{k}+e_{1}\\&=e_{1}+\zeta ^{k-1}e_{2}+\zeta ^{k-2}e_{3}+\cdots +\zeta e_{k}\\&=\zeta (\zeta ^{k-1}e_{1}+\zeta ^{k-2}e_{2}+\cdots +\zeta e_{k-1}+e_{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},\,i=1,\ldots ,k\rangle \,.$
Since the vectors $e_{i}$, $i\geq k+1$, are fixed vectors, the $v_{\zeta }$ together with the $e_{i}$, $i\geq k+1$, form a basis consisting of eigenvectors of $M_{\rho }$. Hence, $M_{\rho }$ is diagonalizable.
$\Box$

## Theorem

A permutation matrix over $\mathbb {C}$ is

### Proof

$\Box$