§7: Der Entzerrungsalgorithmus

\underline{(7.7) DEF:} Eine (m × n)–Matrix T ≠ O heißt eine Treppenmatrix , wenn T die auf der Folie angegebene Form hat .

\underline{Bem:} Bei einer Treppenmatrix T ∈ M_{m,n}(�) kommen zuerst Nullspalten (evtl. auch keine), dann kommt der erste Einheitsvektor e_{1} ∈ �^{m}. Die nächsten Spalten sind Vielfache von e_{1} (evtl. auch gar keine), danach kommt der zweite Einheitsvektor e_{2} ∈ �^{m}, danach kommen höchstens Linearkombinationen von e_{1} und e_{2} (also Spalten, bei denen höchstens die ersten beiden Komponenten ≠ 0 sein können), dann kommt der dritte Einheitsvektor e_{3} ∈ �^{m} usw. Schließlich gibt es eine Zahl r, so daß der Einheitsvektor e_{r} als Spalte vorkommt und die restlichen Spalten von T (evtl. auch gar keine) Linearkombinationen von e_{1}, e_{2}, …, e_{r} sind. Es läßt sich also eine Treppenlinie einzeichnen, so daß in den Stufen die 1 des entsprechenden Einheitsvektors steht und unterhalb der Linie nur Nullen stehen.

\underline{Beispiele:} für Treppenmatrizen

( \begin{matrix}0 & 1 & 1 & 0 & 2 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 & 4 & 0 & 3 & 5 \\ 0 & 0 & 0 & 0 & 0 & 1 & 4 & 7 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) , ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} )

\underline{(7.8) SATZ:} Jede (m × n)–Matrix A ≠ O läßt sich durch elementare Zeilenumformungen in eine Treppenmatrix T umformen. Diese Matrix T ist durch A eindeutig bestimmt und heißt die Treppenmatrix von A. Sie wird mit T (A) bezeichnet.

\underline{(7.9) FOLG:} Ist A ≠ O eine (m × n)–Matrix, so gibt es eine invertierbare (m × m)–Matrix G mit

G · A = T (A) .

\underline{(7.10) DEF:} Es sei O ≠ A ∈ M_{m,n}(�) eine Matrix mit der zugehörigen Treppenmatrix T (A) . Dann heißt die Anzahl rg(A) der von o verschiedenen Zeilen von T (A) der Rang von A. Die Nullmatrix soll den Rang 0 haben.

\underline{Beispiel:} Besitzt eine Matrix A ∈ M_{4,5}(�) die Treppenmatrix T (A) = ( \begin{matrix}1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 2 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ,

so ist rg(A)= 3 .

\underline{(7.11) SATZ:} Für eine quadratische Matrix A ∈ M_{n}(�) sind folgende Aussagen äquivalent:

a) A ist invertierbar

b) T (A) ist invertierbar

c) T (A) = E_{n}

d) rg(A) = n .

\underline{(7.12) DEF:} Sei (⋆) Ax = b ein LGS mit der Koeffizientenmatrix A ∈ M_{m,n}(�) und dem Vektor b ∈ �^{m} der rechten Seite. Dann heißt die Matrix

(A|b) ∈ M_{m,n+1}(�) ,

die durch Anhängen von b an A entsteht, die erweiterte Koeffizientenmatrix von (⋆) .

\underline{Beispiel:} Seien A = ( \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 1 & 0 & 1 \\ 3 & 0 & 2 & 0 \end{matrix} ) ∈ M_{3,4}(�) und b = ( \begin{matrix}7 \\ 8 \\ 9 \end{matrix} ) ∈ �^{3} , dann ist

(A|b) = ( \begin{matrix}1 & 2 & 3 & 4 & 7 \\ 2 & 1 & 0 & 1 & 8 \\ 3 & 0 & 2 & 0 & 9 \end{matrix} ) ∈ M_{3,5}(�)

\underline{(7.13) SATZ:} Die Lösungsmenge eines LGS’s Ax = b ändert sich nicht, wenn man an der erweiterten Koeffizientenmatrix (A|b) elementare Zeilenumformungen vornimmt.

\underline{(7.14) FOLG:} Seien A ∈ M_{m,n}(�) und b ∈ �^{m}. Dann gibt es eine invertierbare Matrix G ∈ M_{m}(�) mit G · A = T (A) , und die LGS’e Ax = b und T (A)x = Gb haben dieselben Lösungsmengen, d.h.

Lös(A, b) = Lös(T (A), Gb) .

\underline{(7.15) SATZ:} Das LGS Ax = b ist genau dann lösbar, wenn rg(A) = rg(A|b) gilt.

\underline{(7.16) BEM:} Die Ränge von A und (A|b) können sich höchstens um 1 unterscheiden. Es gilt

Ax = b nicht lösbar ⟺ rg(A|b) = rg(A) + 1 .

\underline{(7.17) BEISPIEL:} Seien T ∈ M_{5}(�) eine Treppenmatrix und b′ ∈ �^{5} ein 5–Tupel von folgender Form:

T = ( \begin{matrix}1 & 0 & 0 & t_{14} & t_{15} \\ 0 & 1 & 0 & t_{24} & t_{25} \\ 0 & 0 & 1 & t_{34} & t_{35} \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) b′ = ( \begin{matrix}b′_{1} \\ b′_{2} \\ b′_{3} \\ 0 \\ 0 \end{matrix} ) .

Wir wollen das LGS  (⋆) T x = b′  lösen.

Die Spalten von T seien mit s_{1}, s_{2}, s_{3}, s_{4}, s_{5} bezeichnet. Dann sind also s_{1} = e_{1}, s_{2} = e_{2}, s_{3} = e_{3} Einheitsvektoren in �^{5} .

a) Das LGS (⋆) ist nach (7.15) lösbar, da rg(T |b′) = 3 = rg(T) gilt.

b) b′ ist eine Lösung von (⋆) , da T · b′ = b′ gilt (nachrechnen!).

c) Setze u_{4} := s_{4} − e_{4} und u_{5} = s_{5} − e_{5} .

Wir wollen zeigen, daß u_{4} und u_{5} Lösungen des zugehörigen homogenen LGS’s T x = o_{5} sind :

T u_{4} = ( \begin{matrix}1 & 0 & 0 & t_{14} & t_{15} \\ 0 & 1 & 0 & t_{24} & t_{25} \\ 0 & 0 & 1 & t_{34} & t_{35} \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ( \begin{matrix}t_{14} \\ t_{24} \\ t_{34} \\ −1 \\ 0 \end{matrix} ) = ( \begin{matrix}t_{14} − t_{14} \\ t_{24} − t_{24} \\ t_{34} − t_{34} \\ 0 \\ 0 \end{matrix} ) = o_{5}

T u_{5} = ( \begin{matrix}1 & 0 & 0 & t_{14} & t_{15} \\ 0 & 1 & 0 & t_{24} & t_{25} \\ 0 & 0 & 1 & t_{34} & t_{35} \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix} ) ( \begin{matrix}t_{15} \\ t_{25} \\ t_{35} \\ 0 \\ −1 \end{matrix} ) = ( \begin{matrix}t_{15} − t_{15} \\ t_{25} − t_{25} \\ t_{35} − t_{35} \\ 0 \\ 0 \end{matrix} ) = o_{5}

d) Wir wollen Lös(T, o_{5}) = L_{�} (u_{4}, u_{5}) zeigen , d.h. jede Lösung des homogenen LGS’s T x = o_{5} ist eine Linearkombination der beiden Lösungen u_{4} und u_{5} . Dazu sind zwei Teilmengenbeziehungen zu zeigen!

\underline{L_{�} (u_{4}, u_{5}) ⊆ Lös(T, o_{5})} gilt nach Aufgabe 17 .

Wir beweisen nun \underline{Lös(T, o_{5}) ⊆ L_{�} (u_{4}, u_{5})} : Sei c = (c_{i}) ∈ Lös(T, o_{5}) beliebig. Dann folgt wegen

u_{4} = s_{4} − e_{4} und u_{5} = s_{5} − e_{5}

\underline{\underline{o_{5}}} = T · c = c_{1}s_{1} + c_{2}s_{2} + c_{3}s_{3} + c_{4}s_{4} + c_{5}s_{5} = c_{1}e_{1} + c_{2}e_{2} + c_{3}e_{3} + c_{4}(u_{4} + e_{4}) + c_{5}(u_{5} + e_{5})

= \underbrace{c_{1}e_{1} + c_{2}e_{2} + c_{3}e_{3} + c_{4}e_{4} + c_{5}e_{5}}_{=c}+c_{4}u_{4} + c_{5}u_{5} = \underline{\underline{c + c_{4}u_{4} + c_{5}u_{5}}}

Also c = −(c_{4}u_{4} + c_{5}u_{5}) = (−c_{4})u_{4} + (−c_{5})u_{5} ∈ L_{�} (u_{4}, u_{5}) .

e) Eine beliebige Lösung des inhomogenen LGS’ T x = b′ ist nach (3.12) von der Form b′ + u mit u ∈ Lös(T, o_{5})

oder

Lös(T, b′) = { b′ + su_{4} + tu_{5} | s, t ∈ � }

Als Verallgemeinerung dieses (bewiesenen) Beispieles erhalten wir:

\underline{(7.18) SATZ:} Sei T ∈ M_{n}(�) eine Treppenmatrix vom Rang r mit den Spalten s_{1}, s_{2}, …, s_{n}. Es gelte s_{k} = e_{k} für alle k = 1, 2, …, r. Ferner sei b′ = (b′_{i}) ∈ �^{n} ein n–Tupel mit b′_{j} = 0 für alle j > r. Dann gilt:

a) Das LGS T x = b′ ist lösbar, und b′ ist eine Lösung.

b) T · (s_{j} − e_{j}) = o_{n} , d.h.

u_{j} := s_{j} − e_{j} (j = r + 1, …, n)

ist eine Lösung des zugehörigen homogenen LGS’s T x = o_{n}.

c) Lös(T, o_{n}) = L_{�} (u_{r+1}, …, u_{n}) , d.h. jede Lösung des homogenen LGS’s T x = o_{n} ist eine Linearkombination der Lösungen u_{r+1}, …, u_{n}.

d) Jede Lösung von T x = b′ ist von der Form b′ + t_{r+1}u_{r+1} + … + t_{n}u_{n} (t_{r+1}, …, t_{n} ∈ �) .

\underline{(7.19) BEISPIEL:} Wir betrachten jetzt ein LGS Bx = c aus 4 Gleichungen für 5 Unbekannte, dessen erweiterte Koeffizientenmatrix

(B|c) = ( \begin{matrix}1 & −1 & 0 & 1 & −1 & 4 \\ 0 & 0 & 1 & 1 & 2 & −2 \\ 1 & −1 & −1 & 0 & 2 & 1 \\ −1 & 1 & 2 & 1 & 0 & −3 \end{matrix} ) ∈ M_{4,6}(�)

sein soll. Da wir die Lösungen (das sind hier bei 5 Unbekannten 5–Tupel) aus den Spalten ablesen wollen, hängen wir an (B|c) eine Nullzeile an und erhalten die Matrix

(A|b) = ( \begin{matrix}1 & −1 & 0 & 1 & −1 & 4 \\ 0 & 0 & 1 & 1 & 2 & −2 \\ 1 & −1 & −1 & 0 & 2 & 1 \\ −1 & 1 & 2 & 1 & 0 & −3 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) ∈ M_{5,6}(�) ,

die jetzt auch 5 Zeilen hat. Die LGS’e Bx = c und Ax = b haben dieselben Lösungen. Wir bringen nun (A|b) durch elementare Zeilenumformungen auf Treppenform. Das Ergebnis (nachrechnen!) ist die Matrix

(T |b′) = ( \begin{matrix}1 & −1 & 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Wegen rg(A) = rg(A|b) ist das LGS Ax = b (und damit auch Bx = c) lösbar. Im Gegensatz zu (7.17) sind die drei Einheitsvektoren e_{1}, e_{2}, e_{3} ∈ �^{5} jedoch nicht die ersten drei Spalten von (T |b′) , sondern sind die erste, dritte bzw. fünfte Spalte. Um jetzt trotzdem wie in (7.17) verfahren zu können, bringen wir die drei Einheitsvektoren durch Spaltenvertauschungen an die Positionen 1,2 und 3. Spaltenvertauschungen bedeuten lediglich eine Umbenennung der Unbekannten (s. Übungen). Jetzt können wir das neue LGS T′x = b′ lösen. Wenn wir diese Vertauschungen dann wieder rückgängig machen, erhalten wir schließlich die gesuchten Lösungen des LGS’s Bx = c. Vertauschen wir also die 2–te mit der 3–ten Spalte und anschließend in der neuen Matrix die 3–te mit der 5–ten Spalte, so erhalten wir die Matrix

(T′|b′) = ( \begin{matrix}1 & 0 & 0 & 1 & −1 & 3 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & −1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Wir ersetzen nun die Nullen in der Hauptdiagonale durch −1 :

(S|b′) = ( \begin{matrix}1 & 0 & 0 & 1 & −1 & 3 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & −1 \\ 0 & 0 & 0 & −1 & 0 & 0 \\ 0 & 0 & 0 & 0 & −1 & 0 \end{matrix} ) .

\begin{matrix}↑ & ↑ & ↑ \\ u′_{4} & u′_{5} & b′ \end{matrix}

Bezeichnen wir die 4–te Spalte mit u′_{4} und die 5–te Spalte mit u′_{5} , so folgt

(⋆) Lös(T′, b′) = \{ b′ + su′_{4} + tu′_{5} | s, t ∈ � \} = \{ ( \begin{matrix}3 + s − t \\ s \\ −1 \\ −s \\ −t \end{matrix} ) | s, t ∈ � \} .

Nun müssen wir nur noch die Umbenennungen der Unbekannten (d.h. die Spaltenvertauschungen) wieder rückgängig machen. Dazu vertauschen wir in dem Lösungsvektor

( \begin{matrix}3 + s − t \\ s \\ −1 \\ −s \\ −t \end{matrix} )

(oder in den Vektoren u′_{4}, u′_{5}, b′) zuerst die 3–te mit der 5–ten Komponente, danach die 2–te mit der 3–ten Komponente, und erhalten

( \begin{matrix}3 + s − t \\ s \\ −1 \\ −s \\ −t \end{matrix} ) ⟶ ( \begin{matrix}3 + s − t \\ s \\ −t \\ −s \\ −1 \end{matrix} ) ⟶ ( \begin{matrix}3 + s − t \\ −t \\ s \\ −s \\ −1 \end{matrix} ) .

Damit ist

Lös(B, c) = Lös(T′, b′) = \{ ( \begin{matrix}3 + s − t \\ −t \\ s \\ −s \\ −1 \end{matrix} ) | s, t ∈ � \} ,

was leicht nachgeprüft werden kann, indem man B mit dem Lösungsvektor ausmultipliziert.

Nehmen wir diese Vertauschungen mit den Komponenten der Vektoren u′_{4}, u′_{5} und b′ vor, so erhalten wir

u′_{4} = ( \begin{matrix}1 \\ 1 \\ 0 \\ −1 \\ 0 \end{matrix} ) ⟶ u_{4} := ( \begin{matrix}1 \\ 0 \\ 1 \\ −1 \\ 0 \end{matrix} ) , u′_{5} = ( \begin{matrix}−1 \\ 0 \\ 0 \\ 0 \\ −1 \end{matrix} ) ⟶ u_{5} := ( \begin{matrix}−1 \\ −1 \\ 0 \\ 0 \\ 0 \end{matrix} ) ,

b′ = ( \begin{matrix}3 \\ 0 \\ −1 \\ 0 \\ 0 \end{matrix} ) ⟶ v := ( \begin{matrix}3 \\ 0 \\ 0 \\ 0 \\ −1 \end{matrix} ). Die Lösungsmenge ist dann

Lös(B, c) = \{ v + su_{4} + tu_{5} | s, t ∈ � \} = \{( \begin{matrix}3 \\ 0 \\ 0 \\ 0 \\ −1 \end{matrix} ) + s( \begin{matrix}1 \\ 0 \\ 1 \\ −1 \\ 0 \end{matrix} ) + t( \begin{matrix}−1 \\ −1 \\ 0 \\ 0 \\ 0 \end{matrix} ) | s, t ∈ � \}

= \{ ( \begin{matrix}3 + s − t \\ −t \\ s \\ −s \\ −1 \end{matrix} ) | s, t ∈ � \} .

(7.20) Beispiel für den Entzerrungsalgorithmus

Wir greifen noch einmal das LGS Bx = c aus (7.19) auf. Durch einen kleinen “Trick” können wir die Lösungen direkt ablesen, ohne daß wir explizit die Spaltenvertauschungen ausführen müssen. Dazu bringen wir auch die erweiterte Koeffizientenmatrix

(B|c) = ( \begin{matrix}1 & −1 & 0 & 1 & −1 & 4 \\ 0 & 0 & 1 & 1 & 2 & −2 \\ 1 & −1 & −1 & 0 & 2 & 1 \\ −1 & 1 & 2 & 1 & 0 & −3 \end{matrix} ) ∈ M_{4,6}(�)

durch elementare Zeilenumformungen auf Treppenform

(T |c′) = ( \begin{matrix}1 & −1 & 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ) .

Hieraus bilden wir eine (5 × 6)–Matrix (T′, c′′) , indem wir 2 Nullzeilen so einfügen, daß die in den Stufen der Treppenlinie stehenden Einsen der Einheitsvektoren auf der Hauptdiagonale von T′ stehen, und indem wir die unterste Nullzeile streichen (die Matrix (T′|c′′) muß soviel Zeilen haben, wie es Unbekannte in dem LGS gibt, hier 5) .

(T′|c′′) = ( \begin{matrix}1 & −1 & 0 & 1 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 \end{matrix} )

Nun ersetzen wir die Nullen in der Hauptdiagonale durch −1 (hier 2–mal)

( \begin{matrix}1 & −1 & 0 & 1 & 0 & 3 \\ 0 & −1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & −1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & −1 \end{matrix} )

\begin{matrix}↑ & ↑ & ↑ \\ u_{2} & u_{4} & v \end{matrix}

Jetzt können wir die relevanten Größen ablesen: v ist eine spezielle Lösung von Bx = c, und u_{2}, u_{4} sind Lösungen des zugehörigen homogenen LGS’s , aus denen sich alle Lösungen von Bx = o_{4} linear kombinieren lassen.

Die Lösungsmenge ist

Lös(B, c) = \{ v+su_{4}+tu_{2} | s, t ∈ IR \} = \{( \begin{matrix}3 \\ 0 \\ 0 \\ 0 \\ −1 \end{matrix} ) + s( \begin{matrix}1 \\ 0 \\ 1 \\ −1 \\ 0 \end{matrix} ) + t( \begin{matrix}−1 \\ −1 \\ 0 \\ 0 \\ 0 \end{matrix} ) | s, t ∈ � \}

= \{( \begin{matrix}3 + s − t \\ −t \\ s \\ −s \\ −1 \end{matrix} ) | s, t ∈ IR \} .

Dies ist genau das in (7.19) gefundene Ergebnis!

Allgemein gilt:

(7.21) Der Entzerrungsalgorithmus

Seien A ∈ M_{m,n}(�) und b ∈ �^{m}. Für die Lösung des LGS’s Ax = b sind in Verallgemeinerung von (7.19) und (7.20) die folgenden Schritte auszuführen:

• Bringe die erweiterte Koeffizientenmatrix (A|b) durch elementare Zeilenumformungen auf Treppenform. Das Ergebnis ist eine Matrix (T (A)|b′) vom Format (m, n + 1) . An dieser Matrix läßt sich insbesondere ablesen, ob das LGS lösbar ist oder nicht. Im Falle der Lösbarkeit führe die nächsten Schritte aus:

• Füge Nullzeilen ein oder streiche Nullzeilen, so daß aus (T (A)|b′) eine Matrix B vom Format (n, n + 1) entsteht, bei der die Einsen, die in den Stufen der Treppenlinie standen, jetzt in der Hauptdiagonale stehen.

• Ersetze in der Matrix B die Nullen in der Hauptdiagonale durch −1 . Die entstandene Matrix heiße C.

• Die rechte Spalte von C ist eine spezielle Lösung von Ax = b, die Spalten mit −1 in der Haupdiagonalposition sind Lösungen von Ax = o_{m}, aus denen sich alle Lösungen von Ax = o_{m} linear kombinieren lassen.

• Bilde die Lösungsmenge von Ax = b entsprechend (3.13) .