Irreduzibilität einer Matrix zeigen

Question

Aufgabe:

Eine Matrix \(A \in \mathbb{R}^{n \times n}\) ist genau dann irreduzibel, wenn der zugehörige Graph \(G(A).=(V,E)\) mit \(V:=\{P_{1},P_{2},...,P_{N}\}\), \(E=\{E_{ij} :a_{ij} \neq 0, 1 \leq i,j \leq n\}\) zusammenhängend ist.

Problem/Ansatz:

Ich weiß nur wann eine Matrix irreduzibel ist.

Über Hilfe würde ich mich freuen.

Comments

Ich weiß nur wann eine Matrix irreduzibel ist.

Das ist schonmal gut. Aber wir kennen Eure genaue Def. nicht. Also lass mal sehen.

---

Eine Matrix \(A \in \mathbb{R}^{n}\) heißt irreduzibel, wenn es keine Permutationsmatrix \(P\) gibt sodass $$ P^TAP =\begin{pmatrix} \tilde{A}_{11} & 0\\ \tilde{A}_{21} & \tilde{A}_{22} \end{pmatrix} $$

mit \(\tilde{A}_{11} \in \mathbb{R}^{p \times p},\tilde{A}_{22} \in \mathbb{R}^{q \times q},\tilde{A}_{21} \in \mathbb{R}^{q \times p}, \) \(p,q \in \mathbb{R}^n\) und \(p+q=n\).

---

Habt ihr auch noch irgendwelche Sätze dazu in der Vorlesung gehabt?

---

Zu der Irreduzibilität direkt haben wir nichts weiteres.

Answer 1

Ich gehe davon aus, dass der Graph als gerichtet verstanden wird, und dass du stark zusammenhängend meinst.

Außerdem hilfreich zu wissen wäre es, ob du außer der Definition auch irgendwelche Lemmata über irreduzible Matrizen kennst. Je besser du deinen Wissensstand rüberbringen kannst, desto besser kann man dir helfen. Im Übrigen möchte hier keiner der Helfer bei jeder Frage jedem FS die Informationen aus der Nase herausziehen.

Zuallererst: Die Irreduziblität einer Matrix ist eine boolsche Eigenschaft einer Matrix, d.h. du unterscheidest nur zwischen Nulleinträgen und Nichtnulleinträgen, da ja nur Einträge permutiert werden. Alle Nichtnulleinträge durch \(1\) zu ersetzen, verändert also die Irreduziblität nicht. Wir können also oBdA davon ausgehen, dass \(A\) nur als Einträge \(0\) oder \(1\) hat und damit die Adjazenzmatrix von \(G\) ist. Es reicht also, die Aussage für beliebige gerichtete Graphen und deren Adjazenzmatrizen zu beweisen.

Die Adjazenzmatrix \(A\) von \(G\) besitzt zwei nützliche Eigenschaften, mit denen wir jetzt Algebra machen können. Erstens ist die Matrix \(A\) nichtnegativ (d.h. alle Einträge nichtnegativ), in diesem Fall ist Irreduziblität äquivalent dazu, dass für alle \(i,j\) ein \(k\) existiert mit \(\left(A^k\right)_{ij}>0\). Das ist hoffentlch ein Lemma in der Vorlesung, ansonsten ist es auch nicht schwer zu beweisen. Potenzen von Dreiecksblockmatrizen sind auch wieder Dreiecksblockmatrizen, d.h. wenn beliebige Einträge irgendwann mal positiv werden, wie zum Beispiel ein Eintrag des \(0\)-Blocks rechts oben, kannst du rechts oben keinen \(0\)-Block stehen haben.

Jetzt haben die Einträge der Potenzen von \(A\) als Adjazenzmatrix von \(G\) aber auch eine starke Interpretation: Der Eintrag \(\left(A^k\right)_{ij}\) ist gerade die Anzahl der Wege der Länge \(k\) von Knoten \(i\) zu knoten \(j\). Wenn für alle \(i,j\) ein \(k\) existiert mit \(\left(A^k\right)_{ij}>0\) dann existieren für alle \(i,j\) auch ein \((i,j)\)-Weg und \(G\) ist damit stark zusammenhängend.

Das ist der konzeptuell anschaulichste Beweis, der mir dazu einfällt. Aber wie gesagt, diesen Weg einzuschlagen ist nur möglich, wenn du das Lemma kennst oder selbst beweisen kannst.

Comments

Danke für die ausführliche Antwort. Leider kannte ich das von dir gennante Lemma nicht. Das einzige Satz/Lemma was ich noch kenne und mit irreduziblen Matrix zu tun hat ist:

Genügen die Zeilensummen einer irreduziblen Matrix \(A \in \mathbb{R}^{n \times n} \)den Bedingungen: $$\sum_{k=1,k \neq i}^{n} |a_{ik}| \leq |a_{ii}|$$ für \(i =1,2,3,...,n\) und

$$\sum_{k=1,k \neq r}^{n} |a_{rk}| \leq |a_{rr}|$$ für ein \(r \in \{1,2,3,...,n\}\)

so ist A regulär und das Jacobi und Gauß-Seidel Verfahren konvergieren.

Answer 2

Ich versuche mal eine "elementare" Antwort:

A ist reduzibel, wenn es eine nichttriviale disjunkte Zerlegung \(\{1, \ldots,n\}=I \cup J\) gibt mit \(a_{i,j}=0\) falls \(i \in I, j \in J\).

1. Wenn A reduzibel ist, dann ist G mit \(V:=\{1, \ldots,n\}\)  nicht zusammenhängend:

Sei \(a \in I,b \in J\). Wenn \((a=k_1, \ldots k_m=b)\) ein Weg in G ist, dann gibt es ein kleinstes i, so dass \(k_i \in I\) ist und \(k_{i+1} \in J\). Dann wäre \((k_i,k_{i+1})\) keine Kante in G, Widerspruch.

2. Wenn G nicht zusammenhängend ist, dann ist A reduzibel.

Sei \(a,b \in V\) so, dass es keinen Weg in G gibt, der a und b verbindet. Definiere:

$$I:=\{i \in V \mid i=a \text{ oder es existiert in G ein Weg } (a, \ldots, i)\}$$

Das Komplement J enthält b. Sein nun \(i \in I,j \in J\). Dann existiert ein Weg \((a=k_1, \ldots k_m=i)\) in G. Wenn jetzt \(a_{i,j}\neq 0\) wäre, dann wäre \((a=k_1, \ldots k_m=i,j)\) ein Weg und es wäre \(j \in I\)