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

in ${}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.$

In ${}\mathbb {C} [X]$, we have the factorization

${}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

permutation matrix.

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 :i_{1}\mapsto i_{2}\mapsto \ldots \mapsto i_{k}\mapsto i_{1}$ and a ${}k$-th root of unity ${}\zeta$, the vectors

${}v_{\zeta }:=\zeta ^{k-1}e_{i_{1}}+\zeta ^{k-2}e_{i_{2}}+\cdots +\zeta e_{i_{k-1}}+e_{i_{k}}\,$

are eigenvectors of ${}M_{\rho }$ for the eigenvalue ${}\zeta$. In particular, a permutation matrix of a cycle over ${}\mathbb {C}$ is

diagonalizable.

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.

$\Box$

Theorem

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

diagonalizable.

Proof

See exercise.

$\Box$