Einschub B) Lineare Gleichungssysteme

Wir wollen hier LGS’e einmal in der Sprache von linearen Abbildungen beschreiben. Damit vereinfachen sich frühere Überlegungen, und die Resultate ergeben sich in natürlicher Weise.

Vorgelegt sei das LGS

(⋆) A · x = b

mit der Koeffizientenmatrix A ∈ M_{m,n}(K) und dem Vektor b ∈ K^{m} der rechten Seite. Ein (bekanntes) Kriterium für die Lösbarkeit von (⋆) gibt das folgende Lemma:

\underline{(B.1) LEMMA:} Ax = b lösbar ⟺ rg(A) = rg(A, b)

\underline{Bew:} Sei A ∈ M_{m,n}(K) die Matrix mit den Spalten a_{1}, …, a_{n} ∈ K^{m}. Dann gilt:

Ax = b lösbar ⟺ b ∈ L_{K}(a_{1}, …, a_{n})
⟺ L_{K}(a_{1}, …, a_{n}) = L_{K}(a_{1}, …, a_{n}, b)
⟺ dim_{K}(L_{K}(a_{1}, …, a_{n})) = dim_{K}(L_{K}(a_{1}, …, a_{n}, b) )
(da L_{K}(a_{1}, …, a_{n}) UVR von L_{K}(a_{1}, …, a_{n}, b) ist )
⟺ rg_{s}(A) = rg_{s}(A, b)
⟺ rg(A) = rg(A, b)  □

Die Koeffizientenmatrix A definiert die lineare Abbildung

f_{A} : K^{n} ⟶ K^{m} , v ⟼ A · v

Nun gilt für v ∈ K^{n} : v ∈ Lös(A, b) ⟺ A · v = b ⟺ f_{A}(v) = b ⟺ v ∈ f_{A}^{−1}({b}), d.h.

Lös(A, b) = f_{A}^{−1}({b})

Insbesondere gilt Lös(A, o_{m}) = f_{A}^{−1}({o_{m}}) = Kern(f_{A})

Damit ist also die Lösungsmenge eines homogenen LGS’s als Kern einer linearen Abbildung ein Unterraum von K^{n}, für dessen Dimension sich nach dem Rangsatz

dim_{K}(Lös(A, o_{m})) = dim_{K}(Kern(f_{A})) = n − rg_{K}(f_{A}) = n − rg(A)

ergibt. Ist v_{0} ∈ Lös(A, b) eine spezielle Lösung von (⋆) , so gilt

Lös(A, b) = f_{A}^{−1}({b}) = v_{0} + Kern(f_{A}) = v_{0} + Lös(A, o_{m})

Ist rg(A) = r, so gilt dim_{K}(Lös(A, o_{m})) = n − r, und Lös(A, o_{m}) besitzt eine Basis {v_{1}, v_{2}, …, v_{n−r}} aus n − r Lösungsvektoren aus Lös(A, o_{m}). Damit läßt sich jede Lösung v von (⋆) darstellen in der Form

v = v_{0} + α_{1}v_{1} + … + α_{n−r}v_{n−r}

mit Koeffizienten α_{i} ∈ K.

Zusammenfassend erhalten wir die folgenden Ergebnisse, denen wir schon in §10 begegnet sind:

\underline{(B.2) SATZ:} Seien A ∈ M_{m,n}(K) eine Matrix vom Range r und b ∈ K^{m}. Für das LGS

A · x = b

gilt:

a) Die Lösungsmenge L_{0} = Lös(A, o_{m}) des zugehörigen homogenen LGS’s

A · x = o_{m}

ist ein Untervektorraum von K^{n}, der die Dimension n − r hat.

b) Ist das LGS A · x = b lösbar und ist v_{o} ∈ L := Lös(A, b) eine spezielle Lösung und ist { v_{1}, …, v_{n−r} } eine Basis von L_{0} , so gilt

L = v_{0} + L_{0} = { v_{0} + α_{1}v_{1} + … + α_{n}v_{n} | α_{i} ∈ K }

Die folgenden Aussagen ergeben sich sofort:

\underline{(B.3) SATZ:} Seien A ∈ M_{m,n}(K) und b ∈ K^{m}. Dann gilt für das LGS (⋆) A · x = b:

a) (⋆) ist für jedes b ∈ K^{m} lösbar ⟺ f_{A} ist surjektiv ⟺ rg(A) = m

b) A · x = o_{m} besitzt genau eine Lösung ⟺ f_{A} ist injektiv ⟺ rg(A) = n

c) Ist (⋆) lösbar, so gilt: (⋆) eindeutig lösbar ⟺ rg(A) = n.

\underline{(B.4) FOLG:} Sei A ∈ GL_{n}(K) . Dann ist das LGS

(⋆) A · x = b

für jedes b ∈ K^{n} eindeutig lösbar. Zusatz: A^{−1} · b ist die eindeutig bestimmte Lösung.

\underline{Bew:} Die erste Behauptung ergibt sich sofort aus (B.3). Wir wollen hier aber noch einen direkten Beweis geben, der nur die Invertierbarkeit der Koeffizientenmatrix benutzt: Existenz: Für v := A^{−1}b ∈ K^{n} gilt Av = A(A^{−1}b) = (AA^{−1})b = E_{n}b = b, d.h. v ∈ Lös(A, b) . Eindeutigkeit: Sind v, v′ ∈ K^{n} Lösungen von (⋆) , so folgt Av = b = Av′, also Av = Av′. Linksmultiplikation mit A^{−1} ergibt v = v′. □

Alternativer Beweis von (B.4):

Da A invertierbar ist, ist f_{A} : K^{n} ⟶ K^{n} ein Isomorphismus. Daher besitzt b ∈ K^{n} genau ein Urbild unter f_{A} und das LGS (⋆) daher genau eine Lösung, nämlich

f_{A}^{−1}(b) = A^{−1} · b .

Beim Entzerrungsalgorithmus muß die erweiterte Koeffizientenmatrix (A, b) eines LGS’s Ax = b auf Treppenform gebracht werden. Dies geschieht mit Hilfe elementarer Zeilenumformungen, die einer Linksmultiplikation mit Elementarmatrizen entsprechen. Daß dabei die Lösungsmenge nicht verändert wird, zeigt der folgende (schon bekannte, aber jetzt einfacher zu beweisende) Satz:

\underline{(B.5) SATZ:} Seien A ∈ M_{m,n}(K) und b ∈ K^{m}.

a) Für jede invertierbare Matrix P ∈ GL_{m}(K) haben die beiden linearen Gleichungssysteme

(⋆) A · x = b und (⋆⋆) (P · A) · x = P · b

dieselbe Lösungsmenge.

b) Die Lösungsmenge des linearen Gleichungssystems (⋆) A · x = b ändert sich nicht bei elementaren Zeilenumformungen der erweiterten Koeffizientenmatrix (A, b).

\underline{Bew:} a) Lös(A, b) ⊆ Lös(P A, P b) ist klar. Für den Nachweis der umgekehrten Inklusion multipliziere (⋆⋆) von links mit P^{−1} .

b) Die Ausführung einer elementaren Zeilenumformung auf (A, b) entspricht einer Linksmultiplikation von (⋆) mit einer Elementarmatrix G ∈ GL_{m}(K). Nach a) ändert sich dabei nicht die Lösungsmenge. □