Diese Aufgabenstellung haben wir bereits besprochen, siehe Satz 6.22.

Eine äquivalente Formulierung des Problems ist, eine Basis vom Kern \(\operatorname{Ker}(A)\) einer Matrix \(A\) zu bestimmen, denn \(\operatorname{Ker}(A)\) ist genau die Lösungsmenge des homogenen Gleichungssystems \(Ax=0\).

Sei \(U\subseteq K^m\) ein Untervektorraum und sei \(u_1, \dots , u_n\in U\) ein Erzeugendensystem von \(U\). Wir wissen, dass es eine Basis von \(U\) gibt, die aus Vektoren dieses Erzeugendensystems besteht. Um eine solche zu finden, betrachten wir die Matrix \(A\in M_{m\times n}\), deren \(j\)-te Spalte der Spaltenvektoren \(u_j\in K^m\) ist. Sei \(B\) eine Matrix in Zeilenstufenform, die aus \(A\) durch elementare Zeilenumformungen entsteht. Dann bilden die \(u_j\) für diejenigen Indizes \(j\), die in \(B\) zu einer Spalte mit einer führenden Eins korrespondieren, eine Basis von \(U\).

Begründung des Verfahrens. Sind \(s_1, \dots , s_n\in K^m\) die Spalten einer Matrix \(S\), geht die Matrix \(S^\prime \) mit den Spalten \(s_1^\prime , \dots , s_n^\prime \) aus \(S\) durch elementare Zeilenumformungen hervor und sind \(c_j\in K\), so gilt \(\sum _{j=1}^n c_j s_j=0\) genau dann, wenn \(\sum _{j=1}^n c_js_j^\prime = 0\). Das ist für alle drei Typen von elementaren Zeilenumformungen leicht einzusehen.

Das bedeutet, dass für eine Teilmenge \(J\subseteq \{ 1,\dots n\} \) die Spalten \(s_j\), \(j\in J\), genau dann linear unabhängig sind, wenn es \(s_j^\prime \), \(j\in J\) sind.

Eine Basis innerhalb des gegebenen Erzeugendensystems ist eine maximale linear unabhängige Teilmenge darin. Für eine Matrix in Zeilenstufenform ist klar, dass die Spalten mit führenden Einsen eine solche maximale linear unabhängige Teilmenge bilden.

Eine äquivalente Formulierung des Problems ist, eine Basis vom Bild einer Matrix \(A\) zu bestimmen, denn das Bild von \(A\) ist genau der von den Spalten von \(A\) erzeugte Untervektorraum.

In ähnlicher Weise kann man eine linear unabhängige Teilmenge \(L\) in einem Untervektorraum \(U\subseteq K^m\) zu einer Basis ergänzen, wenn man irgendein Erzeugendensystem \(E\) von \(U\) kennt. Denn dann ist \(L\cup E\) auch ein Erzeugendensystem, auf das man das Verfahren des vorherigen Abschnitts anwenden kann. Wenn man die Elemente von \(L\) als die linken Spalten der Matrix \(A\) schreibt, führt die lineare Unabhängigkeit dazu, dass diese Spalten in der Zeilenstufenform jedenfalls führende Einsen enthalten werden. An den zusätzlich auftretenden führenden Einsen kann man ablesen, welche Elemente von \(E\) man noch hinzunehmen kann, um eine Basis zu erhalten.

Seien \(U, W\subseteq K^m\) Untervektorräume mit Basen \(u_1, \dots , u_r\) und \(w_1, \dots , w_s\). Wir wollen Basen von \(U+W\) und \(U\cap W\) finden.

Da \(u_1,\dots , u_r, w_1, \dots , w_s\) die Summe \(U+W\) erzeugen, können wir das vorher besprochene Verfahren anwenden, um innerhalb dieses Erzeugendensystems eine Basis von \(U+W\) zu finden.

Um eine Basis von \(U\cap W\) zu finden, verfahren wir folgendermaßen. Ein Element \(v \in K^m\) liegt genau dann in \(U\cap W\), wenn es sowohl als Linearkombination der \(u_j\), als auch als Linearkombination der \(w_j\) darstellbar ist, wenn also \(a_j\) und \(b_j\) existieren mit

Um alle Elemente von \(U\cap W\) zu finden, müssen wir also alle Tupel \((a_1, \dots , a_r, b_1, \dots , b_s)\) finden mit

oder mit anderen Worten die Lösungsmenge des linearen Gleichungssystems \(Ax = 0\), wo \(A\) die Matrix mit Spalten \(u_1,\dots , u_r, -w_1, \dots , -w_s\) ist. Ist \((x_j)_j\in K^{r+s}\) ein Element der Lösungsmenge, so ist \(\sum _{j=1}^r x_j u_j = \sum _{j=r+1}^{r+s} x_j w_j\in U\cap W\). Wir bezeichnen für den Moment für \(x = (x_j)_j\in K^{r+s}\) mit \(\overline{x}\) den Vektor \(\sum _{j=1}^r x_j u_j\). Bilden dann \(v_1,\dots , v_t\) eine Basis der Lösungsmenge, so ist \(\overline{v_1}, \dots , \overline{v_t}\) ein Erzeugendensystem von \(U\cap W\), und sogar eine Basis, wie wir gleich begründen werden.

Zunächst die folgende Bemerkung: Weil mit \(w_1, \dots , w_s\) auch \(-w_1, \dots , -w_s\) eine Basis ist, kann man auch die beiden Verfahren in einem Schritt durchführen und aus der Zeilenstufenform der Matrix \(A\) mit Spalten \(u_1,\dots , u_r, -w_1, \dots , -w_s\) eine Basis von \(U+W\) ablesen.

Insbesondere folgt, dass die Anzahl der führenden Einsen in der Zeilenstufenform von \(A\) genau \(\dim (U+W)\) ist. Die Dimension \(t\) der Lösungsmenge ist also \(r+s - \dim (U+W) = \dim (U)+\dim (W) - \dim (U+W) = \dim (U\cap W)\), siehe Satz 6.46. Weil das Erzeugendensystem \(\overline{v_1}, \dots , \overline{v_t}\) von \(U\cap W\), das wir oben gefunden haben, genau \(\dim (U\cap W)\) Elemente hat, handelt es sich um eine Basis. (Man kann sich die lineare Unabhängigkeit auch direkt überlegen, ohne die Dimensionsformel für den Durchschnitt von Untervektorräumen zu benutzen. Sehen Sie, wie?)

Seien \(K\) ein Körper, \(V\) ein \(K\)-Vektorraum und seien \(u_1, \dots , u_n\in V\). Wir setzen \(U:= \langle u_1, \dots , u_n\rangle \), so dass \(\{ u_1, \dots , u_n\} \) ein Erzeugendensystem des Untervektorraums \(U\) ist. Es gibt aber in aller Regel viele andere Erzeugendensysteme. Ist die Familie \(u_1, \dots , u_n\) nicht linear unabhängig, so können wir sie geeignet verkleinern, ohne ihr Erzeugnis zu ändern. Wir können auch den Austauschsatz auf den Vektorraum \(U\) anwenden.

Hier wollen wir besprechen, wie wir wir das gegebene Erzeugendensystem durch direkte Umformungen abändern können, ohne die lineare Hülle zu verändern. Sind \(1\le i,j\le n\), \(i\ne j\) und \(a\in K\), so gilt

Ist \(1\le i\le n\) und \(a\in K^\times \), so gilt

Beide Behauptungen prüft man unmittelbar nach, indem man zeigt, dass jeweils die linke Seite in der rechten enthalten ist, und umgekehrt.

Sei nun \(V=K^m\), und \(u_1, \dots , u_n\in K^m\). Sei \(A\in M_{m\times n}(K)\) die Matrix mit den Spalten \(u_1,\dots , u_n\). Dann können wir, ähnlich wie wir in Abschnitt 5.2.1 elementare Zeilenumformungen definiert haben, elementare Spaltenumformungen betrachten: (I) Addieren eines Vielfachen einer Spalte zu einer anderen Spalte, (II) Vertauschen zweier Spalten, (III) Multiplizieren einer Spalte mit \(a\in K^\times \). Die Überlegungen des vorherigen Absatzes können wir dann formulieren als

Das ermöglicht es, durch Spaltenumformungen eine besonders einfache Basis eines Untervektorraums von \(K^m\) zu finden, der durch ein Ezeugendensystem gegeben ist: Analog zum gewöhnlichen Gauß-Algorithmus kann man eine Matrix durch elementare Spaltenumformungen auch »reduzierte Spaltenstufenform« bringen. (Wir können definieren, dass eine Matrix \(A\) reduzierte Spaltenstufenform hat, wenn die transponierte Matrix \(A^t\) reduzierte Zeilenstufenform hat.)

Machen Sie sich die Unterschiede zwischen Zeilen- und Spaltenumformungen klar: Spaltenumformungen verändern nicht den Untervektorraum, der von den Spaltenvektoren erzeugt wird; schon allein, weil beliebige Spaltenvertauschungen erlaubt sind, ist aber klar, dass man keine Rückschlüsse der Art ziehen kann, welche der ursprünglich gegebenen Vektoren linear unabhängig, ein Erzeugendensystem oder eine Basis sind. Bei Zeilenumformungen bleibt hingegen die Information, ob eine Spalte eine Linearkombination von anderen Spalten ist, erhalten; es verändert sich aber der Untervektorraum, der von den Spalten erzeugt wird.