Irreduzible Matrix

spezielle Eigenschaft einer 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.[1] Das deutsche Wort „unzerlegbar“, das Frobenius für diese Eigenschaft verwendete, wurde als „irreducible“, „unreduced“ oder „indecomposable“ ins Englische übertragen.[2] 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.[3] 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

Bearbeiten

Eine dünnbesetzte Matrix   heißt zerlegbar (reduzibel), wenn eine Permutationsmatrix   existiert, so dass sie durch das Matrixprodukt   in eine (hier obere) Blockdreiecksmatrix überführt werden kann,

 

mit Untermatrizen  .[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  sucht, unter der (in allen Spalten) nur Nullen stehen:

 

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

Potenz und Irreduzibilität

Bearbeiten

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.[6] 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.

Verwendung

Bearbeiten

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.

Beispiel

Bearbeiten
 
Der Adjazenzgraph der Matrix  

Die folgende Matrix

 

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  . 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

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  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