Satz von Perron-Frobenius

Der Satz von Perron-Frobenius befasst sich mit der Existenz eines positiven Eigenvektors zu einem positiven, betragsgrößten Eigenwert von nichtnegativen Matrizen. Die Aussagen haben eine wichtige Bedeutung zum Beispiel für die Potenzmethode und Markow-Ketten.

Der Satz wurde zunächst von Oskar Perron für den einfacheren Fall positiver Matrizen gezeigt und dann von Ferdinand Georg Frobenius für nicht-negative Matrizen verallgemeinert.

Die Begriffe positiv und nicht-negativ sind dabei elementweise zu verstehen:

$A={\begin{pmatrix}a_{11}&\ldots &a_{1n}\\\vdots &&\vdots \\a_{n1}&\ldots &a_{nn}\end{pmatrix}}>0\iff a_{ij}>0,\ i,j=1,\ldots ,n.$

Dadurch wird auch eine Halbordnung unter Matrizen eingeführt, man schreibt $A\leq B$, wenn $B-A\geq 0$ gilt.

Satz von Frobenius

Wenn von der Matrix lediglich $A\geq 0$ gefordert ist (einige Elemente können auch null sein), muss unterschieden werden, ob die Matrix zerlegbar ist oder nicht. Eine quadratische Matrix heißt zerlegbar (reduzibel), wenn sie durch gleichzeitige Permutation von Zeilen und Spalten in folgende Form überführt werden kann:

${\hat {A}}={\begin{pmatrix}B&0\\C&D\end{pmatrix}}$;

$B$ und $D$ sind quadratische Matrizen. Wenn das nicht möglich ist, heißt die Matrix unzerlegbar (irreduzibel).

Der Satz von Frobenius lautet:

"Eine unzerlegbare nichtnegative Matrix $A={\begin{Vmatrix}a_{ik}\end{Vmatrix}}_{1}^{n}$ besitzt stets eine positive charakteristische Wurzel $r$, die einfache Wurzel der charakteristischen Gleichung ist. Der Betrag aller anderen charakteristischen Wurzeln übertrifft diese Zahl $r$ nicht. Der 'maximalen' charakteristischen Wurzel $r$ entspricht ein Eigenvektor $z$ mit positiven Koordinaten.

Besitzt $A$ insgesamt $h$ charakteristische Wurzeln $\lambda _{0}=r,\lambda _{1},...,\lambda _{h-1}$ vom Betrag $r$, so sind diese Zahlen alle voneinander verschieden und sind Wurzeln der Gleichung

$\lambda ^{h}-r^{h}=0$;

betrachtet man alle charakteristischen Wurzeln $\lambda _{0},\lambda _{1},...,\lambda _{h-1}$ der Matrix $A={\begin{Vmatrix}a_{ik}\end{Vmatrix}}_{1}^{n}$ als Punkte in der komplexen $\lambda$-Ebene, so geht das System dieser Wurzeln bei Drehung der Ebene um den Ursprung mit dem Winkel ${\frac {2\pi }{h}}$ in sich über. Für $h>1$ kann die Matrix $A$ durch eine Permutation der Reihen in die 'zyklische' Form

$A={\begin{pmatrix}0&A_{12}&0&...&0\\0&0&A_{23}&...&0\\.&.&.&...&.\\0&0&0&...&A_{h-1,h}\\A_{h1}&0&0&...&0\\\end{pmatrix}}$

übergeführt werden, wobei sämtliche Diagonalelemente quadratisch sind."

Wie ersichtlich schließt dieser Satz nicht aus, dass verschiedene Eigenwerte mit dem Betrag $|\lambda |=\varrho (A)=r$ existieren können. Falls allerdings $A$ primitiv ist, das heißt, dass eine Potenz $A^{m}$ für ein $m\in \mathbb {N}$ positiv ist, dann gibt es nur einen Eigenwert $\lambda$ von $A$ mit $|\lambda |=\varrho (A)$.

Für beliebige nichtnegative Matrizen muss der Satz von Frobenius dahingehend abgeschwächt werden, dass die „maximale“ charakteristische Wurzel und der dazugehörige Eigenvektor nichtnegativ sind.

Satz von Perron

„Eine positive Matrix $A={\begin{Vmatrix}a_{ik}\end{Vmatrix}}_{1}^{n}$ besitzt stets eine reelle und überdies positive charakteristische Wurzel $r$, die einfache Wurzel der charakteristischen Gleichung ist und den Betrag aller anderen charakteristischen Wurzeln übertrifft. Zu einer 'maximalen' charakteristischen Wurzel $r$ gibt es einen Eigenvektor $z=(z_{1},z_{2},...,z_{n})$ der Matrix $A$ mit positiven Koordinaten $z_{i}>0\quad (i=1,2,...,n)$.“

Der Satz von Perron folgt logisch aus dem Satz von Frobenius. Das sieht man an folgender einfachen Betrachtung: Sind alle Elemente einer Matrix positiv, so ist die oben angegebene zirkuläre Struktur nicht möglich. Da diese aber zwangsläufig aus der Existenz mehrerer Wurzeln mit dem Betrag $r$ folgt, gibt es in diesem Fall keine imaginären charakteristischen Wurzeln vom Betrag $r$.

Für positive Matrizen $A>0$ sagt der Satz aus, dass der Spektralradius $\varrho (A)$ von $A$ gleichzeitig ein positiver, einfacher Eigenwert von $A$ ist,

$\lambda _{1}=\varrho (A)>0,$

zu dem ein ebenfalls positiver Eigenvektor $z>0$ existiert, $Az=\varrho (A)z.$ Außerdem ist $\lambda _{1}$ größer als die Beträge aller anderen Eigenwerte der Matrix,

$\lambda _{1}>|\lambda _{j}|,\ j=2,\ldots ,n.$

Weiterhin ist der Spektralradius eine monotone Abbildung von positiven Matrizen,

$0<A<B\ \Rightarrow \ 0<\varrho (A)<\varrho (B).$

Allgemeiner gilt der Satz auch für primitive Matrizen.

Beispiel

Man betrachte die nichtnegativen Matrizen

$A={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}},\ B={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}},\ C={\begin{pmatrix}0&3&0\\0&2&1\\1&0&2\end{pmatrix}}.$

Die Matrix $A$ hat den doppelten Eigenwert $1=\varrho (A)$, da sie reduzibel ist, und den Eigenwert $-1$, da der Block $A_{MM}$ zyklisch ist. Auch bei der Matrix $B$ ist $\varrho (B)=1$ ein Eigenwert, es gibt aber noch zwei weitere komplexe Eigenwerte mit gleichem Betrag, da auch $B$ zyklisch ist. Erst bei $C$ ist $\lambda _{1}=3=\varrho (C)$ größer als der Betrag eins der anderen Eigenwerte ${\frac {1}{2}}(1\pm i{\sqrt {3}})$, und zum größten Eigenwert 3 gehört der positive Eigenvektor $(1,1,1)^{T}$.

Anwendungen

Die Bedeutung der Sätze beruht darauf, dass man die wesentlichen Voraussetzungen Positivität bzw. Nichtnegativität direkt prüfen kann und ihre Aussagen wichtig sind für die Konvergenz der Potenzmethode und die Konvergenz gegen die stationäre Verteilung bei Markow-Ketten.

Für die Konvergenz ist dabei insbesondere die Trennung der Eigenwert-Beträge $\varrho (A)>|\lambda |$ für $\lambda \not =\varrho (A)$ wichtig, welche nur bei primitiven (und somit insbesondere bei positiven) Matrizen uneingeschränkt gilt. Deshalb wird im PageRank-Algorithmus von Google mit dem Dämpfungsfaktor $d>0$ statt der reinen Link-Matrix $T\geq 0$ eine positive Matrix benutzt.

Der Satz von Frobenius stellt die mathematische Grundlage für das volkswirtschaftliche Modell dar, das von Piero Sraffa entwickelt worden ist.

Literatur

• Bertram Huppert: Angewandte Lineare Algebra, Walter de Gruyter (1990). ISBN 3-11-012107-7.
• O. Perron: Zur Theorie der Matrices, Math. Ann. 64, 248–263 (1907).
• G. Frobenius: Über Matrizen aus nicht negativen Elementen, Berl. Ber. 1912, 456–477.
• Thomas W. Hawkins: Continued fractions and the origins of the Perron-Frobenius theorem, Archive History Exact Sciences, 62, 2008, 655–717