Inhalt

6.5 Wie berechne ich …?

Ich habe etwas gezögert, ob es überhaupt sinnvoll ist, diesen Abschnitt ins Skript aufzunehmen, denn gerade für diese »Rechenverfahren« gilt: Es ist besser, wenn Sie sich selbst überlegen, wie Sie die uns zur Verfügung stehenden Verfahren (und das ist im Moment eigentlich nur der Gauß-Algorithmus) auf die zu bewältigende Aufgabe anwenden. Insbesondere rate ich davon ab, die Varianten, die unten diskutiert werden, auswendig zu lernen. Letztlich habe ich mich aber doch entschieden, einige Aufgabentypen hier zu sammeln, auch um illustrieren zu können, dass es am Ende von Kapitel 7 möglich sein wird, einiges noch klarer darzustellen. Konkrete Beispiele zu diesen Aufgabentypen finden Sie in den Online-Aufgaben.

Sei $K$ ein Körper. Um Basen von Untervektorräumen in $K^n$, $n\in \mathbb N$, zu berechnen und damit zusammenhängende Fragen über Untervektorräume zu beantworten, erweist sich der Gauß-Algorithmus als Universalwerkzeug.

Wir haben bereits erwähnt, dass die Spalten einer Matrix $A\in M_{m\times n}(K)$ genau dann eine linear unabhängige Familie in $K^m$ bilden, wenn das homogene Gleichungssystem $Ax=0$ eindeutig lösbar ist, also nur die triviale Lösung besitzt. Ein Vektor $b\in K^m$ liegt genau dann im Untervektorraum von $K^m$, der von den Spalten von $A$ erzeugt wird, wenn das Gleichungssystem $Ax=b$ lösbar ist. Die Spalten von $A$ bilden genau dann eine Basis von $K^m$, wenn das lineare Gleichungssystem $Ax=b$ für alle $b$ eindeutig lösbar ist. Das ist nur dann möglich, wenn $m=n$ ist, d.h. wenn $A$ quadratisch ist; es ist dann äquivalent dazu, dass die Matrix reduzierte Zeilenstufenform $E_n$ hat, und auch dazu, dass $A$ invertierbar ist. Siehe Korollar 5.22 und Satz 5.54.

6.5.1 Basis der Lösungsmenge eines homogenen linearen Gleichungssystems

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$.

6.5.2 Eine Basis innerhalb eines gegebenen Erzeugendensystems

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.

6.5.3 Eine linear unabhängige Teilmenge zu einer Basis ergänzen

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.

6.5.4 Eine Basis vom Durchschnitt und der Summe von Untervektorräumen

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

\[ a_1 u_1 + \cdots + a_r u_r = v = b_1 w_1 + \cdots + b_sw_s. \]

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

\[ a_1 u_1 + \cdots + a_r u_r - b_1 w_1 - \cdots - b_sw_s = 0, \]

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?)

6.5.5 Eine möglichst einfache Basis eines Untervektorraums finden – Spaltenumformungen

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

\[ \langle u_1,\dots , u_n\rangle = \langle u_1,\dots , u_{i-1}, u_i+au_j, u_{i+1}, \dots , u_n\rangle . \]

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

\[ \langle u_1,\dots , u_n\rangle = \langle u_1,\dots , u_{i-1}, au_i, u_{i+1}, \dots , u_n\rangle . \]

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

Lemma 6.50

Sei $A\in M_{m\times n}(K)$ eine Matrix, und sei $A^\prime $ eine Matrix, die aus $A$ durch elementare Spaltenumformungen entsteht. Sei $U\subseteq K^m$ der Untervektorraum, der von den Spalten von $A$ erzeugt wird, und sei $U^\prime \subseteq K^m$ der Untervektorraum, der von den Spalten von $A^\prime $ erzeugt wird. Dann gilt $U=U^\prime $.

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.