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 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\le B$, wenn $B-A\ge0$ gilt.

Positive Matrizen

Für positive Matrizen A > 0 (d.h. A = (a_ij) mit a_ij > 0 $\forall$ 1 ≤ i, j ≤ n) 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 x > 0 existiert, $Ax=\varrho(A)x.$ Außerdem ist λ₁ 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 Funktion von positiven Matrizen,

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

Nichtnegative Matrizen

Wenn nur noch $A\ge0$ gilt, ist die Situation komplizierter, der Satz gilt dann nur, wenn einige Sonderfälle ausgeschlossen werden. Dazu benötigt man folgende Begriffe, die einen Bezug zur Graphentheorie besitzen. Eine Matrix heißt zerlegbar (reduzibel), wenn eine Aufteilung der Indizes $\{1,\ldots,n\}=M\cup N$ existiert, so dass die umgeordnete Matrix Block-Dreieckform besitzt

$\begin{pmatrix}A_{MM}& A_{MN}\\ 0&A_{NN}\end{pmatrix}.$

Dabei meint A_MN die Untermatrix mit Zeilenindizes aus M und Spaltenindizes aus N. Wenn diese Anordnung unmöglich ist, heißt die Matrix unzerlegbar (irreduzibel). Damit gilt:

Für eine unzerlegbare, nichtnegative Matrix $A\ge0$ ist der Spektralradius $\varrho(A)$ ein positiver, einfacher Eigenwert der Matrix und es gibt dazu einen positiven Eigenvektor x > 0 mit $Ax=\varrho(A)x.$ Der Spektralradius hängt monoton von A ab,

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

Allerdings schließt dieser Satz nicht aus, dass verschiedene Eigenwerte mit dem Betrag $|\lambda|=\varrho(A)$ existieren können.

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 zerlegbar ist mit $M=\{1,2\},\ N=\{3\}$ 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 $\frac12(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 den Grenzzustand 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 positiven Matrizen uneingeschränkt gilt. Deshalb wird im PageRank-Algorithmus von Google mit dem Dämpfungsfaktor d > 0 statt der reinen Link-Matrix $T\ge0$ eine positive Matrix benutzt.

Literatur

• B. 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.