13.5 Eigenwerte der Adjazenzmatrix

Der Petersen-Graph ist der hier abgebildetete Graph. Er hat $10$ Ecken und an jeder Ecke gehen $3$ Kanten ab. Es ist klar, dass wir ihn als Teilgraph des vollständigen Graphen $K_{10}$ mit $10$ Ecken einbetten können. Da in $K_{10}$ an jeder Ecke $9$ Kanten abgehen, ist es denkbar, dass man den Graphen $K_{10}$ vollständig überdecken kann, indem man den Petersen-Graph auf drei verschiedene Weisen als Teilgraph einbettet (also so, dass insgesamt jede Kante von $K_{10}$ in einem der drei Teilgraphen vorkommt). Wir werden unten sehen, dass dies nicht möglich ist. Es ist aber klar, dass es eine sehr langwierige (und langweilige) Aufgabe wäre, das »per Hand« durch direktes Überprüfen aller Möglichkeiten zu beweisen. Stattdessen gibt es eine elegante Beweismethode mit linearer Algebra.

$\begin{tikzpicture} [line width=0.05pt, scale=1] \coordinate (A) at (0, 1); \coordinate (B) at (0.95106, 0.30902); \coordinate (C) at (-0.95106, 0.30902); \coordinate (D) at (-0.58779, -0.80902); \coordinate (E) at (0.58779, -0.80902); \draw [thick] (E) – (A); \draw [thick] (C) – (E); \draw [thick] (C) – (B) – (D) – (A); \node [fill, circle, inner sep=0.08cm] at (A) {}; \node [fill, circle, inner sep=0.08cm] at (B) {}; \node [fill, circle, inner sep=0.08cm] at (C) {}; \node [fill, circle, inner sep=0.08cm] at (D) {}; \node [fill, circle, inner sep=0.08cm] at (E) {}; \coordinate (F) at (0, 2); \coordinate (G) at (1.90212, 0.61804); \coordinate (H) at (-1.90212, 0.61804); \coordinate (I) at (-1.17558, -1.61804); \coordinate (J) at (1.17558, -1.61804); \node [fill, circle, inner sep=0.08cm] at (F) {}; \node [fill, circle, inner sep=0.08cm] at (G) {}; \node [fill, circle, inner sep=0.08cm] at (H) {}; \node [fill, circle, inner sep=0.08cm] at (I) {}; \node [fill, circle, inner sep=0.08cm] at (J) {}; \draw [thick] (F) – (G) – (J) – (I) – (H) – (F); \draw [thick] (A) – (F); \draw [thick] (B) – (G); \draw [thick] (C) – (H); \draw [thick] (D) – (I); \draw [thick] (E) – (J); \node [fill, circle, inner sep=0.08cm] at (A) {}; \node [fill, circle, inner sep=0.08cm] at (B) {}; \node [fill, circle, inner sep=0.08cm] at (C) {}; \node [fill, circle, inner sep=0.08cm] at (D) {}; \node [fill, circle, inner sep=0.08cm] at (E) {}; \end{tikzpicture}$

Zur Lösung dieses Problems untersuchen wir die Eigenwerte der Adjazenzmatrix.

Die Adjazenzmatrix $A$ von $K_{10}$ ist sehr einfach: Es ist die $(10\times 10)$-Matrix mit Nullen auf der Diagonalen und Einsen in allen anderen Feldern. Wir schreiben $J_{10}$ für die Matrix, deren Einträge sämtlich $=1$ sind. Dann gilt also $A = J_{10} - E_{10}$.

Wenn wir den Petersen-Graph als Teilgraph in $K_{10}$ einbetten, so ergibt sich eine Bijektion auf den Eckenmengen. Wir können die Situation also so beschreiben, dass wir die Ecken $\{ 1, \dots , 10\} $ von $K_{10}$ so mit Kanten verbinden, dass sich ein zum Petersen-Graph isomorpher Graph ergibt. Je nachdem, wie wir das machen, ergibt sich eine unterschiedliche Adjazenzmatrix (bezogen auf die Eckenmenge $\{ 1, \dots , 10\} $, die wir festhalten).

Angenommen, es gäbe drei Einbettungen des Petersen-Graphs als Teilgraphen von $K_{10}$, die insgesamt alle Kanten überdecken. Wegen der zahlenmäßigen Übereinstimmung wird dann jede Kante genau einmal getroffen. Sind $M_1$, $M_2$, $M_3$ die drei Adjazenzmatrizen dieser Teilgraphen, so gilt also

\[ A = M_1 + M_2 + M_3. \]

Außerdem sind die Matrizen $M_i$ alle zueinander und zur Adjazenzmatrix des Petersen-Graphen (bezüglich irgendeiner fixierten Eckennummerierung) konjugiert (Bemerkung 13.13). Das bedeutet, dass $M_1$, $M_2$ und $M_3$ dieselben Eigenwerte haben, und dass die zugehörigen Eigenräume dieselben Dimensionen haben, Lemma 10.7.

Lemma 13.14

Sei $M$ eine der drei Matrizen $M_1$, $M_2$, $M_3$. Dann gilt:

Der Eigenraum von $M$ zum Eigenwert $1$ hat Dimension $5$.
Der Eigenraum von $M$ zum Eigenwert $1$ ist enthalten in dem Untervektorraum

\[ U_0 := \{ (x_1,\dots , x_{10});\ \sum _{i=1}^{10} x_i = 0 \} \]

von $\mathbb Q^{10}$.

Beweis

zu (1). Berechne mit dem Gauß-Algorithmus die Dimension von $\operatorname{Ker}(M - E_{10})$. Wir lassen die einfache Rechnung hier aus.

zu (2). In jede Spalte von $M-E_{10}$ sind genau drei Einträge gleich $1$, genau einer gleich $-1$ (der Diagonaleintrag) und alle anderen gleich $0$. Die Summe aller Zeilen vom $M- E_{10}$ ist also $(2, \dots , 2)$. Das bedeutet, dass alle Lösungen $(x_1, \dots , x_{10})$ des linearen Gleichungssystems $(M-E_{10})x = 0$ auch die Gleichung

\[ 2x_1 + \cdots + 2x_{10} =0 \]

erfüllen, also in $U_0$ liegen.

Die Eigenräume zum Eigenwert $1$ von $M_1$ und $M_2$ liegen in dem $9$-dimensionalen Vektorraum $U_0$, müssen sich also nicht-trivial schneiden. Sei $x\ne 0$ ein Element des Durchschnitts. Es gilt dann $J_{10}x=0$, weil $x\in U_0$. Wir rechnen nun

\[ M_3 x = (A-M_1-M_2)x = (J_{10} - I_{10} - M_1 - M_2)x = -3x. \]

Den gewünschten Widerspruch erhält man nun, indem man (wieder mit dem Gauß-Algorithmus) überprüft, dass der Kern von $M_3 + 3 E_{10}$ trivial ist, also dass $-3$ kein Eigenwert der Adjazenzmatrix des Petersen-Graphen ist.

Quelle: [ Ma ] Kap. 13; Matoušek verweist auf eine Arbeit von Lossers und Schwenk. Für ein ähnliches aber etwas komplizierteres Problem siehe auch loc. cit. Kap. 14.

Lineare Algebra I, WS 2020/21

Inhalt

13.5 Eigenwerte der Adjazenzmatrix