Perron-Frobenius Satz

Beschreibung

Der Perron-Frobebius Satz gibt eine Menge Informationen über die Struktur von nicht-negativen quadratischen Matrizen

Aperiodischer Perron-Frobenius

Sei $A$ eine nicht-negative Quadratische Matrix. Ist $A$ irreduzibel und aperiodisch, existiert ein reeller Eigenwert $\lambda >0$ sodass:

• $\lambda$ hat die Algebraische Vielfachheit $1$
• $\lambda$ hat streng positive linke und rechte Eigenvektoren.
• $\lambda$ ist der echt größte Eigenvektor, d.h. $|\mu |<\lambda$ für andere Eigenwerte $\mu$
• Wenn $0\le B\le A$ (eintragsweise) dann gilt $|\beta |\le \lambda$ für alle Eigenwerte $\beta$ von $B$
• ${\lim }_{n\to \infty }\frac{A^n}{{\lambda }^n}=rl$, wobei $l$ und $r$ die linken und rechten Eigenvektoren für $A$ sind, normalisiert, sodass $l\cdot r=1$.

Beweis: Der wichtigste Teil des Beweises ist, dass es eine Eigengerade durch den positiven Quadranten gibt und dass jeder nicht-negative Vektor sich diesem durch Iteration annähert. Am einfachsten funktioniert das über den Banachscher Fixpunktsatz. Betrachte das Einheitssimplex von ${\mathbb{R}}^n$. Da $A$ aperiodisch ist, existiert ein $l$, sodass alle Einträge von $A^l$ streng positiv sind. Die Abbildung $\alpha (x)=\frac{A^{l}x}{|A^{l}x|}$ mit der Manhattan-Metrik bildet das Einheitssimplex auf sich selbst ab. Da alle Basisvektoren des ${\mathbb{R}}^n$ auf streng positive Vektoren abgebildet werden, liegt das Bild von $\alpha$ im Inneren des Simplex. Aufgrund der Linearität bedeutet das, dass eine Iteration das Simplex immer weiter schrumpft. Nach dem Fixpunktsatz existiert damit ein Fixpunkt, welcher der gesuchte Eigenvektor ist.

Allgemeiner Perron-Frobenius Satz

Sei $A$ eine nicht-negative, quadratische Matrix. Ist $A$ irreduzibel, existiert ein reeller Eigenwert $\lambda >0$ sodass:

• $\lambda$ hat die Algebraische Vielfachheit $1$
• $\lambda$ hat streng positive linke und rechte Eigenvektoren.
• $\lambda$ ist der größte Eigenvektor, d.h. $|\mu |\ge \lambda$ für andere Eigenwerte $\mu$
• Wenn $0\le B\le A$ (eintragsweise) dann gilt $|\beta |\le \lambda$ für alle Eigenwerte $\beta$ von $B$

Der Eigenwert $\lambda$ wird dann als Perron-Wert bezeichnet. Der dazugehörige Eigenvektor als Perron-Vektor.

Des Weiteren, sollte $\lambda$ doch $1$ sein, so ist $M$ eine Permutationsmatrix.

Beweis: Sei $A$ irreduzibel. Dann besitzt $A$ graphentheoretisch eine wohldefinierte Periode $p$. Die Matrix $A^p$ beschreibt alle Verbindungen, die mit $p$ langen Pfaden zwischen zwei Knoten gemacht werden können. Mit einer Permutation können wir daher o.E. die Spalten und Reihen so umordnen, dass eine Blockdiagonalmatrix entsteht. Die Blöcke sind hierbei die jeweiligen zyklischen Untermengen. Da $A^p$ eine in Blockdiagonalform ist, lassen sich die einzelnen Blöcke unabhängig voneinander untersuchen. Des Weiteren sind die Blöcke irreduzibel und aperiodisch. Damit lässt sich der aperiodische Perron-Frobenius anwenden. Jeder einzelne Block trifft somit eine Aussage über seinen jeweiligen Perron-Wert. Ehrlich gesagt habe ich aber keine Ahnung, wie diese Information über $A^p$ und für den Beweis von Perron-Frobenius helfen könnte.

Eigenwerte Irreduzibler Matrizen

Sei $A$ eine nicht-negative, quadratische, irreduzible Matrix mit Periode $p$ und Perron-Wert $\lambda$. Dann hat $A$ genau $p$ komplexe Eigenwerte mit Betrag $\lambda$. Jeder ist eine Wurzel von $x^p-{\lambda }^p=0$.

Ist $\mu$ ein anderer Eigenwert von $A$, so ist $\mu \exp (i2\pi k/p)$ auch ein Eigenvektor.

Iteratives Verhalten

Sei $A$ eine nicht-negative, irreduzible Matrix mit Periode $p$ und Perron-Wert $\lambda$. Seien $C_0,...,C_{p-1}$ Zyklische Untermenge (Matrix) der Indizes. Dann gilt für $j,j\in C_k$ ${\lim }_{n\to \infty }(A^{np}/{\lambda }^{np}{)}_{ij}=r_i{l}_j$ wobei $l,r$ so normalisiert sind, dass $lr=p$.

Eigenschaften

Eigenschaft

lit_kitchensSymbolicDynamicsOnesided2012