imported>Fan-vom-Wiki: Tippfehler

2024-02-08T01:02:37Z

Tippfehler

Neue Seite

Eine '''Irreduzible Matrix''', eigentlich '''Unzerlegbare Matrix''', ist eine Matrix mit einer speziellen Eigenschaft, die im Jahr 1912 von [[Ferdinand Georg Frobenius |Georg Frobenius]] in die [[Lineare Algebra]] eingeführt worden ist.<ref>{{Literatur |Autor=Georg Frobenius |Titel=Über Matrizen aus nicht negativen Elementen |Hrsg= |Sammelwerk=Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin: Jahrgang 1912. Erster Halbband. Januar bis Juni |Verlag=Verlag der Königlichen Akademie der Wissenschaften. In Commission bei Georg Reimer |Ort=Berlin |Datum=1912 |Seiten=456–477 |Online=[https://upload.wikimedia.org/wikipedia/commons/4/44/Ueber_Matrizen_aus_nicht_negativen_Elementen.pdf Originalartikel]}}</ref> Das deutsche Wort „unzerlegbar“, das Frobenius für diese Eigenschaft verwendete, wurde als „irreducible“, „unreduced“ oder „indecomposable“ ins Englische übertragen.<ref>Richard S. Varga, 1962, S. 19</ref> 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.<ref>Feliks R. Gantmacher, 1986, S. 395</ref> Um festzustellen, ob eine Matrix diese Eigenschaft besitzt, bedient man sich einer einfachen Methode der [[Graphentheorie]].

Eine [[Matrix (Mathematik)|Matrix]] ist unzerlegbar (irreduzibel), wenn sie durch Permutation von Zeilen und Spalten nicht in eine untere (oder obere) [[Blockmatrix#Blockdreiecksmatrix |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]] <math>A</math> heißt '''zerlegbar (reduzibel)''', wenn eine [[Permutationsmatrix]] <math>P</math> existiert, so dass sie durch das Matrixprodukt <math>PAP^T</math> in eine (hier obere) [[Blockmatrix#Blockdreiecksmatrix |Blockdreiecksmatrix]] überführt werden kann,

:<math>
PAP^T=
\begin{bmatrix}
\mathbf{A}_{11} & \mathbf{A}_{12} & \cdots & \mathbf{A}_{1n} \\
0 & \mathbf{A}_{22} & \cdots & \mathbf{A}_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \mathbf{A}_{nn}
\end{bmatrix} ,
</math>

mit Untermatrizen <math>\mathbf{A}_{ij}</math>.<ref>{{Literatur |Autor=Rudolf Kochendörffer |Titel=Determinanten und Matrizen |Auflage=2 |Verlag=B. G. Teubner |Ort=Leipzig |Datum=1961 |Umfang=VI, 144 S. |Seiten=109}}</ref>

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 [[Hauptdiagonale]]n (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 <math>\mathbf{A}_{11}</math>sucht, unter der (in allen Spalten) nur Nullen stehen:

:<math>
PAP^T=
\begin{bmatrix}
\mathbf{A}_{11} & \mathbf{A}_{12} \\
0 & \mathbf{A}_{22} \\
\end{bmatrix} .
</math>

Dann hat man die Eigenschaft der Matrix, ''zerlegbar (reduzibel)'' zu sein, bereits gefunden.<ref> Richard S. Varga, 1962, S. 18</ref>

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

:<math>A^k >0 </math>

gilt, das heißt, dass alle Einträge der [[Matrixpotenz]] <math>A^k</math> positiv sind.<ref>Peter Knabner, Wolf Barth, 2013, S. 842</ref>
Etwas schwächer ist die Aussage, dass eine Matrix <math> A </math> irreduzibel ist, wenn <math> A \geq 0 </math> gilt und ein <math>k \in \mathbb{N}</math> existiert, sodass <math> A^k >0 </math> ist.

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

== Verwendung ==
Irreduzible Matrizen spielen eine Rolle für die Existenz von [[Eigenvektor]]en 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 [[Gerichteter Graph|gerichteten Graphen]] ist genau dann irreduzibel, wenn der Graph [[Zusammenhang (Graphentheorie)|stark zusammenhängend]] ist.
Des Weiteren gilt: ist <math>A</math> irreduzibel, so ist auch <math>A^T</math> irreduzibel. Außerdem ist die Irreduzibilität einer [[Stochastische Matrix|stochastischen Matrix]] äquivalent zur [[Irreduzible Markow-Kette|Irreduzibilität der Markow-Kette]], welche durch die stochastische Matrix beschrieben wird.

== Beispiel ==

[[File:Adjazenzgraph.svg |mini |Der [[Adjazenzgraph]] der Matrix <math>A</math>]]

Die folgende Matrix

:<math>
A =
\left[\begin{array}{rr|rr}
0 & 3 & 0 & 0 \\
2 & 0 & 4 & 0 \\
\hline
0 & 0 & 0 & 1 \\
0 & 0 & 2 & 0
\end{array}\right]
</math>

ist eine obere [[Blockmatrix#Blockdreiecksmatrix |Blockdreiecksmatrix]] und somit zerlegbar (reduzibel). Das kann man ohne weitere Hilfsmittel wie Graphen sofort erkennen. Die Grafik zeigt trotzdem einen [[Gerichteter Graph |gerichteten Graph]], und zwar den [[Adjazenzgraph]] der Matrix <math>A</math>. 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'' [[Zusammenhang (Graphentheorie)|stark zusammenhängend]]. Deshalb ist der Graph (und damit die Matrix) reduzibel (zerlegbar).

== Literatur ==
*{{Literatur |Autor=[[Richard S. Varga]] |Titel=Matrix Iterative Analysis |Verlag=Prentice-Hall |Ort=Englewood Cliffs, NJ |Datum=1962 |Umfang=XIII, 322}}
* {{Literatur |Autor=Feliks R. Gantmacher |Titel=Matrizentheorie |Verlag=VEB Deutscher Verlag der Wissenschaften |Ort=Berlin |Datum=1986 |ISBN=3-326-00001-4 |Umfang=654}}
* {{Literatur | Autor=[[Peter Knabner]], [[Wolf Barth (Mathematiker)|Wolf Barth]] | Titel=Lineare Algebra. Grundlagen und Anwendungen | Reihe=Springer-Lehrbuch | Verlag=Springer Spektrum| Ort=Berlin u. a.| Jahr=2013| ISBN=978-3-642-32185-6 }}

== Weblinks ==
* {{MathWorld
| id = ReducibleMatrix
| title = Reducible Matrix
| author =
}}

== Einzelnachweise ==
<references />

[[Kategorie:Matrix]]

[[en:Perron–Frobenius theorem#Classification of matrices]]

Irreduzible Matrix - Versionsgeschichte

imported>Fan-vom-Wiki: Tippfehler