# Graph/Adjazenzmatrix/Charakteristisches Polynom/Eigenräume/Textabschnitt
## Definition

Zu einem Graphen nennt man das charakteristische Polynom der Adjazenzmatrix das charakteristische Polynom von $G$.
Entsprechende nennt man die Eigenwerte (Eigenvektoren, Eigenräume u.s.w.) der Adjazenzmatrix auch die Eigenwerte des Graphen.

## Beispiel

Das charakteristische Polynom zur Adjazenzmatrix des vollständigen Graphen $K_{n}$ ist nach Definition die Determinante von
    ${\begin{pmatrix}x&-1&\ldots &-1&-1\\-1&x&-1&\ldots &-1\\\vdots &\ddots &\ddots &\ddots &\vdots \\-1&\ldots &-1&x&-1\\-1&-1&\ldots &-1&x\end{pmatrix}}.$
In diesem Fall ist es einfacher, direkt die Eigenräume zu berechnen. Für $x=-1$ steht hier überall $-1$ und der Kern besitzt die Basis
    ${\begin{pmatrix}1\\-1\\0\\\vdots \\0\\0\end{pmatrix}},\,{\begin{pmatrix}0\\1\\-1\\\vdots \\0\\0\end{pmatrix}},\ldots ,{\begin{pmatrix}0\\0\\0\\\vdots \\1\\-1\end{pmatrix}}.$
Somit ist $-1$ ein Eigenwert mit geometrischer Vielfachheit $n-1$. Für $x=n-1$ ergibt sich die Matrix
    ${\begin{pmatrix}n-1&-1&\ldots &-1&-1\\-1&n-1&-1&\ldots &-1\\\vdots &\ddots &\ddots &\ddots &\vdots \\-1&\ldots &-1&n-1&-1\\-1&-1&\ldots &-1&n-1\end{pmatrix}}$
und der Kern davon ist
    $\mathbb {R} {\begin{pmatrix}1\\1\\\vdots \\1\\1\end{pmatrix}}.$
Somit ist $n-1$ ein Eigenwert mit geometrischer Vielfachheit $1$. Da die Summe der geometrischen Vielfachheiten bereits die Dimension $n$ ist, handelt es sich jeweils auch um die algebraischen Vielfachheiten und das charakteristische Polynom ist
    $(x+1)^{n-1}(x-n+1).$

## Bemerkung

Für einen Graphen liegt folgende Interpretation nahe: Ein Knotenpunkt ist der mögliche Aufenthaltsort eines Gerüchtes, einer Information, eines Virus. Wenn eine Kante zwischen zwei Punkten $u$ und $v$ besteht, so bedeutet dies, dass in einem bestimmten Zeitabschnitt das Gerücht von $u$ nach $v$ hinüber- oder zurückwechselt. Die Gesamtverteilung des Gerüchtes ist ein Spaltenvektor
    ${\left(c_{v}\right)}_{v\in V}$
der für jeden Punkt angibt, wie stark im Ort $v$ das Gerücht verbreitet ist. Der Gesamtübergang in dem erwähnten Zeitintervall wird dann durch Multiplikation der Adjazenzmatrix $A$ mit der Gesamtverteilung beschrieben. Wenn beispielsweise zu Beginn das Gerücht nur in einem Knotenpunkt $u$ mit der Stärke $1$ präsent ist, so ist es nach dem Zeitintervall in den zu $u$ benachbarten Knoten jeweils mit der Stärke $1$ präsent, und dies ist gerade der $u$-te Spaltenvektor der Adjazenzmatrix (da wir ohne Schleifen arbeiten, vergisst man in diesem Modell das Gerücht, indem man es weitererzählt, es liegt eine gedächtnislose Weitergabe vor; man kann die Weitergabe auch abschwächen, wenn man die Adjazenzmatrix mit einem Faktor skaliert). Die Gerüchtverteilung nach $\ell$ Durchläufen zur Anfangsgerüchtverteilung wird dann durch $A^{\ell }(c_{v})$ beschrieben. Eine Eigenverteilung, also ein Eigenvektor der Adjazenzmatrix, ist durch die Eigenschaft gekennzeichnet, dass sich bei einem Durchlauf ein bestimmtes Vielfaches dieser Verteilung selbst ergibt. Der gemeinsame Faktor, der an jeder Stelle den Übergang beschreibt, ist der Eigenwert.
Im vollständigen Graphen gibt es nach Beispiel die beiden Eigenwerte $n-1$ und $-1$. Die Gerüchtverteilung ${\begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}}$
(an jeder Stelle wird mit der gleichen Intensität $1$ das Gerücht geglaubt) wird durch einen Weitergabevorgang in die Gerüchtverteilung ${\begin{pmatrix}n-1\\n-1\\\vdots \\n-1\end{pmatrix}}$ überführt, jeder hört das Gerücht $n-1$ mal. Die Gerüchtverteilung ${\begin{pmatrix}1\\-1\\0\\\vdots \\0\end{pmatrix}}$, wobei $-1$ so zu verstehen ist, dass das Gerücht an dieser Stelle mit der gleichen Intensität nicht geglaubt wird, wird durch den Vorgang in die Verteilung ${\begin{pmatrix}-1\\1\\0\\\vdots \\0\end{pmatrix}}$ überführt. Die beiden nichtneutralen Personen übernehmen wechselseitig ihre Einstellung zum Gerücht und alle anderen Personen hören es einmal in positiver und einmal in negativer Weise, was sich aufhebt.