Irreduzible Matrix

Irreduzibilität von Matrizen ist ein Konzept der linearen Algebra, welches enge Verbindungen zur Graphentheorie aufweist. Vereinfacht gesagt ist eine Matrix irreduzibel, wenn ihre Zeilen und Spalten nicht so permutiert werden können, dass die Matrix in die untere Blockdreiecksgestalt überführt wird.

Neben Anwendungen in der Graphentheorie, findet das Konzept der Irreduzibilität Anwendung in der Theorie der positiven Eigenwerte und -vektoren, siehe etwa Satz von Perron-Frobenius.

Definition

Eine Matrix $A \in \mathbb{R}^{n \times n}$ heißt reduzibel, wenn eine Permutationsmatrix existiert, so dass

$PAP^T= \begin{pmatrix} A_{MM}& 0\\ A_{NM}&A_{NN} \end{pmatrix}.$

Dabei ist $A_{MM}$ aus $\mathbb{R}^{p \times p}$ mit $p \in \{1, \ldots, n-1\}$ und die anderen Blockmatrizen dementsprechend passend dimensioniert. Ist diese Umordnung nicht möglich, so heißt die Matrix irreduzibel.

Potenz und Irreduzibilität

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

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

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

Verwendung

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 irreduzibel, so ist auch $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.

Beispiel

Der Adjazenzgraph der Matrix . Es existiert kein Pfad von Knoten 3 zu Knoten 2, der Graph ist also nicht stark zusammenhängend.

Betrachte als Beispiel die folgende Matrix:

$A = \begin{bmatrix} 0 & 3 & 0 & 0 \\ 2 & 0 & 4 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 2 & 0 \\ \end{bmatrix}$

Die transponierte Matrix ist

$A^T = \begin{bmatrix} 0 & 2 & 0 & 0 \\ 3 & 0 & 0 & 0 \\ 0 & 4 & 0 & 2 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}$

Damit ist die Matrix $A^{T}$ in der geforderten Blockdreiecksform und deshalb reduzibel.

Basierend auf einem Artikel in:

Wikipedia.de