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 obere Blockdreiecksgestalt überführt wird.

Definition

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

$PAP^{T}={\begin{pmatrix}A_{MM}&A_{MN}\\0&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.

Sind alle Eintrage der Matrix $A$ nichtnegativ, dann ist die Irreduzibilität von $A$ äquivalent dazu, dass eine Zahl $k\in \mathbb {N}$ existiert, für die gilt: $A^{k}>0$, das heißt dass alle Einträge von $A^{k}$ positiv sind.

Eigenschaften

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.

Beispiele

Betrachte als Beispiel die folgende Matrix:

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

Vertauscht man hier die zweite und die dritte Spalte sowie die zweite und die dritte Zeile, so ist die permutierte Matrix von der Form

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

Damit ist die Matrix $A^{\prime }$ in Blockdreiecksform und $A$ deshalb reduzibel.

Literatur

• Peter Knabner, Wolf Barth: Lineare Algebra: Grundlagen und Anwendungen. 1. Auflage. Springer Spektrum, Berlin Heidelberg 2012, ISBN 978-3-642-32185-6.