11 Gleichungssysteme

Eine der Hauptaufgaben die an Mathematiker gestellt werden ist das Lösen von Gleichungen, wie z.B.

$$a+x = b$$

$$a\cdot x = b$$

$$a_0+a_1\, x+\dots+a_n\,x^n = b$$

$$a_0\,x_0+a_1\,x_1+\dots+a_n\,x_n = b$$
oder allgemein

$$f(x) = b f.$$

Üblicherweise sind dabei die Variablen $x$, $x_0$,..., $x_n$ Zahlen, manchmal aber auch durchaus komplizierteres wie z.B. Vektoren, Matrizen oder sogar Abbildungen. Im letzteren Fall ist man insbesonders an der Lösung von Differentialgleichungen wie z.B.

$$x'(t) = f(t,x(t))$$

interessiert.

Wir haben bislang Gleichungen der ersten 3 Arten behandeln. Nun wenden wir uns solchen der 4.ten Art, sogenannten linearen Gleichungen zu.

11.1 Beispiele.

1. Zwei Züge fahren mit jeweils konstanter Geschwindigkeit aufeinander zu. Und zwar sei der erste Zug um 9h im Ort $A$ gestartet und bewege sich mit 80 km/h auf den zweiten Zug zu, welcher um 10h im 480km entfernten Ort $B$ gestartet ist und sich mit 120 km/h bewegt.
   Zu welchen Zeitpunkt und an welchen Ort werden sich die beiden Züge begegnen?

   Um dieses Problem anzugehen, müssen wir uns aus der Physik in Erinnerung rufen, daß der bei konstanter Geschwindigkeit $v$ in der Zeit $t$ zurückgelegte Weg gerade $v\cdot t$ ist. Wir können beide Züge in ein Zeit-Weg Diagramm einzeichnen. D.h. wir tragen auf der horizontalen Achse die Zeit $t$ (bei 9h beginnend) und auf der vertikalen Achse den Abstand von $A$ auf.

   
   

   

   Zeit und Ort des Treffpunkts können wir dann geometrisch aus den Koordinaten des Schnittpunktes der beiden Geraden ablesen.

   Natürlich können wir das auch präzise durchrechnen. Der Abstand des 1. Zuges von $A$ zum Zeitpunkt $t$ ist $s_1(t):=80\cdot(t-9)$ und jeder des 2. Zuges von $A$ zum Zeitpunkt $t$ ist $s_2(t):=480-120\cdot(t-10)$. Also ist das Gleichungssystem

   $$s = 80\cdot (t-9)$$

   $$s = 480 -120\cdot(t-10)$$

   
   
   zu lösen, d.h. $80\,t-720=480-120\,t+1200$ und somit ist $t =\frac{2400}{200}=12$ und $s=80\cdot 3=240$.

2. Ein anderes Beispiel aus der Ökonomie. Ein Betrieb kann 3 verschiedene Produkte $A$, $B$ und $C$ herstellen. Für $A$ wird eine Arbeitsstunde, für $B$ zwei und für $C$ drei pro erzeugten Stück benötigt. Die Produkte werden zum Preis von $30$, $50$ und $70$ Euro verkauft. Der Energieverbrauch pro Stück liegt bei $5$, $3$ und $2$ kWh pro erzeugten Stück. Es werden in 40 Arbeitsstunden Produkte im Wert von $1040$ Euro produziert bei einen Energieverbrauch von $93$ kWh.
   Wieviel Stück des jeweiligen Produkte wurden erzeugt?

   Wir nennen die jeweiligen Stückzahlen $x$, $y$ und $z$. Dann läßt sich die Angabe durch folgende 3 Gleichungen beschreiben

   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcr} 1 x & + & 2 y ... ... & 50 y & + & 70 z & = & 1040 \\ 5 x & + & 3 y & + & 2 z & = & 93 \end{array}$$
   Ohne die Lösungen zu ändern können wir offensichtlich folgende Umformungen (die sogenannten elementaren Zeilenumformungen) vornehmen:
   1. Eine Zeile mit einem Faktor ungleich 0 multiplizieren;
   2. Zwei Zeilen miteinander vertauschen;
   3. Von einer Zeile (ein Vielfaches) eine(r) andere(n) Zeile abziehen.
   Wir benutzen dies nun dazu, um das Gleichungssystem in die Form
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcr} x & & & & & = & b_1 \\ & & y & & & = & b_2 \\ & & & & z & = & b_3 \end{array}$$
   zu bekommen, aus der wir die Lösungen $x=b_1$, $y=b_2$, $z=b_3$ unmittelbar ablesen können. Zuerst verwenden wir (b) und multiplizieren die 2.te Zeile $II$ mit $1/10$ und erhalten
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcr} 1 x & + & 2 y ... ...& + & 5 y & + & 7 z & = & 104 \\ 5 x & + & 3 y & + & 2 z & = & 93 \end{array}$$
   Nun verwenden wir (c) und bilden $II\leftarrow II-3\cdot I$ sowie $III\leftarrow III-5\cdot I$ und erhalten
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcr} x & + & 2 y & ... ...\ & - & y & - & 2 z & = & -16 \\ & - & 7 y & - & 13 z & = & -107 \end{array}$$
   Wir bilden $II\leftarrow (-1)\cdot II$ und bilden $III\leftarrow III+7\cdot II$:
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcr} x & + & 2 y & ... ...3 z & = & 40 \\ & & y & + & 2 z & = & 16 \\ & & & & z & = & 5 \\ \end{array}$$
   Nun bilden wir $II\leftarrow II-2\cdot III$:
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcr} x & + & 2 y & + & 3 z & = & 40 \\ & & y & & & = & 6 \\ & & & & z & = & 5 \\ \end{array}$$
   Und schließlich $I\leftarrow I-2\cdot I -3\cdot III$:
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcr} x & & & & & = & 13 \\ & & y & & & = & 6 \\ & & & & z & = & 5 \\ \end{array}$$
   und erhalten für die Stückzahlen $x=13$, $y=6$ und $z=5$.

   Beispiel. Ein vorläufig letztes Beispiel aus der Chemie. Um den Sprengstoff Trinitrotoluol (TNT) $C_7H_5O_6N_3$ zu gewinnen wird Methylbenzol (Toluol) $C_7H_8$ und Salpetersäure $HNO_3$ gemischt und man erhält Wasser $H_2O$ und $TNT$.
   In welchen Mengen reagieren nun die involvierten Substanzen?

   Wenn $x$, $y$, $z$ und $w$ die Molekülanzahlen der an der Reaktion

   $$x\,C_7H_8 + y\, HNO_3 \to z\, C_7H_5O_6N_3 + w\,H_20$$
   beteiligten Stoffe bezeichnet, so müssen folgende Beziehungen gelten

   $$C: \qquad x\,7=z\,7$$

   $$H: \qquad x\,8+y=z\,5+w\,2$$

   $$N: \qquad y=z\,3$$

   $$O: \qquad y\,3=z\,6+w$$

   
   
   Aus der 1. Gleichung folgt $x=z$, die 3. besagt $y=3z$ und eingesetzt in die 2. oder 4. liefert $8z+3z=5z+2w$ bzw. $9z=6z+w$ also $w=3z$. Wir sehen allerdings, daß keine eindeutige Lösung sondern unendlich viele dieses Gleichungssystems mit 4 Variablen $x$, $y$, $z$, $w$ und $4$ Gleichungen existieren. Um eine gewünschte Menge $z$ der Salpetersäure zu erhalten können wir nun die dafür nötigen Mengen $x$ von Toluol und $y$ der Salpetersäure sowie die dabei anfallende Menge $w$ des Wassers bestimmen.

   Das oben beschriebene Verfahren liefert in diesen Fall:

   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcrcr} 7 x & & & - ... ... & & y & - & 3 z & & & = & 0 \\ & & 3 y & - & 6 z & - & w & = & 0 \end{array}$$
   $I\leftarrow \frac17\cdot I$, $II\leftarrow II-8\cdot I$
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcrcr} x & & & - & ... ... & & y & - & 3 z & & & = & 0 \\ & & 3 y & - & 6 z & - & w & = & 0 \end{array}$$
   $III\leftarrow III-II$, $IV\leftarrow IV-3\cdot II$
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcrcr} x & & & - & ... ... & & - & 6 z & + & 2 w & = & 0 \\ & & & - & 15 z & + & 5 w & = & 0 \end{array}$$
   $III\leftarrow \frac{-1}{6}\cdot III$, $IV\leftarrow IV-15\cdot III$
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcrcr} x & & & - & ... ... & & & & z & - & \frac13 w & = & 0 \\ & & & & & & 0 w & = & 0 \\ \end{array}$$
   Und weiter $II\leftarrow II-3\cdot III$ und $I\leftarrow I+III$
   $$\setlength\arraycolsep{2pt} \begin{array}{rcrcrcrcr} x & & & & & ... ... & & & & z & - & \frac13 w & = & 0 \\ & & & & & & 0 w & = & 0 \\ \end{array}$$
   Das Verfahren liefert also nicht lauter 1'er in der Diagonale, sondern an der letzten Stelle einen 0-er.

11.2 Geometrische Interpretation.
Wir wollen nun ein (geometrisches) Verständnis für solche eventuell unendliche Lösungsmengen $L\subseteq \mathbb{K}^n$ linearer Gleichungen entwickeln. Die Koeffizienten $a_{i,j}$ der Gleichungen bilden eine Matrix $(a_{i,j})_{1\leq i\leq m,\,1\leq j\leq n}$, die wir als lineare Abbildung $A:\mathbb{K}^n\to\mathbb{K}^m$ auffassen können. Die Inhomogenitätsterme $b_i$ bilden einen Vektor $(b_1,\dots,b_m)\in\mathbb{K}^m$ und Lösungen $(x_1,\dots,x_m)$ des linearen Gleichungssystems sind gerade Punkte $x=(x_1,\dots,x_m)$ mit $A(x)=b$, beschreiben also einen affinen Teilraum von $\mathbb{K}^n$ den man dadurch erhält, daß man zur einer Lösung des inhomogenen Gleichungssystems alle Lösungen $y$ des zugehörigen homogenen Systems $A(y)=0$, d.h. den $\operatorname{Ker}(A)$ hinzuaddiert. Falls $A$ surjektiv oder zumindest $b$ im Bild von $A$ liegt so existiert mindestens eine Lösung $x$ von $A(x)=b$. Ist $A$ injektiv so ist die Lösung eindeutig bestimmt. Ist $A$ bijektiv, so existiert für jedes $b\in\mathbb{K}^m$ eine eindeutig bestimmte Lösung $x\in \mathbb{K}^n$ und diese kannals $x=A^{-1}(b)$ berechnet werden.

Es sei $A:V\to W$ linear. Dann nennt man eine Gleichung der Form $A(x)=0$ eine homogene lineare Gleichung und eine solche der Form $A(x)=y$ mit gegebenen $y$ eine inhomogene lineare (oder auch affine) Gleichung.

Als Resumeé haben wir also:

Proposition.
Die Gesamtheit der Lösungen eines homogenen linearen Gleichungssystems bilden einen Vektorraum, einen Teilvektorraum von $\mathbb{R}^n$.    []

Sowie:

Proposition.
Die allgemeine Lösung einer inhomogenen linearen Gleichung wird dadurch beschrieben, daß man zu einer (speziellen) Lösung der inhomogenen Gleichung alle Lösungen der entsprechenden homogenen Gleichung hinzuaddiert.    []

Man rufe sich in diesen Zusammenhang die geometrische Interpretation einer Gleichung $a_1\,x_1+a_2\,x_2+a_3\,x_3=b$ mit Koeffizienten $a_1,\dots,a_n,b\in\mathbb{R}$ in Erinnerung. Dies beschreibt (im Fall $(a_1,\dots,a_n)\ne 0$) bekanntlich eine Ebene im Raum, und mehrere solche Gleichungen, die gleichzeitig erfüllt sein sollen, denn Durchschnitt der entsprechenden Ebenen, also je nach Anzahl und Lage eine Ebene, eine Gerade, einen Punkt oder die leere Menge. Obige Parameterdarstellung der Lösungen des Gleichungssystems nach Gauß entspricht dabei gerade der Bestimmung einer Parameterdarstellung dieser Schnittmenge.

11.3 Proposition.
Sei $A:V\to W$ linear und $y\in W$ fix. Dann besitzt die Gleichung $A(x)=y$ genau dann eine Lösung $x_0$, wenn $y\in A(V)$ liegt. Die Menge aller Lösungen ist dann durch $x_0+\operatorname{Ker}(A)$ gegeben, ist also ein affiner Teilraum der Dimension $\dim(\operatorname{Ker}(A))=\dim(V)-\operatorname{Rang}(A)$. Die Lösungen von $A(x)=y$ sind dann durch $x=x_0+\sum_{j=1}^k \lambda _k v_k$ gegeben, wobei die $v_k$ eine Basis von $\operatorname{Ker}(A)$ seien.

11.4 Gauß'sches Eliminationsverfahren.
Wenn wir ein allgemeines inhomogenes lineares Gleichungssystem in $n$ vielen Variablen $x_1$, $\dots$, $x_n$ und $m$ vielen Gleichungen der Form

$$\setlength\arraycolsep{2pt} \begin{array}{... ...\ a_{m,1}\,x_1 & + & \dots & + & a_{m,n}\,x_n & = & b_m \\ \end{array}$$

mit fixen Eintragungen $a_{1,1},\dots,a_{m,n}$ (Beachte, daß der 1. Index $i$ in $a_{i,j}$ die Zeilennummer und der 2. Index $j$ die Spaltennummer der Eintragung $a_{i,j}$ angibt.) sowie $b_1,\dots,b_m$ vorliegen haben, so können wir dieses schrittweise unter Beibehaltung der Lösungen wie folgt umformen. Wunschziel dabei wäre eine Diagonalgestalt der Form

$$\setlength\arraycolsep{2pt} \begin{array}{... ...\ddots & & & \vdots\; & \vdots \\ & & & & x_n & = & c_m \\ \end{array}$$

zu erreichen. Dies ist im Falle $n\ne m$ nicht, und, wie das chemische Beispiel zeigt, selbst für $n=m$ nicht immer möglich. Aber folgendes können wir zumindest tun:

Falls die erste Spalte aus lauter Nullen besteht so machen wir im ersten Schritt nichts. Andernfalls wählen wir eine Zeile $i$ deren erster Koeffizienten $a_{i,1}\ne 0$ ist, multiplizieren diese mit $1/a_{i,1}$ um als ersten Koeffizienten 1 zu erhalten, und tauschen sie an die 1. Stelle. Sodann ziehen wir von allen übrigen Zeilen $j$ das entsprechende Vielfache $a_{j,1}$ der ersten Zeile ab um alle anderen Koeffizienten der 1. Spalte in 0'en zu verwandeln.

Im nächsten Schritt verfahren wir ebenso mit der 2. Spalte fort, wobei wir allerdings die 1. Zeile unverändert stehen lassen und nur die Zeilen 2 bis $m$ weiter umformen, falls wir bei ihr im vorangegangenen Schritt schon einen 1'er als ersten Koeffizienten erreicht haben.

Diese Schritte führen wir solange durch, bis keine Zeilen oder keine Spalten (bis auf die letzte) mehr übrig sind, wobei wir jeweils jene Zeilen, in denen wir schon einen führenden 1'er erreicht haben unverändert abschreiben. Wenn wir jene Spalten, wo wir einen 1'er erzeugen konnten, weil sie an den relevanten Stellen nicht aus lauter 0'er bestanden haben, mit $1\leq j_1<j_2<\dots<j_r$ bezeichnen, so haben wir eine Form erreicht, wo $a_{i,j_i}=1$ für $1\leq i\leq r$ und alle anderen Eintragungen im Teil-Rechteck, dessen rechte obere Ecke $a_{i,j_i}$ ist, 0 sind. Anders formuliert, die Spalten-Nummern $j_i$ der führenden 1'er in der $i$-ten Zeile sind streng monoton wachsend. Durch Abziehen entsprechender Vielfachen von den darüberstehenden Zeilen können wir weiters erreichen, daß in der Spalte über $a_{i,j_i}=1$ ebenfalls lauter 0'er sind.

$$\setlength\arraycolsep{2pt} \begin{array}{... ...\hdots &\hdots &\hdots &0 &\hdots &\hdots &0 &\boxed{c_m}\\ \end{array}$$

Für die Lösung bedeutet dies nun, daß falls die letzten $m-r$ Gleichungen nicht widersprüchlich sind (d.h. $c_{r+1}=\dots=c_{m}=0$ ist), so können die $n-r$ Variablen der übrigen Spalten $x_j$ mit $j\ne j_1,\dots,j_r$ frei gewählt werden und die anderen $r$ Variablen $x_{j_1},\dots,x_{j_r}$ daraus eindeutig berechnet werden.

Diese Methode zur Bestimmung der Lösungen eines linearen Gleichungssystems nennt man Gauß'sches Eliminationsverfahren.

11.5 Proposition.
Elementare Zeilenumformungen einer $n\times m$-Matrix über einem Körper $\mathbb{K}$ lassen sich durch Multiplikation von links mit einer invertierbaren $m\times m$-Matrix ausdrücken. Wendet man also auf die erweiterte Matrix eines linearen Gleichungssystems eine beliebige Abfolge von elementaren Zeilenoperationen an, so erhält man die erweiterte Matrix eines äquivalenten Systems.

Beweis. Es sei $\pi$ eine Permutation der Menge $m=\{0,\dots,m-1\}$, also eine bijektive Abbildung $\pi:m\to m$. Dies induziert eine lineare Abbildung $f:=\pi^*:\mathbb{K}^m\to\mathbb{K}^m$ definiert durch $\pi^*(x)=(x_{\pi(i)})_{0\leq i<m}$, also mit $\pi^*(e_i)=e_{\pi^{-1}(i)}$. Diese ist offensichtlich ein Isomorphismus mit Inverser $(\pi^{-1})^*$. Ist insbesonders $\pi$ eine Transposition, so ist $\pi^{-1}=\pi$ und $\pi^*$ vertauscht gerade 2 der Basisvektoren $e_i$. Es ist

$$(\pi^*\o A)(e_j)=\pi^*(A(e_j))=\sum_{k} a_{k,j}\pi^*(e_k)= \sum_k a_{k,j} e_{\pi^{-1}(k)}=\sum_i a_{\pi(i),j} e_i$$

Also erhält man die Matrix $[f\o A]$ aus $[A]$ indem man die Zeilen entsprechend $\pi$ miteinander vertauscht.

Multiplikation der $i$-ten Zeile von $[A]$ mit den Skalar $\lambda$ läßt sich durch Multiplikation von links mit der Matrix, die auf der Diagonale lauter 1'er hat bis auf die $i$-te Stelle wo $\lambda$ und sonst lauter 0'er als Eintragungen hat. Die zugehörige bijektive lineare Abbildung $f$ wird durch

$$e_j\mapsto \begin{cases}e_j&\text{für }j\ne i \\ \lambda \,e_j &\text{für }j=i \end{cases}$$

beschrieben.

Sei schließlich $\lambda \in\mathbb{K}$ und $0\leq i,j< m$ mit $i\neq j$ beliebig. Nach (10.7) gibt es eine eindeutige lineare Abbildung $f:\mathbb{K}^m\to\mathbb{K}^m$, die $f(e_j)=e_j+\lambda e_i$ und $f(e_k)=e_k$ für $k\neq j$ erfüllt. Für $x=(x_0,\dots,x_{m-1})\in\Bbb K^m$ gilt dann

$$f(x)=f\Bigl(\sum x_ke_k\Bigr)=\sum_{k\neq j}x_ke_k+x_je_j+\lambda x_je_i=\sum_{k\neq i}x_ke_k+(x_i+\lambda x_j)e_i.$$

Die Spalten von $[f\o A]$ erhält man indem man $f$ auf die Spalten von $[A]$ anwendet. Das bedeutet aber, das Linksmultiplikation mit $[f]$ genau die Zeilenoperation $i\mapsto i+\lambda \cdot j$ liefert. Wir müssen also nur noch sehen, daß $[f]$ invertierbar, also $f$ ein linearer Isomorphismus ist. Sei dazu $g$ die analoge Abbildung mit $-\lambda$ statt $\lambda$. Nach Definition bildet sowohl $g\o f$ als auch $f\o g$ jedes $e_k$ auf sich selbst ab. Da eine lineare Abbildung durch ihre Werte auf einer Basis eindeutig bestimmt ist, folgt daraus $g\o f=f\o g=\operatorname{id}$, also ist $f$ ein linearer Isomorphismus.

    []

Bemerkung.
Natürlich spielt es eine Rolle, in welcher Reihenfolge elementare Zeilenoperationen durchgeführt werden. Zum Beispiel erhält man natürlich ein anderes Ergebnis, wenn man erst $i\leftrightarrow j$ und dann $i\mapsto \lambda \cdot i$ anwendet, als wenn man erst $i\mapsto \lambda \cdot i$ und dann $i\leftrightarrow j$ anwendet. Bei Zeilenoperationen, die keine gemeinsamen Zeilen betreffen spielt die Reihenfolge aber keine Rolle, und wir werden diese Operationen oft in einem Schritt durchführen um nicht allzu viel aufschreiben zu müssen. So kann man etwa für fixes $j$ und verschiedene $i_1,\dots,i_k$, die auch alle ungleich $j$ sind, die Operationen $i_1\mapsto i_1+\lambda _1\cdot i$ bis $i_k\mapsto i_k+\lambda _k\cdot i$ gleichzeitig durchführen.

11.6 Invertierbarkeit und Bestimmung der inversen Matrix.
In diesem Abschnitt betrachten wir eine $n\times n$-Matrix $A$ über einem Körper $\mathbb{K}$. Wir wollen ein explizites Verfahren entwickeln, das entscheidet, ob die Matrix $A$ invertierbar ist, und falls ja, die inverse Matrix $A^{-1}$ explizit bestimmen. Sind $A$ und $S$ invertierbare $n\times n$-Matrizen, dann ist $SA$ invertierbar (und $(SA)^{-1}=A^{-1}S^{-1}$) nach Satz (2.5). Ist umgekehrt für eine invertierbare Matrix $S$ die Matrix $SA$ invertierbar, dann ist $A=S^{-1}SA$ ebenfalls invertierbar. Insbesondere ändern elementare Zeilenoperationen nichts an der Invertierbarkeit einer Matrix, denn diese lassen sich nach (11.5) durch Multiplikation von links mit einer invertierbaren Matrix $S$ beschreiben. Wenn wir also wissen wollen, ob eine Matrix $A$ invertierbar ist, dann können wir $A$ mit Hilfe des Gauß'schen Algorithmus auf Zeilenstufenform bringen und überprüfen, ob die resultierende Matrix invertierbar ist. Das ist relativ einfach, und es liefert sogar einen Algorithmus zur Berechnung der inversen Matrix:

11.7 Theorem.
Ist $A$ eine beliebige invertierbare $n\times n$-Matrix über einem Körper $\mathbb{K}$, dann kann man $A$ durch eine endliche Folge von elementaren Zeilenoperationen in die Einheitsmatrix $\Bbb I$ umwandeln. Man erhält die inverse Matrix $A^{-1}$ indem man die dazu nötigen Zeilenoperationen in der selben Reihenfolge auf die Einheitsmatrix $\Bbb I$ anwendet.

Beweis. Sei $A\in L_\mathbb{K}(n,n)$ invertierbar. Die Inverse $B:=A^{-1}$ ist nach (10.7) durch ihre Werte $b_j:=A^{-1}(e_j)$ auf der Standard-Basis $\{e_1,\dots,e_n\}$ eindeutig festgelegt. Wir müssen also die Gleichungen $A(b_j)=e_j$ lösen. Dies geschieht durch Anwendung des Gauß'schen Algorithmus auf die erweiterte Matrix $(A,e_j)$ und wir erhalten $(\operatorname{id},b_j)$. Wenden wir dies gleichzeitig für alle Basis-Vektoren $e_1,\dots,e_n$ als auf $(A,\operatorname{id})=(A,e_1,\dots,e_n)$ an so erhalten wir $(\operatorname{id},B)=(\operatorname{id},b_1,\dots,b_n)$ und somit die Matrix $B$ der Inversen zu $A$.     []

Bemerkung.

1. Der obige Satz liefert uns einen einfachen Algorithmus, der entscheidet, ob eine $n\times n$-Matrix $A$ invertierbar ist und im Fall der Invertierbarkeit sofort die inverse Matrix berechnet. Man bildet einfach die $2n\times n$-Matrix $(A\vert\Bbb I)$ die als erste $n$-Spalten $A$ und als zweite $n$-Spalten $\Bbb I$ hat. Dann wendet man den Gauß'schen Algorithmus an um diese Matrix auf Zeilenstufenform zu bringen. Führt das zu $r=n$ und $j_i=i$ für alle $i=1,\dots,n$, dann ist $A$ invertierbar. Die resultierende Matrix ist dann gerade $(\Bbb I\vert A^{-1})$.
2. Sowohl der Gauß'sche Algorithmus als auch das hier beschriebene Verfahren zur Bestimmung der inversen Matrix können natürlich leicht einem Computer beigebracht werden (sofern der Computer bereits im Körper $\mathbb{K}$ rechnen kann, was aber meist nicht allzu schwierig ist). Für allgemeine Matrizen sind diese Verfahren sogar ziemlich effizient. Weiß man mehr über das Gleichungssystem (etwa das sehr viele Koeffizienten gleich Null sind - ``dünn besetzte Systeme'') dann gibt es schnellere Verfahren zur Lösung solcher Systeme.

Beispiele.

1. Für die $2\times 2$-Matrix aus (10.28a)
   $$\begin{pmatrix} \sqrt{2} & \frac1{\sqrt{2}} \\ 0 & \frac{\sqrt{3}}{\sqrt{2}} \end{pmatrix}$$
   liefert der Algorithmus zur Bestimmung der Inversen:
   $$\begin{pmatrix} \sqrt{2} & \frac1{\sqrt{2}} & 1 & 0 \\ 0 & \frac... ... & - \frac{1}{\sqrt{6}} \\ 0 & 1 & 0 & \frac{\sqrt{2}}{\sqrt{3}} \end{pmatrix}$$
   Die Inverse ist somit durch
   $$\begin{pmatrix} \frac1{\sqrt{2}} & - \frac{1}{\sqrt{6}} \\ 0 & \frac{\sqrt{2}}{\sqrt{3}} \end{pmatrix}$$
   gegeben.
2. Für die $2\times 2$-Matrix
   $$\begin{pmatrix}2 & 1 \\ 1 & 2 \end{pmatrix}$$
   sieht unser Algorithmus zur Bestimmung der Inversen wie folgt aus:
   $$\begin{pmatrix}2 & 1 & 1 & 0\\ 1 & 2 & 0 & 1\end{pmatrix}\mapsto ... ...\frac{2}{3} & -\frac{1}{3}\\ 0 & 1 & -\frac{1}{3} & \frac{2}{3}\end{pmatrix}.$$
   Somit ist $A$ invertierbar und die Form von $A^{-1}$ aus (10.27) verifiziert.

3. Für die Matrix $[I]$ aus (10.28a) liefert dieses Verfahren

   $$\begin{pmatrix}\frac1{\sqrt{2}} & \frac1{\sqrt{6}} & \frac1{\sqrt... ... \\ 0 & -\frac{\sqrt{2}}{\sqrt{3}} & \frac1{\sqrt{3}} & 0 & 0 & 1 \end{pmatrix} \mapsto \begin{pmatrix}1 & \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\... ...-\frac{\sqrt{2}}{\sqrt{3}} & \frac1{\sqrt{3}} & 0 & 0 & 1 \end{pmatrix} \mapsto$$

   $$\mapsto \begin{pmatrix}1 & \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\... ...c{\sqrt{3}}{\sqrt{2}} & 0 \\ 0 & 0 & \sqrt{3} & 1 & 1 & 1 \end{pmatrix} \mapsto$$

   $$\mapsto \begin{pmatrix}1 & \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\... ...ac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \end{pmatrix} \mapsto$$

   $$\mapsto \begin{pmatrix}1 & \frac{1}{\sqrt{3}} & \frac{\sqrt{2}}{\... ...ac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \end{pmatrix} \mapsto$$

   $$\mapsto \begin{pmatrix}1 & 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}... ... 1 & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \end{pmatrix}$$

   
   

4. In einem weiteren Beispiel mit einer $3\times 3$-Matrix liefert das Gauß'sche Verfahren

   $$\begin{pmatrix}1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 2 & 3 & 0 & 1 & 0\\ 1 & 4 & 9 & 0 & 0 & 1\end{pmatrix} \mapsto \begin{pmatrix}1 & 1 & 1 & \phantom{-}1 & 0 & 0 \\ 0 & 1 & 2 & -1 & 1 & 0\\ 0 & 3 & 8 & -1 & 0 & 1\end{pmatrix} \mapsto$$

   $$\mapsto \begin{pmatrix}1 & 1 & 1 & \phantom{-}1 & \phantom{-}0 & ... ... -1 & \phantom{-}1 & 0\\ 0 & 0 & 2 & \phantom{-}2 & -3 & 1\end{pmatrix} \mapsto$$

   $$\mapsto \begin{pmatrix}1 & 0 & -1 & \phantom{-}2 & -1 & 0 \\ 0 & ... ...& \phantom{-}1 & \phantom{-}1 & -\frac{3}{2} & \frac{1}{2}\end{pmatrix} \mapsto$$

   $$\mapsto \begin{pmatrix}1 & 0 & 0 & \phantom{-}3 & -\frac{5}{2} & ... ... 0 & 0 & 1 & \phantom{-}1 & -\frac{3}{2} & \phantom{-}\frac{1}{2}\end{pmatrix}.$$

   
   

11.8 Definition.
Eine lineare Abbildung $A:V\to W$ heißt regulär, wenn sie den maximal möglichen Rang $\min\{\dim(V),\dim(W)\}$ hat.

11.9 Lemma.
Der Rang einer Matrix $A\in L_\mathbb{K}(n,m)$ stimmt mit jenen der auf Zeilenstufenform transformierten Matrix überein und letzterer ist genau die Anzahl $r$ der von 0 verschiedenen Zeilen.

Beweis. Elementare Zeilenumformungen ändern die Lösungsmenge des (homogenen) Gleichungssystems $A(x)=0$ nicht. Als ist $\operatorname{Ker}(A)=\operatorname{Ker}(A')$, wobei $A'$ die auf Zeilenstufenform transformierte Matrix bezeichnet. Wegen der Dimensionsformel (10.14) ist somit $\operatorname{rang}(A)=n-\dim(\operatorname{Ker}(A))=n-\dim(Ker(A'))=\operatorname{rang}(A')$.

Nach (10.21) ist der Rang die maximale Anzahl linear unabhängiger Spalten. In der Zeilenstufenform stehen in den Spalten $j_1,\dots,j_r$ mit führenden 1'ern in den entsprechenden Zeilen gerade die Einheitsvektoren $e_1,\dots,e_r$. Diese sind linear unabhängig und alle anderen Spalten lassen sich als Linearkombination dieser schreiben. Also ist $r$ die maximale Anzahl linearunabhängiger Spalten und somit der Rang von $A'$.     []

11.9a Bemerkung.
Der Rang einer Matrix ist ebenso die maximale Anzahl linear unabhängiger Zeilen, denn die oben angegebenen Operationen ändern den Zeilenrang nicht und jener der transformierten Matrix $A'$ ist gerade $r$. Dies folgt mittels (13.15) auch aus

$$\begin{multline*} \operatorname{Rang}(A^t)=\dim(\operatorname{Bild}(A^t))=\dim(... ...name{Ker}A)=\dim(\operatorname{Bild}(A))=\operatorname{Rang}(A) \end{multline*}$$

11.10 Folgerung.
Eine lineare Gleichung $Ax=y$ ist genau dann lösbar, wenn der Rang der Matrix $[A]$ von $A$ gleich jenen der erweiterten Matrix $([A],[y])$ ist.

Beweis. Es ist $Ax=y$ genau dann lösbar, wenn $[y]\in\langle \{A(e_1),\dots,A(e_p)\}\rangle$ liegt, d.h. jede maximal unabhängige Teilmenge von Spaltenvektoren in $[A]$ ist auch eine in $([A],[y])$.     []

11.11 Proposition.
Es seien $V$ und $W$ Vektorräume der Dimension $n:=\dim(V)=\dim(W)$ sowie $B$ und $C$ Basen von diesen. Für $A\in L(V,W)$ sind folgende Aussagen äquivalent:

1. $A$ ist ein Isomorphismus;
2. $A$ ist injektiv;
3. $\operatorname{Ker}(A)=\{0\}$;
4. $A$ ist surjektiv;
5. $\operatorname{rang}(A)=n$;
6. $\tilde A=I_C\o A\o I_B^{-1}:\mathbb{K}^n\to\mathbb{K}^n$ ist ein Isomorphismus;
7. $[A]_{B,C}$ ist invertierbar;
8. $A$ ist regulär.

Beweis. $(1\Leftrightarrow 2\wedge4)$ ist trivial.

$(2\Leftrightarrow 3)$ ist (10.5).

$(4\Leftrightarrow 5)$ ist offensichtlich, wegen $\operatorname{rang}(A)=\dim(A(V))$.

$(3\Leftrightarrow 5)$ folgt aus der Dimensionsformel $\htmlref{(10.14)}{nmb:10.14}$.

$(1\Leftrightarrow 6)$, da $I_C$ und $I_B$ nach (10.16) Isomorphismen sind.

$(6\Leftrightarrow 7)$ gilt da wegen (10.23) und 10.24 die lineare Abbildung $\tilde A$ genau dann invertierbar ist, wenn die Matrix $[\tilde A]$ es ist.

$(5\Leftrightarrow 8)$ ist offensichtlich.     []

11.12 Lineare Codes.

Wir wollen als nächstes kurz eine Anwendung der linearen Algebra über endlichen Körpern besprechen, nämlich die sogenannten linearen Codes. Der Einfachheit halber werden wir uns auf den Körper $\Bbb Z_2$ beschränken und hauptsächlich ein konkretes Beispiel (nämlich den sogenannten Hemming-(4,7)-Code) besprechen, anstatt die allgemeine Theorie zu entwickeln.

Bei Codes sollte man nicht an Geheimbotschaften denken, sondern daran, daß man eine Botschaft übertragen möchte, wobei man damit rechnen muß, daß bei der Übertragung Fehler auftreten können. Der Einfachheit halber treffen wir die (ziemlich realistische) Annahme, daß unsere Botschaft einfach eine Folge von ``Worten'' einer fixen Länge $k$ in den ``Buchstaben'' $\{0,1\}$ ist. Wir können also ein solches Wort als ein Element $(x_1,\dots,x_k)\in\mathbb{Z}_2^k$ betrachten. (Bislang wir die Restklassen mit eckigen Klammern angedeutet, also $\mathbb{Z}_2=\{[0],[1]\}$ geschrieben. Die jetzige Schreibweise ist aber dadurch gerechtfertigt, daß $[0]$ das additiv neutrale und $[1]$ das multiplikativ neutrale Element ist, die wir ja immer mit 0 bzw.  $1$ bezeichnet haben.) Die einzige Rechenregel in $\mathbb{Z}_2$, die nicht aus den Eigenschaften der neutralen Elemente folgt ist $1+1=0$.

Wir wollen nun annehmen, daß wir unsere Botschaft auf irgend eine Art und Weise übertragen, und das vereinzelt Fehler auftreten können, also vereinzelt Nullen in Einser und Einser in Nullen verwandelt werden. Wir wollen solche Fehler erkennbar und wenn möglich sogar korrigierbar machen, indem wir zusätzliche Informationen übertragen (in die bei der Übertragung natürlich auch Fehler hinein kommen können). Damit so etwas praktisch nutzbar ist, sollte natürlich die Codierung (also das Hinzufügen der zusätzlichen Information) und die Decodierung (also das Zurückgewinnen der ursprünglichen Information) möglichst einfach sein.

Eine einfache Methode in dieser Richtung ist die Übertragung eines zusätzlichen Prüf- oder Paritätsbits. Man macht einfach aus einem Wort $(x_1,\dots,x_k)$ der Länge $k$ ein Wort der Länge $k+1$, indem man $x_{k+1}$ so wählt, daß in dem Wort $(x_1,\dots,x_{k+1})$ eine gerade Anzahl von Einsen vorkommt, d.h.  $x_{k+1}=x_1+\dots +x_k$ (in $\mathbb{Z}_2$!). Empfängt man ein Wort der Länge $k+1$, dann bildet man $x_1+\dots+x_{k+1}$. Ist diese Summe gleich Null, dann nimmt man einfach die ersten $k$ Elemente als übertragenes Wort. Ist die Summe gleich Eins, dann weiß man, daß in der Übertragung ein Fehler aufgetreten ist (aber nicht an welcher Stelle). Treten zwei Fehler auf, dann kann man das mit dieser Methode nicht mehr erkennen. Man kann diese Methode so interpretieren, daß man auf die Datenworte aus $\mathbb{Z}_2^k$ zunächst eine lineare Abbildung $\mathbb{Z}_2^k\to\Bbb Z_2^{k+1}$ (die das Hinzufügen des Prüfbits beschreibt) anwendet, dann das Bild überträgt. Dann kann man mit einer linearen Abbildung $\mathbb{Z}_2^k\to\mathbb{Z}_2$ (dem Verifikationstest) feststellen ob ein Fehler aufgetreten ist, und falls nicht das ursprüngliche Wort durch eine lineare Abbildung $\mathbb{Z}_2^{k+1}\to\mathbb{Z}_2^k$ (der Rekonstruktion) rekonstruieren.

Wichtig für die Qualität eines Codes ist nicht die lineare Abbildung, die zum Bilden der Codeworte verwendet wird, sondern nur ihr Bild. Deshalb definiert man einen linearen $(n,k)$-Code über $\mathbb{Z}_2$ als einen $k$-dimensionalen Teilraum $C$ von $\Bbb Z_2^n$. Wir wollen nun einen (sehr guten) linearen $(7,4)$-Code, den sogenannten Hemming $(7,4)$-Code beschreiben, bei dem mit 3 Prüfbits bis zu $2$ Fehler sicher erkannt und Einzelfehler sicher korrigiert werden können. (Warum gerade die Kombination $(7,4)$ günstig ist, werden wir im Verlauf der Konstruktion sehen.)

Wir suchen also einen $4$-dimensionalen Teilraum $C$ von $\Bbb Z_2^7$, dessen Element die gültigen Codeworte sind. Eine einfache Methode, so einen Teilraum anzugeben, ist als Kern einer surjektiven linearen Abbildung $\varphi :\mathbb{Z}_2^7\to\mathbb{Z}_2^3$, deren zugehörige Matrix $K$ die Kontrollmatrix des Codes heißt. Somit ist ein (empfangenes) Codewort $x$ genau dann gültig, wenn $Kx=0$ gilt. Das Auftreten eines Fehlers in der Übertragung kann man so interpretieren, daß zu einem gültigen Codewort $x$ ein Fehlerwort $y$ addiert wird. (In $\mathbb{Z}_2$ entspricht ja Addition von $1$ genau dem Vertauschen von 0 und $1$.) Die Anzahl der Übertragungsfehler ist genau die Anzahl der Einsen in $y$. Wegen der Linearität gilt nun $K(x+y)=Kx+Ky=Ky$, also können Fehler genau dann erkannt werden, wenn die Fehlerworte nicht im Kern von $\varphi$ liegen. Wollen wir also Einzelfehler erkennen, dann muß zumindest $Ke_i\neq 0$ für $i=1,\dots,7$ gelten.

Wir wollen aber Einzelfehler nicht nur erkennen, sondern sogar korrigieren können. Um das zu tun, müssen wir die Einzelfehler von einander unterscheiden können, also muß $Ke_i\neq Ke_j$ für $i\neq j$ gelten. Dies läßt uns für $K$ aber im Wesentlichen nur noch eine Möglichkeit, weil $\mathbb{Z}_2^3$ genau $2^3=8$ Elemente, also genau $7$ Elemente außer Null hat. Wir wählen also

$$K=\begin{pmatrix}1 & 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix}.$$

Diese Wahl ist so getroffen, daß $Ke_i$ gerade die Darstellung von $i$ als Binärzahl ist. Dies hat aber noch eine wichtige Konsequenz: Da in $\mathbb{Z}_2^3$ immer $x=-x$ gilt, und $Ke_i\neq Ke_j$ für $i\neq j$ gilt, ist auch $K(e_i+e_j)=Ke_i+Ke_j\neq 0$ für $i\neq j$. Das bedeutet aber, daß auch Doppelfehler noch sicher erkannt werden.

Somit gehen wir also folgendermaßen vor: Empfangen wir ein Wort $x$, dann bilden wir $Kx$. Ist das gleich Null, dann ist kein (erkennbarer) Übertragungsfehler aufgetreten, und $x$ ist das richtige Codewort. Ist $Kx\neq 0$, dann ist sicher ein Übertragungsfehler aufgetreten. War das ein Einzelfehler (die wahrscheinlichste Möglichkeit) dann erhält man das ursprüngliche Codewort, indem man $Kx$ als Binärzahl $j$ interpretiert und dann die $j$-te Eintragung von $x$ ändert (also $x+e_j$ bildet).

Nun wollen wir noch eine konkrete Codierung angeben, also eine lineare Abbildung $\mathbb{Z}_2^4\to\operatorname{Ker}(\varphi )$, deren zugehörige Matrix die Generatormatrix $G$ des Codes heißt. Die einfachste Möglichkeit wäre natürlich, an ein Wort $(x_1,\dots,x_4)$ einfach drei geeignete Prüfbits $(x_5,x_6,x_7)$ anzuhängen. Um das zu realisieren müßten die ersten 4 Zeilen der $4\times 7$-Matrix $G$ die $4\times 4$-Einheitsmatrix $\Bbb I_4$ bilden. Das stellt auch sicher, daß $G$ einer injektiven linearen Abbildung entspricht, also genügt es zusätzlich sicher zu stellen, daß $KG=0$ gilt, denn dann liefert $G$ aus Dimensionsgründen einen linearen Isomorphismus $\Bbb Z_2^4\to\operatorname{Ker}(\varphi )$. Nun verifiziert man leicht durch Lösen eines linearen Gleichungssystems, daß die beiden Bedingungen $G$ eindeutig festlegen. Bestimmt man $G$ explizit, dann sieht man, daß die Prüfbits gegeben sind durch $x_5=x_2+x_3+x_4$, $x_6=x_1+x_3+x_4$ und $x_7=x_1+x_2+x_4$.

Beispiel.
Nehmen wir an, daß ursprüngliche Datenwort ist $(1,0,1,0)$. Nach der Vorschrift zum Bilden der Prüfbits wird das zu $x=(1,0,1,0,1,0,1)$ kodiert. Wird dieses Codewort korrekt übertragen, dann erhält man $Kx=0$, und gewinnt das ursprüngliche Wort $(1,0,1,0)$ als die ersten vier Stellen. Tritt etwa an der zweiten Stelle ein Fehler auf, dann empfangen wir statt $x$ das Wort $x'=(1,1,1,0,1,0,1)$. Nachrechnen ergibt $Kx'=(0,1,0)$. Also sehen wir, daß ein Fehler aufgetreten ist, und zwar vermutlich an der zweiten Stelle. Also sollte das übertragene Wort $(1,0,1,0,1,0,1)$ sein, dessen erste vier Stellen das richtige Datenwort $(1,0,1,0)$ liefern. Nehmen wir nun an, daß zwei Übertragungsfehler auftreten, etwa an der zweiten und der letzten Stelle. Dann empfangen wir das Wort $x''=(1,1,1,0,1,0,0)$ und $Kx''=(1,0,1)$. Wir stellen also (richtigerweise) fest, daß ein Übertragungsfehler aufgetreten ist, der wahrscheinlichste Übertragungsfehler wäre aber eine Änderung in der fünften Stelle (also einem Prüfbit), und wir würden (fälschlicherweise) vermuten, daß das ursprüngliche Wort $(1,1,1,0)$ war.