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.

DefinitionBearbeiten

Eine Matrix   heißt reduzibel, wenn eine Permutationsmatrix   existiert, so dass

 

Dabei ist   aus   mit   und die anderen Blockmatrizen dementsprechend passend dimensioniert. Ist diese Umordnung nicht möglich, so heißt die Matrix irreduzibel.

Potenz und IrreduzibilitätBearbeiten

Sind alle Einträge der Matrix   nichtnegativ und ist die Hauptdiagonale echt positiv, dann ist die Irreduzibilität von   äquivalent dazu, dass eine Zahl   existiert, für die

 

gilt, das heißt, dass alle Einträge der Matrixpotenz   positiv sind.[1] Etwas schwächer ist die Aussage, dass eine Matrix   irreduzibel ist, wenn   gilt und ein   existiert, sodass   ist.

Eine Matrix   mit nichtnegativen Einträgen ist genau dann irreduzibel, wenn es zu jedem Indexpaar   eine Zahl   gibt, so dass der  -Eintrag von   positiv ist.

VerwendungBearbeiten

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   irreduzibel. Außerdem ist die Irreduzibilität einer stochastischen Matrix äquivalent zur Irreduzibilität der Markow-Kette, welche durch die stochastische Matrix beschrieben wird.

BeispielBearbeiten

 
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:

 

Die transponierte Matrix ist

 

Damit ist die Matrix   in der geforderten Blockdreiecksform und   deshalb reduzibel.

WeblinksBearbeiten

LiteraturBearbeiten

EinzelnachweiseBearbeiten

  1. Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen. Springer Spektrum, 2013, S. 842.