Endomorphismen/Endliche Ordnung/Permutationsmatrizen/Eigentheorie/Textabschnitt

Wir betrachten lineare Abbildungen

$\varphi \colon V\longrightarrow V$

mit der Eigenschaft, dass eine Potenz davon die Identität ist, sagen wir

${}\varphi ^{k}=\operatorname {Id} _{V}\,,$

dass ${}\varphi$ also endliche Ordnung besitzt. Typische Beispiele sind Drehungen um einen Winkel der Form ${}{\frac {360}{k}}$ oder Permutationsmatrizen. Das Polynom ${}X^{k}-1$ annulliert dann diesen Endomorphismus und ist daher ein Vielfaches des Minimalpolynoms.

Definition

Es sei ${}K$ ein Körper und ${}n\in \mathbb {N}$. Dann heißen die Nullstellen des Polynoms

$X^{n}-1$

in ${}K$ die ${}n$-ten Einheitswurzeln in ${}K$.

Lemma

Es sei ${}n\in \mathbb {N} _{+}$.

Die Nullstellen des Polynoms ${}X^{n}-1$ über ${}{\mathbb {C} }$ sind

$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]$ gilt die Faktorisierung

${}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)}\,.$

Beweis

Der Beweis verwendet einige Grundtatsachen über die komplexe Exponentialfunktion. Es ist

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

Die angegebenen komplexen Zahlen sind also wirklich Nullstellen des Polynoms ${}X^{n}-1$. Diese Nullstellen sind alle untereinander verschieden, da aus

${}e^{2\pi {\mathrm {i} }k/n}=e^{2\pi {\mathrm {i} }\ell /n}\,$

mit ${}0\leq k\leq \ell \leq n-1$ sofort, durch Betrachten des Quotienten, ${}e^{2\pi {\mathrm {i} }(\ell -k)/n}=1$ folgt, und daraus

${}\ell -k=0\,.$

Es gibt also ${}n$ explizit angegebene Nullstellen und daher müssen dies alle Nullstellen des Polynoms sein. Die explizite Beschreibung in Koordinaten folgt aus der eulerschen Formel.

$\Box$

Definition

Zu einer Permutation ${}\pi$ auf ${}{\{1,\ldots ,n\}}$ nennt man die ${}n\times n$-Matrix

${}M_{\pi }={\left(a_{ij}\right)}\,,$

für die

${}a_{\pi (j),j}=1\,$

ist und sonst alle Einträge ${}0$ sind, eine Permutationsmatrix.

Wir wollen das charakteristische Polynom zu einer Permutationsmatrix bestimmen. Dabei verwenden wir, dass eine Permutation ein Produkt von Zykeln ist. Zu einem Zykel der Form ${}1\mapsto 2\mapsto 3\mapsto \ldots \mapsto k\mapsto 1$ gehört die Permutationsmatrix

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

Jeder Zykel kann (durch Umnummerierung) auf diese Gestalt gebracht werden.

Lemma

Das charakteristische Polynom einer Permutationsmatrix ${}M_{\rho }$ zu einem Zykel ${}\rho \in S_{n}$ der Ordnung ${}k$ ist

${}\chi _{M}=(X-1)^{n-k}(X^{k}-1)\,.$

Beweis

Wir können von einem Zykel der Form ${}1\mapsto 2\mapsto 3\mapsto \ldots \mapsto k\mapsto 1$ ausgehen. Die zugehörige Permutationsmatrix ${}M_{\rho }$ ist bezüglich ${}e_{k+1},\ldots ,e_{n}$ die Einheitsmatrix und hat bezüglich der ersten ${}k$ Standardvektoren die Gestalt

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

Die Determinante zu ${}XE_{n}-M_{\rho }$ ist ${}(X-1)^{n-k}$ multipliziert mit der Determinante von

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

Die Entwicklung nach der ersten Zeile liefert

${}X^{k}+(-1)^{k+1}(-1)(-1)^{k-1}=X^{k}-1\,.$

$\Box$

Lemma

Zu einer Permutationsmatrix ${}M_{\rho }$ über ${}{\mathbb {C} }$ zu einem Zykel ${}\rho \in S_{n}$ mit ${}\rho :i_{1}\mapsto i_{2}\mapsto \ldots \mapsto i_{k}\mapsto i_{1}$

und einer ${}k$-ten Einheitswurzel ${}\zeta$ sind die Vektoren

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

Eigenvektoren von ${}M_{\rho }$ zum Eigenwert ${}\zeta$.

Insbesondere ist eine Permutationsmatrix zu einem Zykel über ${}{\mathbb {C} }$ diagonalisierbar.

Beweis

Es ist

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

Da es ${}k$ verschiedene ${}k$-te Einheitswurzeln in ${}{\mathbb {C} }$ gibt, sind diese Vektoren nach Fakt linear unabhängig und erzeugen einen ${}k$-dimensionalen Untervektorraum ${}U$ von ${}K^{n}$, und zwar gilt

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

Da die Vektoren ${}e_{i}$, ${}i\neq {i_{j}}$, Fixvektoren sind, bilden die ${}v_{\zeta }$ zusammen mit den ${}e_{i}$, ${}i\neq {i_{j}}$, eine Basis aus Eigenvektoren von ${}M_{\rho }$ und daher ist ${}M_{\rho }$ diagonalisierbar.

$\Box$

Satz

Eine Permutationsmatrix

ist über ${}{\mathbb {C} }$ diagonalisierbar.

Beweis

Siehe Aufgabe.

$\Box$