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:

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A\le B} , wenn Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B-A\ge0} gilt.

Satz von Frobenius

Wenn von der Matrix lediglich Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A\geq0} 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:

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat A = \begin{pmatrix} B & 0\\ C & D \end{pmatrix} } ;

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} und Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A = \begin{Vmatrix} a_{ik} \end{Vmatrix}_1^n} besitzt stets eine positive charakteristische Wurzel Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} , die einfache Wurzel der charakteristischen Gleichung ist. Der Betrag aller anderen charakteristischen Wurzeln übertrifft diese Zahl Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} nicht. Der 'maximalen' charakteristischen Wurzel Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} entspricht ein Eigenvektor Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z} mit positiven Koordinaten.

Besitzt Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} insgesamt Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h} charakteristische Wurzeln Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_0 = r, \lambda_1,...,\lambda_{h-1}} vom Betrag Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} , so sind diese Zahlen alle voneinander verschieden und sind Wurzeln der Gleichung

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda^h - r^h = 0} ;

betrachtet man alle charakteristischen Wurzeln Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_0, \lambda_1,...,\lambda_{h-1}} der Matrix Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A = \begin{Vmatrix} a_{ik} \end{Vmatrix}_1^n} als Punkte in der komplexen Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda} -Ebene, so geht das System dieser Wurzeln bei Drehung der Ebene um den Ursprung mit dem Winkel Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac {2\pi} {h}} in sich über. Für Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle h > 1} kann die Matrix Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} durch eine Permutation der Reihen in die 'zyklische' Form

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\lambda|=\varrho(A) = r} existieren können. Falls allerdings Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} primitiv ist, das heißt, dass eine Potenz Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A^m} für ein Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m\in\N} positiv ist, dann gibt es nur einen Eigenwert Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda} von Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} mit Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |\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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A = \begin{Vmatrix} a_{ik} \end{Vmatrix}_1^n} besitzt stets eine reelle und überdies positive charakteristische Wurzel Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} , die einfache Wurzel der charakteristischen Gleichung ist und den Betrag aller anderen charakteristischen Wurzeln übertrifft. Zu einer 'maximalen' charakteristischen Wurzel Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} gibt es einen Eigenvektor Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z = (z_1, z_2,..., z_n)} der Matrix Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} mit positiven Koordinaten Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} folgt, gibt es in diesem Fall keine imaginären charakteristischen Wurzeln vom Betrag Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} .

Für positive Matrizen Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A>0} sagt der Satz aus, dass der Spektralradius Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varrho(A)} von Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} gleichzeitig ein positiver, einfacher Eigenwert von Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} ist,

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_1=\varrho(A)>0,}

zu dem ein ebenfalls positiver Eigenvektor Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z>0} existiert, Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Az=\varrho(A)z.} Außerdem ist Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_1} größer als die Beträge aller anderen Eigenwerte der Matrix,

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda_1>|\lambda_j|,\ j=2,\ldots,n.}

Weiterhin ist der Spektralradius eine monotone Abbildung von positiven Matrizen,

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0<A<B\ \Rightarrow\ 0<\varrho(A)<\varrho(B).}

Allgemeiner gilt der Satz auch für primitive Matrizen.

Beispiel

Man betrachte die nichtnegativen Matrizen

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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