Hallo,
ich wollte mal nachfragen wie man genau nachweist, dass eine Matrix irreduzibel ist. Ich kann das leider absolut nicht nachvollziehen. Vielen Dank im Voraus.
Übung 13/ G47
- Lysapala
- Geschlossen
-
-
Hey,
eine Matrix A (n x n) ist irreduzibel, wenn der zugehörige gerichtete Graph zusammenhängend ist.
Den zugehörigen gerichteten Graphen G(A) bestimmt man wie folgt:
- Der Graph hat n Knoten Pi. Diese sind genau die Diagonaleinträge der Matrix. Im Beispiel 7.1.4 auf Seite 179 im Skript sind die Knoten also: P1=1, P2=4, P3=0 und P4=-7
- Eine gerichtete Kante verbindet Pi imt Pj genau dann, wenn aij[Blockierte Grafik: https://wikimedia.org/api/rest_v1/media/math/render/svg/38cc3d8d8c60120bc2f905bae4d5e10d8ad6a3f4]0. Heißt also, dass eine gerichtete Kante von P1 nach P2 existiert, wenn der Eintrag a12 nicht Null ist.
- Ein gerichteter Weg ist die Aneinanderfügung gerichteter Kanten
- G(A) heißt zusammenhängend, wenn es für jedes Indexpaar (i,j) mit i[Blockierte Grafik: https://wikimedia.org/api/rest_v1/media/math/render/svg/38cc3d8d8c60120bc2f905bae4d5e10d8ad6a3f4]j einen gerichteten Weg von Pi nach Pj gibt.
- Also muss es eine gerichteten Weg von jedem Punkt zu jedem anderen Punkt geben.
- Von P1 muss man also im Beispiel nach P2,P3 und P4 kommen. Dies geht entweder direkt über eine gerichtete Kante, wenn also a12, a13 oder a14 [Blockierte Grafik: https://wikimedia.org/api/rest_v1/media/math/render/svg/38cc3d8d8c60120bc2f905bae4d5e10d8ad6a3f4]0 ist, oder über einen gerichteten Weg die etwa zuerst zu Knoten 3 und dann zu Knoten 2
Anhand eines Beispiels erklärt es sich am besten:
- Die gerichtete Kante von P1 nach P2 existiert, weil a12=1 nicht 0 ist.
- Die gerichtete Kante von P1 nach P3 existiert nicht, weil a13=0 ist.
- Die gerichtete Kante von P1 nach P4 existiert, weil a14=2 ist.
- ..usw.
- Die gerichtete Kante von P2 nach P1 existiert nicht, weil a21=0 ist.
- Die gerichtete Kante von P4 nach P3 existiert, weil a43=1 ist.
- ..usw.
Der Graph ist dann zusammenhängend, wenn man von jedem Knoten zu jedem anderen Knoten laufen kann.
Im Beispiel kommt man von P1 nach P2 und P4. Nach P3 kommt man über einen Umweg: P1->P2->P4->P3.Wenn das für jeden Punkt geht ist der zugehörige gerichtete Graph zusammenhängend und A somit Irreduzibel.