Irreduzible Matrix

Eine dünnbesetzte Matrix ${\displaystyle A}$ heißt zerlegbar (reduzibel), wenn eine Permutationsmatrix ${\displaystyle P}$ existiert, so dass sie durch das Matrixprodukt ${\displaystyle PAP^{T}}$ in eine (hier obere) Blockdreiecksmatrix überführt werden kann,

${\displaystyle PAP^{T}={\begin{bmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\cdots &\mathbf {A} _{1n}\\0&\mathbf {A} _{22}&\cdots &\mathbf {A} _{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{nn}\end{bmatrix}},}$

mit Untermatrizen ${\displaystyle \mathbf {A} _{ij}}$.[4]

Ist diese Umordnung nicht möglich, so heißt die Matrix unzerlegbar (irreduzibel). Das gilt auch analog für eine Umordnung in eine untere Blockdreiecksmatrix. Eine obere Blockdreiecksmatrix kann durch Spiegelung an der Hauptdiagonalen (und damit durch eine Permutationsumordnung) in eine untere Blockdreiecksmatrix überführt werden. Deshalb können beide Definitionstypen gleichberechtigt zur Bestimmung dieser Eigenschaft einer Matrix verwendet werden.

Diese Definition der Zerlegbarkeit kann man vereinfachen, indem man unter den Permutationsergebnissen eine einzelne quadratische Untermatrix ${\displaystyle \mathbf {A} _{11}}$sucht, unter der (in allen Spalten) nur Nullen stehen:

${\displaystyle PAP^{T}={\begin{bmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}\\0&\mathbf {A} _{22}\\\end{bmatrix}}.}$

Dann hat man die Eigenschaft der Matrix, zerlegbar (reduzibel) zu sein, bereits gefunden.[5]

Sind alle Einträge der Matrix ${\displaystyle A}$ nichtnegativ und ist die Hauptdiagonale echt positiv, dann ist die Irreduzibilität von ${\displaystyle A}$ äquivalent dazu, dass eine Zahl ${\displaystyle k\in \mathbb {N} }$ existiert, für die

${\displaystyle A^{k}>0}$

gilt, das heißt, dass alle Einträge der Matrixpotenz ${\displaystyle A^{k}}$ positiv sind.[6] Etwas schwächer ist die Aussage, dass eine Matrix ${\displaystyle A}$ irreduzibel ist, wenn ${\displaystyle A\geq 0}$ gilt und ein ${\displaystyle k\in \mathbb {N} }$ existiert, sodass ${\displaystyle A^{k}>0}$ ist.

Eine Matrix ${\displaystyle A}$ mit nichtnegativen Einträgen ist genau dann irreduzibel, wenn es zu jedem Indexpaar ${\displaystyle (i,j)}$ eine Zahl ${\displaystyle k\in \mathbb {N} }$ gibt, so dass der ${\displaystyle (i,j)}$-Eintrag von ${\displaystyle A^{k}}$ positiv ist.

Irreduzible Matrizen spielen eine Rolle für die Existenz von Eigenvektoren und die Dimension des dazugehörigen Eigenraums, siehe dazu Satz von Perron-Frobenius. Des Weiteren gibt es eine enge Verbindung zur Graphentheorie: Die Adjazenzmatrix eines gerichteten Graphen ist genau dann irreduzibel, wenn der Graph stark zusammenhängend ist. Des Weiteren gilt: ist ${\displaystyle A}$ irreduzibel, so ist auch ${\displaystyle A^{T}}$ irreduzibel. Außerdem ist die Irreduzibilität einer stochastischen Matrix äquivalent zur Irreduzibilität der Markow-Kette, welche durch die stochastische Matrix beschrieben wird.

Der Adjazenzgraph der Matrix ${\displaystyle A}$

Die folgende Matrix

${\displaystyle A=\left[{\begin{array}{rr|rr}0&3&0&0\\2&0&4&0\\\hline 0&0&0&1\\0&0&2&0\end{array}}\right]}$

ist eine obere Blockdreiecksmatrix und somit zerlegbar (reduzibel). Das kann man ohne weitere Hilfsmittel wie Graphen sofort erkennen. Die Grafik zeigt trotzdem einen gerichteten Graph, und zwar den Adjazenzgraph der Matrix ${\displaystyle A}$. Anhand der Grafik kann man erlernen, wie man vorgehen muss, wenn die Zerlegbarkeit einer gegebenen Matrix nicht so offensichtlich ist wie in diesem Beispiel. Wie der Grafik zu entnehmen, existiert kein gerichteter Pfad von Knoten 3 zu Knoten 2. In der Graphentheorie sagt man dazu, der Graph sei nicht stark zusammenhängend. Deshalb ist der Graph (und damit die Matrix) reduzibel (zerlegbar).

• Richard S. Varga: Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ 1962 (XIII, 322).
• Feliks R. Gantmacher: Matrizentheorie. VEB Deutscher Verlag der Wissenschaften, Berlin 1986, ISBN 3-326-00001-4 (654 S.).
• Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer Spektrum, Berlin u. a. 2013, ISBN 978-3-642-32185-6.

• Eric W. Weisstein: Reducible Matrix. In: MathWorld (englisch).

1. Georg Frobenius: Über Matrizen aus nicht negativen Elementen. In: Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin: Jahrgang 1912. Erster Halbband. Januar bis Juni. Verlag der Königlichen Akademie der Wissenschaften. In Commission bei Georg Reimer, Berlin 1912, S. 456–477 (Originalartikel [PDF]).
2. Richard S. Varga, 1962, S. 19
3. Feliks R. Gantmacher, 1986, S. 395
4. Rudolf Kochendörffer: Determinanten und Matrizen. 2. Auflage. B. G. Teubner, Leipzig 1961, S. 109 (VI, 144 S.).
5. Richard S. Varga, 1962, S. 18
6. Peter Knabner, Wolf Barth, 2013, S. 842