Irreduzible Matrix

Eine Irreduzible Matrix, eigentlich Unzerlegbare Matrix, ist eine Matrix mit einer speziellen Eigenschaft, die im Jahr 1912 von Georg Frobenius in die Lineare Algebra eingeführt worden ist. Das deutsche Wort „unzerlegbar“, das Frobenius für diese Eigenschaft verwendete, wurde als „irreducible“, „unreduced“ oder „indecomposable“ ins Englische übertragen. Das Adjektiv „irreduzibel“ kann nur durch eine unkritische Rückübersetzung in die deutsche mathematische Fachliteratur gekommen sein. Das Wort „unzerlegbar“ dagegen wird in deutschen mathematischen Fachbüchern verwendet, die aus dem Russischen ins Deutsche übersetzt worden sind. Um festzustellen, ob eine Matrix diese Eigenschaft besitzt, bedient man sich einer einfachen Methode der Graphentheorie.

Eine Matrix ist unzerlegbar (irreduzibel), wenn sie durch Permutation von Zeilen und Spalten nicht in eine untere (oder obere) Blockdreiecksmatrix überführt werden kann. Unzerlegbare Matrizen sind von Bedeutung in der Theorie der positiven Eigenwerte und -vektoren, zum Beispiel für den Satz von Perron-Frobenius.

Ein lineares Gleichungssystem oder ein Eigenwertproblem mit einer zerlegbaren Matrix dagegen verringert die Anzahl der Rechenoperationen, die für die Lösung des Problems erforderlich ist.

Definition

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

$PA{P}^T=\left[\begin{array}{cccc}{𝐀}_{11}& {𝐀}_{12}& \cdots & {𝐀}_{1n}\\ 0& {𝐀}_{22}& \cdots & {𝐀}_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {𝐀}_{nn}\end{array}\right],$

mit Untermatrizen ${𝐀}_{ij}$.

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 ${𝐀}_{11}$sucht, unter der (in allen Spalten) nur Nullen stehen:

$PA{P}^T=\left[\begin{array}{cc}{𝐀}_{11}& {𝐀}_{12}\\ 0& {𝐀}_{22}\end{array}\right].$

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

Potenz und Irreduzibilität

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

$A^k>0$

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

Eine Matrix $A$ mit nichtnegativen Einträgen ist genau dann irreduzibel, wenn es zu jedem Indexpaar $(i,j)$ eine Zahl $k\in \mathbb{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 $A$ 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 $A$

Die folgende Matrix

$A=\left[\begin{array}{cccc}0& 3& 0& 0\\ 2& 0& 4& 0\\ 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 $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).

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Vorlage:MathWorld