5.3 Das Matrizenprodukt

5.3.1 Rechnen mit Matrizen

In diesem Abschnitt wollen wir Matrizen noch einmal losgelöst vom Begriff des linearen Gleichungssystems studieren und insbesondere Rechenoperationen auf der Menge der Matrizen definieren, die sich in vielen Situationen als sehr nützlich erweisen (auch für die Behandlung von linearen Gleichungssystemen). Wir wiederholen hier zur Erinnerung noch einmal die Definition 5.6.

Definition 5.28

Seien $m, n$ natürliche Zahlen. Unter einer Matrix der Größe $m\times n$ mit Einträgen in $K$ (man spricht auch von einer $(m\times n)$-Matrix über $K$) verstehen wir eine Familie $(a_{ij})_{i=1, \dots , m,\, j=1, \dots , n}$ von Elementen von $K$. Die Elemente $a_{ij}$ heißen die Einträge oder Koeffizienten der Matrix. Eine Matrix stellen wir uns immer in der Form

\[ \left( \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{array} \right) \]

vor, d.h. wir schreiben die Koeffizenten in einem rechteckigen Schema auf, in dem der erste Index die Zeile und der zweite Index die Spalte angibt.

Die Menge aller $(m\times n)$-Matrizen über $K$ bezeichnen wir mit $M_{m\times n}(K)$. Ist $m=n$, so schreiben wir manchmal $M_n(K)$ statt $M_{m\times n}(K)$.

Die Nullmatrix (der Größe $m\times n$) ist die Matrix $0\in M_{m\times n}(K)$, deren Einträge alle gleich Null sind.

Als Spezialfall können wir die Elemente des $K^n$, die wir wie gehabt als Spaltenvektoren betrachten wollen, als Matrizen mit $n$ Zeilen und einer Spalte auffassen, das heißt $K^n = M_{n\times 1}(K)$.

Auch mit Matrizen kann man rechnen. Um zum Beispiel zwei Matrizen (der selben Größe) zu addieren, addieren wir einfach auf jeder Position separat die Einträge. Wie man sinnvolles Produkt von zwei Matrizen definiert, ist nicht ganz so offensichtlich. Wir fassen die wichtigen Rechenoperationen in der folgenden Definition zusammen:

Definition 5.29

Seien $K$ ein Körper und $l, m, n$ natürliche Zahlen. Die Einträge der Matrizen $A$ und $B$ bezeichnen wir mit $a_{ij}$ beziehungsweise $b_{ij}$.

(Summe von Matrizen) Für Matrizen $A, B \in M_{m\times n}(K)$ derselben Größe definieren wir

\[ A+B = (a_{ij} + b_{ij})_{i=1, \dots , m,\, j=1,\dots , n} \in M_{m\times n}(K). \]
(Produkt eines Skalars und einer Matrix) Für eine Matrix $A\in M_{m\times n}(K)$ und ein Element $a\in K$ definieren wir

\[ aA = Aa = (aa_{ij})_{ij}\in M_{m\times n}(K). \]
(Produkt zweier Matrizen) Sind $A \in M_{l\times m}(K)$ und $B\in M_{m\times n}(K)$ Matrizen, so definieren wir das Produkt

\[ A \cdot B = \left(\sum _{j=1}^m a_{ij} b_{jk} \right)_{i=1, \dots , l,\, k=1,\dots , n} \in M_{l\times n}(K). \]

Den Multiplikationspunkt lässt man dabei oft aus: $AB = A\cdot B$.

Beispiel 5.30

Es ist für die Berechnung des Matrizenprodukts manchmal hilfreich, die zu multiplizierenden Matrizen $A$ und $B$ so anzuordnen, wie in der Abbildung gezeigt, d.h. dass $B$ nach oben verschoben wird, und das Ergebnis dann rechts von $A$ und unter $B$ zu stehen kommt. Um die Zelle $c_{ij}$ von $C=AB$ auszurechnen, benutzt man die $i$-te Zeile von $A$ und die $j$-te Spalte von $B$. Diese haben beide $m$ Einträge. Man multipliziert die ersten Einträge, die zweiten Einträge, …, und summiert alle diese Produkte auf.

$\begin{tikzpicture} [>=latex] \matrix (A) [matrix of math nodes,% nodes = {node style ge},% left delimiter = (,% right delimiter = )] at (0,0) {% a_{11} &\ldots & a_{1k} & \ldots & a_{1m} \\ \vdots & \ddots & \vdots & \vdots & \vdots \\ \node[node style sp] (A-3-1) {a_{i1}};& \node[node style sp] {\ldots}; & \node[node style sp] (A-3-3) {a_{ik}};% & \node[node style sp]{\ldots}; & \node[node style sp] (A-3-5) {a_{im}}; \\ \vdots & \vdots& \vdots & \ddots & \vdots \\ a_{l1}& \ldots & a_{lk} & \ldots & a_{lm} \\ }; \node [below] at (A.south) {$A\in M_{l\times m}(K)$}; \matrix (B) [matrix of math nodes,% nodes = {node style ge},% left delimiter = (,% right delimiter =)] at (7*\myunit,6*\myunit) {% b_{11} & \ldots& \node[node style sp] (B-1-3) {b_{1j}}; & \ldots & b_{1n} \\ \vdots& \ddots & \node[node style sp] {\vdots}; & \vdots & \vdots \\ b_{k1} & \ldots& \node[node style sp] (B-3-3) {b_{kj}}; & \ldots & b_{kn} \\ \vdots& \vdots & \node[node style sp] {\vdots};& \ddots & \vdots \\ b_{m1} & \ldots& \node[node style sp] (B-5-3) {b_{mj}};% & \ldots & b_{mn} \\ }; \node [above] at (B.north) { $B\in M_{m\times n}(K)$}; \matrix (C) [matrix of math nodes,% nodes = {node style ge},% left delimiter = (,% right delimiter = )] at (7*\myunit,0) {% c_{11} & \ldots& c_{1j} & \ldots & c_{1n} \\ \vdots& \ddots & \vdots & \vdots & \vdots \\ c_{i1}& \ldots & \node[rectangle, fill=red!30] (C-3-3) {c_{ij}};% & \ldots & c_{in} \\ \vdots& \vdots & \vdots & \ddots & \vdots \\ c_{l1}& \ldots & c_{lk} & \ldots & c_{ln} \\ }; \node [below] at (C.south) {$C=A B\in M_{l\times n}(K)$}; \draw[<->,red, thick](A-3-1) to[in=180,out=90] node[black, arrow style mul] (x) {$a_{i1}b_{1j}$} (B-1-3); \draw[<->,red, thick](A-3-3) to[in=180,out=90] node[black, arrow style mul] (y) {$a_{ik}b_{kj}$}(B-3-3); \draw[<->,red, thick](A-3-5) to[in=180,out=90] node[black, arrow style mul] (z) {$a_{im}b_{mj}$}(B-5-3); \draw[red,->] (x) to node[arrow style plus] {$+\raisebox{.5ex}{\ldots}+$} (y)% to node[arrow style plus] {$+\raisebox{.5ex}{\ldots}+$} (z); % % to (C-3-3.north west); \draw[double equal sign distance] (z) -- (C-3-3.north west); \end{tikzpicture}$

(Illustration angepasst von texample.net, Autor: Alain Matthes.)

Angesichts der Identifikation $K^n = M_{n\times 1}(K)$ können wir auch Elemente von $K^n$ mit Matrizen multiplizieren (wenn die Größen zusammenpassen). Für quadratische Matrizen $A\in M_n(K)$ können wir dann auch die Potenzen $A^n$ von $A$ für $n\in \mathbb N$ definieren: $A^0 = E_n$, $A^1=A$, $A^2 = AA$, und so weiter: $A^n = A^{n-1}A$ für $n{\gt}0$.

Satz 5.31

(Eigenschaften der Rechenoperationen mit Matrizen) Seien $l, m, n \in \mathbb N$.

Die Addition von Matrizen definiert eine Verknüpfung

\[ + \colon M_{m\times n}(K)\times M_{m\times n}(K)\to M_{m\times n}(K), \]

die die folgenden Eigenschaften hat:
1. Assoziativität: $(A+B)+C=A+(B+C)$,
2. Kommutativität: $A+B = B+A$,
3. die Nullmatrix $0$ ist neutrales Element: $0+A = A = A+0$,
4. das additive Inverse der Matrix $(a_{ij})_{i,j}$ ist die Matrix $-A := (-a_{ij})_{i,j} (=(-1)\cdot A)$.
Die Multiplikation von Matrizen definiert eine assoziative Verknüpfung $M_{l \times m}(K)\times M_{m\times n}(K)\to M_{l\times n}(K)$.
Die Addition und das Produkt von Matrizen verhalten sich distributiv, d.h. es gilt

\[ (A + B)C = AC + BC,\quad A(B+C) = AB + AC, \]

wenn immer man die entsprechenden Summen und Produkte bilden kann.

Beweis

Die Eigenschaften der Addition sind klar, da die Addition eintragweise erfolgt. Seien nun $A$, $B$, $C$ Matrizen mit Einträgen $a_{ij}$, $b_{ij}$, $c_{ij}$, so dass die Produkte $AB$, und $BC$ existieren. Die Assoziativität des Produkts ergibt sich aus der Gleichungskette

\[ \sum _k \left(\sum _j a_{ij} b_{jk}\right) c_{kl} = \sum _k \sum _j a_{ij} b_{jk} c_{kl} = \sum _j \sum _k a_{ij} b_{jk} c_{kl} = \sum _j a_{ij} \left(\sum _k b_{jk}c_{kl}\right), \]

in der links der Eintrag von $(AB)C$ in der $i$-ten Zeile und $l$-ten Spalte, und rechts der entsprechende Eintrag von $A(BC)$ steht. (Die Intervalle, über die die Indizes in den Summen laufen, bestimmen sich aus der Größe von $B$ und sind hier ausgelassen.) Die äußeren Gleichheiten benutzen dabei das Distributivgesetz in $K$, die mittlere das Kommutativgesetz: Wir summieren die Ausdrücke $a_{ij} b_{jk} c_{kl}$ für alle $j$ und $k$ auf, und es spielt keine Rolle, wie wir sie anordnen.

Die Rechnung für das Distributivgesetz ist einfach und wir lassen sie hier aus.

Die Einheitsmatrix (der richtigen Größe) ist ein neutrales Element bezüglich der Multiplikation: $E_m A = A$ und $AE_n=A$ für alle $A\in M_{m\times n}(K)$.

Beispiel 5.32

Wie das folgende Beispiel zeigt, ist das Produkt von Matrizen nicht kommutativ:

\[ \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right) = \left( \begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array} \right) \ne \left( \begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array} \right) = \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right) \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right). \]

Die Multiplikation eines Skalars mit einer Matrix ist auch assoziativ und kommutativ: $a(AB) = (aA)B = A(aB)$, wie man unmittelbar nachprüft.

Ergänzung 5.33 Der Strassen-Algorithmus

Interessanterweise lässt sich ein Produkt von zwei $(n\times n)$-Matrizen mit weniger als den a priori erforderlichen $n^3$ Multiplikationen berechnen. Die bekannteste Methode ist der Strassen-Algorithmus . Für das Produkt von zwei $(2\times 2)$-Matrizen kommt er mit $7$ Multiplikationen (statt $8$ für die direkte Rechnung) aus; allerdings werden mehr Additionen als in der direkten Rechnung durchgeführt. Weil Computer für eine Multiplikation mehr Zeit benötigen als für eine Addition, wird der Algorithmus in der Praxis verwendet, aber er bringt einen signifikanten Vorteil erst für Matrizen mit mehreren Hundert Zeilen und Spalten.

Beispiel 5.34

Eine weitere Eigenschaft des Matrizenprodukts, die einen Unterschied zur Multiplikation in einem Körper bedeutet, ist, dass das Produkt von zwei Matrizen $\ne 0$ die Nullmatrix sein kann:

\[ \left( \begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array} \right)^2 = \left( \begin{array}{cc} 0 & 0 \\ 0 & 0 \end{array} \right) \]

Auch wenn die Berechnung des Matrizenprodukts nicht schwierig ist, gibt es darüber weitreichende strukturelle Aussagen, für deren Beweis wir erst im Laufe der Vorlesung die notwendigen Methoden entwickeln werden. Ein Beispiel für so eine Aussage ist der folgende

Satz 5.35

Seien $K$ ein Körper, $n\ge 1$, $A\in M_{n\times n}(K)$. Wenn eine natürliche Zahl $N$ existiert mit $A^N = 0$, dann gilt $A^n = 0$.

Siehe Satz 6.56 für einen Beweis. In der Linearen Algebra 2 werden wir diese Aussage noch weiter verallgemeinern und besser verstehen können (der hier angegebene Satz ist ein Spezialfall des »Satzes von Cayley-Hamilton«).

Bemerkung 5.36

Sei $(A\mid b)$ die erweiterte Koeffizientenmatrix eines linearen Gleichungssystems. Für $x\in K^n = M_{n\times 1}(K)$ ist dann das Matrizenprodukt $Ax$ eine $(m\times 1)$-Matrix, also ein Element von $K^m$, und zwar mit dem Eintrag

\[ \sum _{j=1}^n a_{ij}x_j \]

in der $i$-ten Zeile; das ist genau die linke Seite der $i$-ten Gleichung des betrachteten Gleichungssystems. Das bedeutet: $x\in K^n$ ist ein Lösungsvektor des linearen Gleichungssystems genau dann, wenn $Ax=b$. Die Lösungsmenge des linearen Gleichungssystems $(A\mid b)$ ist also

\[ \{ x\in K^n;\ A x=b \} . \]

Bemerkung 5.37

Wir können elementare Zeilenumformungen als Multiplikation mit einer geeigneten Matrix von links ausdrücken. Sei $A$ eine Matrix.

Typ (I). Sei $A^\prime $ die Matrix, die aus $A$ durch Addition des $a$-fachen der $j$-ten Zeile zur $i$-ten Zeile entsteht. Dann gilt

\[ A^\prime = E_{ij}(a) A, \]

wobei wir für $i\ne j$ und $a\in K$ definieren:

\[ E_{ij}(a):= \left( \begin{array}{ccccc} 1 \\ & \ddots & & a \\ & & \ddots & \\ & & & \ddots \\ & & & & 1 \end{array} \right), \]

wobei der Eintrag $a$ in der $i$-ten Zeile und $j$-ten Spalte ist, auf der Diagonale Einsen stehen und alle anderen Einträge Null sind. (Ist $i{\gt}j$ so befindet sich der Eintrag $a$, anders als in der Abbildung, unterhalb der Diagonalen.)

Typ (II). Sei $A^\prime $ die Matrix, die aus $A$ durch Vertauschen der $i$-ten und $j$-ten Zeile entsteht. Dann gilt

\[ A^\prime = P_{ij} A, \]

wobei wir für $i\ne j$ definieren:

\[ P_{ij} := \left( \begin{array}{ccccccc} 1 \\ & \ddots & & \\ & & 0 & & 1 \\ & & & \ddots & & \\ & & 1 & & 0 & \\ & & & & & \ddots \\ & & & & & & 1 \end{array} \right). \]

Hier befinden sich die beiden Einsen außerhalb der Diagonale in Zeile $i$ und Spalte $j$, und in Zeile $j$ und Zeile $i$. Auf der Diagonale stehen in den Zeilen $i$ und $j$ Nullen, sonst überall $1$.

Typ (III). Sei $A^\prime $ die Matrix, die aus $A$ durch Multiplikation der $i$-ten Zeile mit $a\in K^\times $ entsteht. Dann gilt

\[ A^\prime = \left( \begin{array}{ccccccc} 1 \\ & \ddots \\ & & 1 \\ & & & a \\ & & & & 1 \\ & & & & & \ddots \\ & & & & & & 1 \end{array} \right)A, \]

wobei sich der Eintrag $a$ auf der Diagonalen an Position $i$ befindet, alle anderen Einträge aus der Diagonalen sind $1$, alle Einträge außerhalb der Diagonalen sind $0$. Wir werden für diese »Diagonalmatrix« später die Notation $\operatorname{diag}(1, \dots , 1, a, 1, \dots 1)$ benutzen, siehe Abschnitt 5.3.2.

Wir können nun auch die Schreibweise $-^t$, die wir für Zeilenvektoren schon eingeführt hatten, auf beliebige Matrizen ausdehnen:

Definition 5.38

Sei $A=(a_{ij})_{i,j}\in M_{m\times n}(K)$ eine Matrix. Die transponierte Matrix $A^t$ von $A$ ist die Matrix

\[ A^t = (a_{ji})_{i=1,\dots , n,\ j=1,\dots m} \in M_{n\times m}. \]

Beim Übergang zur transponierten Matrix spiegeln wir also sozusagen an der Diagonalen. Die Anzahl der Zeilen in $A^t$ ist die Anzahl der Spalten von $A$, und umgekehrt.

Beispiel 5.39

\[ \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array} \right)^t = \left( \begin{array}{cc} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{array} \right). \]
\[ \left( \begin{array}{cccc} 1 & 2& 3& 4 \end{array} \right)^t = \left( \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \end{array} \right),\qquad \left( \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \end{array} \right)^t = \left( \begin{array}{cccc} 1 & 2& 3& 4 \end{array} \right) \]

Lemma 5.40

Sei $A$ eine Matrix. Dann gilt $A^{tt} := (A^t)^t = A$.
Seien $A$, $B$ Matrizen, deren Produkt $AB$ existiert. Dann existiert das Produkt $B^t A^t$ und es gilt

\[ (AB)^t = B^t A^t. \]

Beweis

Teil (1) ist klar. Zu Teil (2). Die Existenz der Produkte heißt in beiden Fällen, dass $B$ so viele Zeilen wie $A$ Spalten hat. Der Eintrag von $(AB)^t$ in der $j$-ten Zeile und $i$-ten Spalte ist der Eintrag von $AB$ in Zeile $i$ und Spalte $j$, also

\[ \sum _{k} a_{ik} b_{kj}, \]

wobei wir $A=(a_{ik})_{i,k}$ und $B=(b_{k,j})_{k,j}$ geschrieben haben. Aber das ist nichts anderes als

\[ \sum _k b_{kj} a_{ik}, \]

was der Eintrag von $B^t A^t$ in Zeile $j$ und Spalte $i$ ist.

5.3.2 Spezielle Matrizen

Wir führen noch einige Sprechweisen über Matrizen mit speziellen Eigenschaften ein.

Sei $A = (a_{ij})_{i,j}$ eine quadratische Matrix der Größe $n\times n$. Wir nennen $A$ eine obere Dreiecksmatrix, wenn $a_{ij} = 0$ für alle $i,j$ mit $i {\gt} j$. (An den links mit $\ast $ markierten Einträgen kann irgendein Element von $K$ stehen, die unmarkierten Einträge müssen $=0$ sein.)

\[ \left( \begin{array}{cccc} \ast & \ast & \cdots & \ast \\ & \ast & \cdots & \ast \\ & & \ddots & \vdots \\ & & & \ast \end{array} \right) \]

Analog kann man von unteren Dreiecksmatrizen sprechen (also wenn $a_{ij} = 0$ für alle $i,j$ mit $i {\lt} j$).

\[ \left( \begin{array}{cccc} \ast & & & \\ & \ast & & \\ & & \ddots & \\ & & & \ast \end{array} \right) \]

Eine Diagonalmatrix ist eine quadratische Matrix $A=(a_{ij})_{i,j}$ mit $a_{ij}=0$ für alle $i\ne j$. Mit $\operatorname{diag}(c_1, \dots , c_n)$ bezeichnen wir die Diagonalmatrix der Größe $n$ mit den Diagonaleinträgen $c_1, c_2, \dots , c_n$. Dann gilt $aA = \operatorname{diag}(a, \dots , a)A = A\operatorname{diag}(a, \dots , a)$ für $a\in K$ und $A\in M_{m\times n}$, wobei in der $\operatorname{diag}$-Ausdruck auf der linken Seite von $A$ dann $m$ Einträge, der auf der rechten Seite $n$ Einträge haben muss.

Die $(n\times n)$-Matrix

\[ E_n := \operatorname{diag}(1, \dots , 1) = \left( \begin{array}{cccc} 1 \\ & 1 \\ & & \ddots \\ & & & 1 \end{array} \right) \]

heißt die Einheitsmatrix (der Größe $n$ über dem Körper $K$). (Die Einträge, die gleich Null sind, sind hier weggelassen.)

Wir können Matrizen aus kleineren Matrizen (passender Größen) zusammensetzen; wir sprechen dann von der Notation als Blockmatrizen. Sind zum Beispiel $A\in M_{m_1 \times n_1}(K)$, $B\in M_{m_1 \times n_2}(K)$, $C\in M_{m_2 \times n_1}(K)$, $D\in M_{m_2 \times n_2}(K)$, so erhalten wir durch Zusammensetzen die $(m_1+m_2)\times (n_1+n_2)$-Matrix $\left( \begin{array}{cc} A & B\\ C& D \end{array} \right)$.

Das ist verträglich mit der Multiplikation von Matrizen:

Lemma 5.41

Für $M = \left( \begin{array}{cc} A & B\\ C& D \end{array} \right)$ und $M^\prime = \left( \begin{array}{cc} A^\prime & B^\prime \\ C^\prime & D^\prime \end{array} \right)$ mit $A\in M_{l_1\times m_1}(K)$, $B\in M_{l_1\times m_2}(K)$, $C\in M_{l_2\times m_1}(K)$, $D\in M_{l_2\times m_2}(K)$, $A^\prime \in M_{m_1 \times n_1}(K)$, $B^\prime \in M_{m_1 \times n_2}(K)$, $C^\prime \in M_{m_2 \times n_1}(K)$, $D^\prime \in M_{m_2 \times n_2}(K)$ gilt

\[ MM^\prime = \left( \begin{array}{cc} A & B \\ C & D \end{array} \right) \left( \begin{array}{cc} A^\prime & B^\prime \\ C^\prime & D^\prime \end{array} \right) = \left( \begin{array}{cc} AA^\prime + BC^\prime & AB^\prime + BD^\prime \\ CA^\prime + DC^\prime & CB^\prime + DD^\prime \\ \end{array} \right)\in M_{(l_1+l_2)\times (n_1+n_2)}(K). \]

Beweis

Das lässt sich unmittelbar anhand der Definition des Matrixprodukts nachrechnen.

Weil das Matrizenprodukt (der kleineren Matrizen) nicht kommutativ ist, darf man natürlich in der Situation des Lemmas in den Produkten in den einzelnen Blockeinträgen von $MM^\prime $ die Faktoren nicht vertauschen. Ähnlich funktioniert das mit Blockmatrizen, deren Zeilen und/oder Spalten mehr als zwei Blöcke enthalten.

Bemerkung 5.42

Wir betrachten den Körper $\mathbb C$ der komplexen Zahlen (siehe Beispiel 4.5). Die Elemente von $\mathbb C$ schreiben wir als $a+bi$ mit $a,b\in \mathbb R$.

Wir haben eine Bijektion

\[ \iota \colon \mathbb C\to \left\{ \left( \begin{array}{cc} a & -b \\ b & a \end{array} \right);\ a,b\in \mathbb R\right\} \]

Dabei entsprechen die Addition und Multiplikation auf der linken Seite genau der Addition und Multiplikation von Matrizen auf der rechten Seite, das heißt für alle $z_1, z_2\in \mathbb C$ gilt:

\[ \iota (z_1+ z_2) = \iota (z_1)+\iota (z_2),\qquad \iota (z_1 z_2) = \iota (z_1)\iota (z_2). \]

Dies rechnet man unmittelbar anhand der Definitionen von Addition und Multiplikation auf den beiden Seiten nach. Zum Beispiel für die Multiplikation (der schwierigere Fall), mit $z_\lambda = a_\lambda + b_\lambda i$, $\lambda =1,2$:

\[ \iota (z_1z_2) = \left( \begin{array}{cc} a_1a_2-b_1b_2 & -(a_1b_2 + a_2b_1)\\ a_1b_2 + a_2b_1 & a_1a_2-b_1b_2 \end{array} \right) \]

und

\[ \iota (z_1)\iota (z_2) = \left( \begin{array}{cc} a_1 & -b_1 \\ b_1 & a_1 \end{array} \right) \left( \begin{array}{cc} a_2 & -b_2 \\ b_2 & a_2 \end{array} \right) = \left( \begin{array}{cc} a_1a_2-b_1b_2 & -a_1b_2 - b_1a_2 \\ b_1a_2 +a_1b_2 & -b_1b_2+ a_1a_2\end{array} \right). \]

Es spielt dabei keine Rolle, ob wir schon wissen, dass $\mathbb C$ mit diesen Verknüpfungen ein Körper ist. Wir sehen auch, dass für zwei Matrizen von der oben betrachten Form (d.h., die im Bild von $\iota $ liegen), auch die Summe und das Produkt diese Form haben.

Wir können die Bijektion $\iota $ (und die Gültigkeit der Assoziativgesetze und des Distributivgesetzes in $M_2(\mathbb R)$) benutzen, um zu beweisen, dass die Assoziativgesetze für $+$ und $\cdot $ und das Distributivgesetz in $\mathbb C$ gelten. Dazu bezeichnen wir mit $\iota ^{-1}$ die Umkehrabbildung.

Nun folgt zum Beispiel das Assoziativgesetz der Multiplikation:

\begin{align*} (z_1z_2)z_3 & = \iota ^{-1}(\iota ((z_1 z_2)z_3)) = \iota ^{-1}(\iota (z_1z_2)\iota (z_3)) = \iota ^{-1}((\iota (z_1)\iota (z_2))\iota (z_3))\\ & = \iota ^{-1}(\iota (z_1)(\iota (z_2)\iota (z_3))) = \iota ^{-1}(\iota (z_1)\iota (z_2z_3)) = \iota ^{-1}(\iota (z_1(z_2z_3))) = z_1(z_2z_3). \end{align*}

(Vergleichen Sie das mit der Methode, wie wir in Abschnitt 4.2.1 das Assoziativgesetz in $\mathbb Z$ und die kanonische Projektion $\mathbb Z\to \left.\mathbb Z\middle /n\right.$ benutzt haben, um das Assoziativgesetz in $\left.\mathbb Z\middle /n\right.$ zu beweisen.)

Für das Assoziativgesetz der Addition und das Distributivgesetz kann man genau dieselbe Methode anwenden, um diese auf die entsprechenden Aussagen in $M_2(\mathbb R)$ zurückzuführen.

5.3.3 Bild und Kern einer Matrix

Wir wollen in diesem Abschnitt beschreiben, wie wir einer Matrix $A\in M_{m\times n}(K)$ eine Abbildung $\mathbf f_A\colon K^n\rightarrow K^m$, $x\mapsto Ax$, zuordnen können, und erklären, wie wir damit einige Aussagen über lineare Gleichungssysteme noch einmal umformulieren können. Diese neue Sichtweise ist ein wichtiger Spezialfall der Theorie der linearen Abbildungen, die wir in Kapitel 7 entwickeln werden. Diese beiden Kapitel stellen einen sehr wichtigen Teil der Vorlesung dar, so dass es die Zeit wert ist, uns an dieser Stelle schon ein bisschen darauf vorzubereiten.

Das Grundprinzip ist sehr einfach:

Definition 5.43

Seien $K$ ein Körper und $A\in M_{m\times n}(K)$ eine Matrix über $K$. Wir nennen die Abbildung

\[ \mathbf f_A\colon K^n\rightarrow K^m,\quad x\mapsto Ax, \]

die durch $A$ definierte Abbildung.

Zwei wichtige Begriffe über Abbildungen der Form $\mathbf f_A$ sind das Bild (wie für jede Abbildung) und der Kern:

Definition 5.44

Sei $A\in M_{m\times n}(K)$. Das Bild von $A$, in Zeichen $\operatorname{Im}A$, ist das Bild der Abbildung $\mathbf f_A\colon K^n\rightarrow K^m$, d.h.

\[ \operatorname{Im}A = \{ y\in K^m;\ \text{ es existiert } x\in K^n, \text{ so dass } Ax=y \} . \]

Definition 5.45

Sei $A\in M_{m\times n}(K)$. Der Kern von $A$, in Zeichen $\operatorname{Ker}A$, ist das Urbild des Elements $0\in K^m$ unter der Abbildung $\mathbf f_A$, d.h.

\[ \operatorname{Ker}A = \{ x \in K^n;\ Ax = 0 \} \]

Wir können die neuen Sprechweisen benutzen, um in prägnanter Form über lineare Gleichungssysteme zu sprechen (und später, um die Theorie der linearen Gleichungssysteme in natürlicher Weise in den allgemeinen Kontext einzuordnen):

Satz 5.46

Sei $A\in M_{m\times n}(K)$ eine Matrix.

Der Teilraum $\operatorname{Ker}(A)$ ist die Lösungsmenge des homogenen linearen Gleichungssystems mit Koeffizientenmatrix $A$.
Der Teilraum $\operatorname{Im}(A)$ ist die Menge aller $b\in K^m$, so dass das lineare Gleichungssystem mit erweiterter Koeffizientenmatrix $(A\mid b)$ eine Lösung besitzt.

Beweis

Beide Teile sind direkte Übersetzungen der Definitionen $\mathbf f_A(x) = Ax$, des Kerns und Bildes und der Tatsache, dass die Lösungsmenge des linearen Gleichungssystems mit erweiterter Koeffizientenmatrix $(A\mid b)$ die Menge $\{ x\in K^n;\ Ax=b\} $ ist.

Ein weiteres Indiz dafür, dass die Abbildungen der Form $\mathbf f_A$ gut zu den Strukturen passen, auf die wir beim Studium linearer Gleichungssysteme gestoßen sind, ist das folgende Lemma:

Lemma 5.47

Sei $A\in M_{m\times n}(K)$ eine Matrix. Dann gilt:

$\operatorname{Ker}(A)$ ist ein Teilraum von $K^n$,
$\operatorname{Im}(A)$ ist ein Teilraum von $K^m$.

Beweis

zu (1). Das folgt mit dem vorherigen Satz aus Lemma 5.26. Natürlich lässt sich die Aussage auch leicht direkt nachrechnen.

zu (2). Wegen $\mathbf f_A(0)=0$ ist $0\in \operatorname{Im}(\mathbf f_A)$. Sind $v,w\in \operatorname{Im}(\mathbf f_A)$, etwa $v = \mathbf f_A(v^\prime )$, $w = \mathbf f_A(w^\prime )$, so gilt

\[ v+w = \mathbf f_A(v^\prime ) + \mathbf f_A(w^\prime ) = Av^\prime + Aw^\prime = A(v^\prime + w^\prime ) = \mathbf f_A(v^\prime +w^\prime )\in \operatorname{Im}(\mathbf f_A). \]

Für $v = \mathbf f_A(v^\prime )$ und $a\in K$ gilt $av = aAv^\prime = A(av^\prime ) = \mathbf f_A(av^\prime )\in \operatorname{Im}(\mathbf f_A)$. Damit haben wir alle Teilraumbedingungen überprüft.

Wir können jetzt Frage 5.27 (2) als die Frage formulieren, ob wir beschreiben können, »wie groß« die Teilräume $\operatorname{Ker}(\mathbf f_A)$ und $\operatorname{Im}(\mathbf f_A)$ sind, und einen Zusammenhang dazwischen herstellen können.

Die Verknüpfung von Abbildungen der Form $\mathbf f_A$ ist gerade durch das Matrizenprodukt gegeben. Das liefert eine weitere Rechtfertigung für die Definition des Matrizenprodukts, so wie wir sie gegeben haben.

Satz 5.48

Seien $A\in M_{l\times m}(K)$, $B\in M_{m\times n}$. Dann gilt

\[ \mathbf f_A \circ \mathbf f_B = \mathbf f_{AB}. \]

Beweis

Dies folgt aus der Assoziativität des Matrizenprodukts, wie die folgende Rechnung zeigt:

\[ (\mathbf f_A \circ \mathbf f_B)(x) = \mathbf f_A(\mathbf f_B(x)) = A(Bx) = (AB)x = \mathbf f_{AB}(x) \]

für alle $x\in K^n$.

Beispiel 5.49

Sei $K=\mathbb R$. In diesem Fall kann man die Abbildungen $\mathbf f_A$ geometrisch interpretieren. Im Fall $n=2$ (und mit gewissen Grenzen im Fall $n=3$) kann man das auch graphisch gut veranschaulichen. In den Abbildungen unten ist jeweils die rote Figur das Bild der schwarzen Figur unter der betrachteten Abbildung.

Sei $A = \left( \begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array} \right)$. Dann gilt
\[ A\left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} x \\ -y \end{array} \right) \]
und diese Abbildung ist einfach die Spiegelung an der $x$-Achse.

$\begin{tikzpicture} \begin{scope} \draw [->, gray, thick] (-4.5*.5, 0) – (4.5*.5, 0); \draw [->, gray, thick] (0, -4.5*.5) – (0, 4.5*.5); \draw [gray] (-4*.5, -0.1) – (-4*.5, 0.1) node[black, below, yshift=-.1cm] {$-4$}; \draw [gray] (-2*.5, -0.1) – (-2*.5, 0.1) node[black, below, yshift=-.1cm] {$-2$}; \draw [gray] (2*.5, -0.1) – (2*.5, 0.1) node[black, below, yshift=-.1cm] {$2$}; \draw [gray] (4*.5, -0.1) – (4*.5, 0.1) node[black, below, yshift=-.1cm] {$4$}; \draw [gray] (-0.1, -4*.5) – (0.1, -4*.5) node[black, left, xshift=-.1cm] {$-4$}; \draw [gray] (-0.1, -2*.5) – (0.1, -2*.5) node[black, left, xshift=-.1cm] {$-2$}; \draw [gray] (-0.1, 2*.5) – (0.1, 2*.5) node[black, left, xshift=-.1cm] {$2$}; \draw [gray] (-0.1, 4*.5) – (0.1, 4*.5) node[black, left, xshift=-.1cm] {$4$}; \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick] (a) – (c) – (b); \draw [thick] (c) – (e); \draw [thick] (d) – (f); \draw [thick] (d) – (g); \draw [thick] (h) circle[radius=.3cm*.5]; \fill (f) circle[radius=.1cm*.5]; \fill (g) circle[radius=.1cm*.5]; \fill (i) circle[radius=.06cm*.5]; \fill (j) circle[radius=.06cm*.5]; \draw [thick] (k) arc (240:300:.15) ; \end{scope} \begin{scope} [cm={1, 0, 0, -1, (0,0)}] \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick, red] (a) – (c) – (b); \draw [thick, red] (c) – (e); \draw [thick, red] (d) – (f); \draw [thick, red] (d) – (g); \draw [thick, red] (h) circle[radius=.3cm*.5]; \fill [red] (f) circle[radius=.1cm*.5]; \fill [red] (g) circle[radius=.1cm*.5]; \fill [red] (i) circle[radius=.06cm*.5]; \fill [red] (j) circle[radius=.06cm*.5]; \draw [red, thick] (k) arc (240:300:.15) ; \end{scope} \end{tikzpicture}$
$\begin{tikzpicture} \begin{scope} \draw [->, gray, thick] (-4.5*.5, 0) – (4.5*.5, 0); \draw [->, gray, thick] (0, -4.5*.5) – (0, 4.5*.5); \draw [gray] (-4*.5, -0.1) – (-4*.5, 0.1) node[black, below, yshift=-.1cm] {$-4$}; \draw [gray] (-2*.5, -0.1) – (-2*.5, 0.1) node[black, below, yshift=-.1cm] {$-2$}; \draw [gray] (2*.5, -0.1) – (2*.5, 0.1) node[black, below, yshift=-.1cm] {$2$}; \draw [gray] (4*.5, -0.1) – (4*.5, 0.1) node[black, below, yshift=-.1cm] {$4$}; \draw [gray] (-0.1, -4*.5) – (0.1, -4*.5) node[black, left, xshift=-.1cm] {$-4$}; \draw [gray] (-0.1, -2*.5) – (0.1, -2*.5) node[black, left, xshift=-.1cm] {$-2$}; \draw [gray] (-0.1, 2*.5) – (0.1, 2*.5) node[black, left, xshift=-.1cm] {$2$}; \draw [gray] (-0.1, 4*.5) – (0.1, 4*.5) node[black, left, xshift=-.1cm] {$4$}; \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick] (a) – (c) – (b); \draw [thick] (c) – (e); \draw [thick] (d) – (f); \draw [thick] (d) – (g); \draw [thick] (h) circle[radius=.3cm*.5]; \fill (f) circle[radius=.1cm*.5]; \fill (g) circle[radius=.1cm*.5]; \fill (i) circle[radius=.06cm*.5]; \fill (j) circle[radius=.06cm*.5]; \draw [thick] (k) arc (240:300:.15) ; \end{scope} \begin{scope} [cm={0, 1, 1, 0, (0,0)}] \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick, red] (a) – (c) – (b); \draw [thick, red] (c) – (e); \draw [thick, red] (d) – (f); \draw [thick, red] (d) – (g); \draw [thick, red] (h) circle[radius=.3cm*.5]; \fill [red] (f) circle[radius=.1cm*.5]; \fill [red] (g) circle[radius=.1cm*.5]; \fill [red] (i) circle[radius=.06cm*.5]; \fill [red] (j) circle[radius=.06cm*.5]; \draw [red, thick] (k) arc (240:300:.15) ; \end{scope} \end{tikzpicture}$

Sei $A = \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right)$. Dann gilt
\[ A\left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} y \\ x \end{array} \right) \]
und diese Abbildung ist die Spiegelung an der Diagonalen. Jede Spiegelung an einer Ursprungsgeraden in $\mathbb R^2$ kann in der Form $\mathbf f_A$ dargestellt werden. Können Sie für eine gegebene Gerade $g= \{ (x,y)^t\in \mathbb R^2;\ ax+by=0\} $, $a,b\in \mathbb R$, die Matrix $A$ ausrechnen, für die $\mathbf f_A$ die Spiegelung an $g$ ist?
$\begin{tikzpicture} \begin{scope} \draw [->, gray, thick] (-4.5*.5, 0) – (4.5*.5, 0); \draw [->, gray, thick] (0, -4.5*.5) – (0, 4.5*.5); \draw [gray] (-4*.5, -0.1) – (-4*.5, 0.1) node[black, below, yshift=-.1cm] {$-4$}; \draw [gray] (-2*.5, -0.1) – (-2*.5, 0.1) node[black, below, yshift=-.1cm] {$-2$}; \draw [gray] (2*.5, -0.1) – (2*.5, 0.1) node[black, below, yshift=-.1cm] {$2$}; \draw [gray] (4*.5, -0.1) – (4*.5, 0.1) node[black, below, yshift=-.1cm] {$4$}; \draw [gray] (-0.1, -4*.5) – (0.1, -4*.5) node[black, left, xshift=-.1cm] {$-4$}; \draw [gray] (-0.1, -2*.5) – (0.1, -2*.5) node[black, left, xshift=-.1cm] {$-2$}; \draw [gray] (-0.1, 2*.5) – (0.1, 2*.5) node[black, left, xshift=-.1cm] {$2$}; \draw [gray] (-0.1, 4*.5) – (0.1, 4*.5) node[black, left, xshift=-.1cm] {$4$}; \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick] (a) – (c) – (b); \draw [thick] (c) – (e); \draw [thick] (d) – (f); \draw [thick] (d) – (g); \draw [thick] (h) circle[radius=.3cm*.5]; \fill (f) circle[radius=.1cm*.5]; \fill (g) circle[radius=.1cm*.5]; \fill (i) circle[radius=.06cm*.5]; \fill (j) circle[radius=.06cm*.5]; \draw [thick] (k) arc (240:300:.15) ; \end{scope} \begin{scope} [cm={0, 1, -1, 0, (0,0)}] \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick, red] (a) – (c) – (b); \draw [thick, red] (c) – (e); \draw [thick, red] (d) – (f); \draw [thick, red] (d) – (g); \draw [thick, red] (h) circle[radius=.3cm*.5]; \fill [red] (f) circle[radius=.1cm*.5]; \fill [red] (g) circle[radius=.1cm*.5]; \fill [red] (i) circle[radius=.06cm*.5]; \fill [red] (j) circle[radius=.06cm*.5]; \draw [red, thick] (k) arc (240:300:.15) ; \end{scope} \end{tikzpicture}$

Sei $A = \left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right)$. Dann gilt
\[ A\left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} -y \\ x \end{array} \right) \]
und diese Abbildung ist die Drehung um $90^\circ $ gegen den Uhrzeigersinn. Können Sie auch die Drehung um $180^\circ $ und um $270^\circ $ gegen den Uhrzeigersinn in der Form $\mathbf f_A$ für geeignete Matrizen $A$ darstellen? Wir werden später sehen, dass sich alle Drehungen um den Ursprung in der Form $\mathbf f_A$ darstellen lassen, siehe Beispiel 7.60.
Sei $A = \left( \begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array} \right)$. Dann gilt
\[ A\left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} x+2y \\ y \end{array} \right) \]
und diese Abbildung nennt man eine Scherung.

$\begin{tikzpicture} \begin{scope} \draw [->, gray, thick] (-4.5*.5, 0) – (4.5*.5, 0); \draw [->, gray, thick] (0, -4.5*.5) – (0, 4.5*.5); \draw [gray] (-4*.5, -0.1) – (-4*.5, 0.1) node[black, below, yshift=-.1cm] {$-4$}; \draw [gray] (-2*.5, -0.1) – (-2*.5, 0.1) node[black, below, yshift=-.1cm] {$-2$}; \draw [gray] (2*.5, -0.1) – (2*.5, 0.1) node[black, below, yshift=-.1cm] {$2$}; \draw [gray] (4*.5, -0.1) – (4*.5, 0.1) node[black, below, yshift=-.1cm] {$4$}; \draw [gray] (-0.1, -4*.5) – (0.1, -4*.5) node[black, left, xshift=-.1cm] {$-4$}; \draw [gray] (-0.1, -2*.5) – (0.1, -2*.5) node[black, left, xshift=-.1cm] {$-2$}; \draw [gray] (-0.1, 2*.5) – (0.1, 2*.5) node[black, left, xshift=-.1cm] {$2$}; \draw [gray] (-0.1, 4*.5) – (0.1, 4*.5) node[black, left, xshift=-.1cm] {$4$}; \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick] (a) – (c) – (b); \draw [thick] (c) – (e); \draw [thick] (d) – (f); \draw [thick] (d) – (g); \draw [thick] (h) circle[radius=.3cm*.5]; \fill (f) circle[radius=.1cm*.5]; \fill (g) circle[radius=.1cm*.5]; \fill (i) circle[radius=.06cm*.5]; \fill (j) circle[radius=.06cm*.5]; \draw [thick] (k) arc (240:300:.15) ; \end{scope} \begin{scope} [cm={1, 0, 2, 1, (0,0)}] \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick, red] (a) – (c) – (b); \draw [thick, red] (c) – (e); \draw [thick, red] (d) – (f); \draw [thick, red] (d) – (g); \draw [thick, red] (h) circle[radius=.3cm*.5]; \fill [red] (f) circle[radius=.1cm*.5]; \fill [red] (g) circle[radius=.1cm*.5]; \fill [red] (i) circle[radius=.06cm*.5]; \fill [red] (j) circle[radius=.06cm*.5]; \draw [red, thick] (k) arc (240:300:.15) ; \end{scope} \end{tikzpicture}$
Sei $A = \left( \begin{array}{cc} 2 & 0 \\ 0 & 2 \end{array} \right)$. Dann gilt
\[ A\left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} 2x \\ 2y \end{array} \right). \]
Diese Abbildung nennt man eine Streckung (um den Faktor $2$). Wie würden Sie die Abbildung $\mathbf f_A$ beschreiben, wenn $A = \left(\begin{array}{cc} a & 0 \\ 0 & a \end{array}\right)$ mit $a {\lt} 0$ ist? Was macht $\mathbf f_A$, wenn $A$ eine Diagonalmatrix mit verschiedenen Werten auf der Diagonale ist? Was passiert, wenn eine Null auf der Diagonale steht?

$\begin{tikzpicture} \begin{scope} \draw [->, gray, thick] (-4.5*.5, 0) – (4.5*.5, 0); \draw [->, gray, thick] (0, -4.5*.5) – (0, 4.5*.5); \draw [gray] (-4*.5, -0.1) – (-4*.5, 0.1) node[black, below, yshift=-.1cm] {$-4$}; \draw [gray] (-2*.5, -0.1) – (-2*.5, 0.1) node[black, below, yshift=-.1cm] {$-2$}; \draw [gray] (2*.5, -0.1) – (2*.5, 0.1) node[black, below, yshift=-.1cm] {$2$}; \draw [gray] (4*.5, -0.1) – (4*.5, 0.1) node[black, below, yshift=-.1cm] {$4$}; \draw [gray] (-0.1, -4*.5) – (0.1, -4*.5) node[black, left, xshift=-.1cm] {$-4$}; \draw [gray] (-0.1, -2*.5) – (0.1, -2*.5) node[black, left, xshift=-.1cm] {$-2$}; \draw [gray] (-0.1, 2*.5) – (0.1, 2*.5) node[black, left, xshift=-.1cm] {$2$}; \draw [gray] (-0.1, 4*.5) – (0.1, 4*.5) node[black, left, xshift=-.1cm] {$4$}; \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick] (a) – (c) – (b); \draw [thick] (c) – (e); \draw [thick] (d) – (f); \draw [thick] (d) – (g); \draw [thick] (h) circle[radius=.3cm*.5]; \fill (f) circle[radius=.1cm*.5]; \fill (g) circle[radius=.1cm*.5]; \fill (i) circle[radius=.06cm*.5]; \fill (j) circle[radius=.06cm*.5]; \draw [thick] (k) arc (240:300:.15) ; \end{scope} \begin{scope} [cm={2, 0, 0, 2, (0,0)}] \coordinate (a) at (0, 0); \coordinate (b) at (1.2*.5, 0); \coordinate (c) at (.6*.5, 1*.5); \coordinate (d) at (.6*.5, 2*.5); \coordinate (e) at (.6*.5, 2.3*.5); \coordinate (f) at (0, 1.3*.5); \coordinate (g) at (1.5*.5, 1.7*.5); \coordinate (h) at (.6*.5, 2.6*.5); \coordinate (i) at (.5*.5, 2.72*.5); \coordinate (j) at (.7*.5, 2.72*.5); \coordinate (k) at (.45*.5, 2.52*.5); \draw [thick, red] (a) – (c) – (b); \draw [thick, red] (c) – (e); \draw [thick, red] (d) – (f); \draw [thick, red] (d) – (g); \draw [thick, red] (h) circle[radius=.3cm*.5]; \fill [red] (f) circle[radius=.1cm*.5]; \fill [red] (g) circle[radius=.1cm*.5]; \fill [red] (i) circle[radius=.06cm*.5]; \fill [red] (j) circle[radius=.06cm*.5]; \draw [red, thick] (k) arc (240:300:.15) ; \end{scope} \end{tikzpicture}$

Wir werden die Abbildungen der Form $\mathbf f_A$ in Kapitel 7 genauer untersuchen und dann unter anderem charakterisieren können, welche Abbildungen $K^n\to K^m$ in dieser Art beschrieben werden können.

5.3.4 Invertierbare Matrizen

Wir haben schon besprochen, dass elementare Zeilenumformungen sich als Multiplikation mit einer Matrix von links beschreiben lassen, und dass sie umkehrbar sind. Wenn $S$ die Matrix zu einer elementaren Zeilenumformung von $A$ ist, dann gibt es eine Matrix $S^\prime $, die ebenfalls eine elementare Zeilenumformung beschreibt, so dass $S^\prime S A=A$. Das führt uns auf die folgende Definition:

Definition 5.50

Eine quadratische Matrix $A\in M_{n\times n}(K)$ heißt invertierbar, wenn eine Matrix $B\in M_{n\times n}(K)$ existiert mit

\[ AB = BA = E_n. \]

Lemma 5.51

Sei $A\in M_{n\times n}(K)$ eine invertierbare Matrix. Dann gibt es genau eine Matrix $B\in M_{n\times n}(K)$ mit $AB=BA=E_n$. Wir bezeichnen sie mit $A^{-1}$ und nennen sie die zu $A$ inverse Matrix . Es ist dann auch $B$ invertierbar, und $B^{-1} =A$.

Beweis

Seien $B$ und $B^\prime $ gegeben mit $AB = B^\prime A = E_n$. (Wir brauchen also jeweils nur die eine Hälfte der definierenden Eigenschaft, allerdings einmal die Rechts- und einmal die Linksversion.) Dann gilt

\[ B = E_nB = (B^\prime A)B = B^\prime (AB) = B^\prime E_n = B^\prime . \]

Der zweite Teil der Behauptung ist dann klar.

Wenn die Matrix $A$ invertierbar ist, dann können wir aus dem Ergebnis $C = AB$ einer Matrizenmultiplikation die Matrix $B$ zurückgewinnen: $B = A^{-1} C$. Insbesondere gilt: Ist $A$ invertierbar und $Ax=b$ ein lineares Gleichungssystem, so ist dieses eindeutig lösbar und die Lösung ist $A^{-1}b$. Allerdings ist es selten sinnvoll, $A^{-1}$ auszurechnen, wenn man nur ein lineares Gleichungssystem mit Koeffizientenmatrix $A$ lösen möchte.

Lemma 5.52

Seien $A, B\in M_n(K)$ invertierbar. Dann ist auch das Produkt $AB$ invertierbar und es gilt

\[ (AB)^{-1} = B^{-1} A^{-1}. \]

Beweis

Es gilt $(AB) (B^{-1} A^{-1}) = E_n = (B^{-1} A^{-1})(AB)$.

Beispiel 5.53

Wir benutzen die Notation von Bemerkung 5.37. Sei $K$ ein Körper, $n\in \mathbb N$, $1\le i,j\le n$, $i\ne j$, $a\in K$.

Es gilt $E_{ij}(a)^{-1} = E_{ij}(-a)$.
Es gilt $P_{ij}^{-1} = P_{ij}$.
Eine Diagonalmatrix $\operatorname{diag}(a_1, \dots , a_n)$ mit $a_i\in K$ ist genau dann invertierbar, wenn $a_i\ne 0$ für alle $i=1,\dots , n$ gilt. In diesem Fall ist

\[ \operatorname{diag}(a_1, \dots , a_n)^{-1} = \operatorname{diag}(a_1^{-1}, \dots , a_n^{-1}) \]

Insbesondere ist für $a\ne 0$: $\operatorname{diag}(1, \dots , 1, a, 1, \dots , 1)^{-1} = \operatorname{diag}(1, \dots , 1, a^{-1}, 1, \dots , 1)$.

Wir sehen erneut, dass elementare Zeilenumformungen die Lösungsmenge des zugehörigen homogenen linearen Gleichungssystems nicht ändern, denn für jede invertierbare Matrix $S$ ist $Ax=0$ äquivalent zu $SAx=0$.

Satz 5.54

Seien $K$ ein Körper, $n\in \mathbb N$ und $A\in M_n(K)$. Dann sind äquivalent:

Die Matrix $A$ ist invertierbar.
Die reduzierte Zeilenstufenform von $A$ ist $E_n$.

Erinnern Sie sich, dass wir in Korollar 5.22 die Eigenschaft von $A$, reduzierte Zeilenstufenform $E_n$ zu haben, in Termen von linearen Gleichungssystemen umgeschrieben haben. Dies werden wir im Beweis des Satzes benutzen.

Beweis

Wenn $A$ invertierbar ist, dann ist $Ax=0$ äquivalent zu $x = A^{-1}0 = 0$, das homogene lineare Gleichungssystem zu $A$ ist daher eindeutig lösbar. Aus Korollar 5.22 folgt, dass $A$ reduzierte Zeilenstufenform $E_n$ hat.

Nun habe $A$ reduzierte Zeilenstufenform $E_n$. Dann gibt es elementare Zeilenumformungen, die $A$ in die Einheitsmatrix umformen. Wir können diese als Multiplikation mit Matrizen $S_1, S_2, \dots , S_l$ ausdrücken:

\[ S_l S_{l-1} \cdots S_1 A = E_n. \]

Wir haben in Beispiel 5.53 gesehen, dass alle $S_i$ invertierbar sind. Also können wir mit ihren Inversen von links multiplizieren und erhalten

\[ A = S_1^{-1} S_2^{-1} \cdots S_l^{-1} E_n. \]

Die rechte Seite ist invertierbar und genauer erhalten wir

\[ A^{-1} = S_l \cdots S_1. \]

Wenn wir am Schluss das Beweises $A^{-1} = S_l \cdots S_1E_n$ schreiben, dann liefert uns dies direkt einen Algorithmus, um $A^{-1}$ zu berechnen: Wenn wir $A$ durch elementare Zeilenumformungen, die durch die Matrizen $S_1$, …, $S_l$ beschrieben werden, auf die Einheitsmatrix bringen können, dann bringen genau dieselben Zeilenumformungen die Einheitsmatrix auf die Matrix $A^{-1}$.

Beispiel 5.55

Um das Verfahren zum bestimmen des Inversen einer Matrix $A\in M_n(K)$ in der Praxis durchzuführen, schreibt man $A$ und $E_n$ nebeneinander in eine $(n\times 2n)$-Matrix. Etwas übersichtlicher wird es, wenn man in der Mitte einen senkrechten Strich mitführt. Dann bringt man mit elementaren Zeilenumformungen die Matrix $A$ auf reduzierte Zeilenstufenform und führt die Umformungen immer für die gesamte Matrix durch. Ist das Ergebnis der reduzierten Zeilenstufenform von $A$ die Einheitsmatrix, dann ist $A$ invertierbar, und die rechte Hälfte der so erhaltenen Matrix ist $A^{-1}$. Erhält man eine andere Matrix als $E_n$ als reduzierte Zeilenstufenform von $A$, so ist die Matrix $A$ nicht invertierbar.

Ein konkretes Beispiel: Sei $K=\mathbb Q$, $n=3$ und

\[ A = \left( \begin{array}{ccc} 1 & 1 & 0 \\ 2 & 0 & 1 \\ 3 & 1 & 0 \end{array} \right). \]

Wir bringen nun in der Matrix

\[ (A\mid E_3) = \left( \begin{array}{ccc|ccc} 1 & 1 & 0 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 & 1 & 0\\ 3 & 1 & 0 & 0 & 0 & 1 \end{array} \right) \]

die linke Hälfte durch elementare Zeilenumformungen auf reduzierte Zeilenstufenform:

\begin{align*} & \left( \begin{array}{ccc|ccc} 1 & 1 & 0 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 & 1 & 0\\ 3 & 1 & 0 & 0 & 0 & 1 \end{array} \right)\xrightarrow {Z_2 \rightsquigarrow Z_2 - 2Z_1,\ Z_3 \rightsquigarrow Z_3 - 3 Z_1}\\ & \left( \begin{array}{ccc|ccc} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & -2 & 1 & -2 & 1 & 0\\ 0 & -2 & 0 & -3 & 0 & 1 \end{array} \right)\xrightarrow {Z_3 \rightsquigarrow Z_3 -Z_2,\ Z_2 \rightsquigarrow -\frac12 Z_2}\\ & \left( \begin{array}{ccc|ccc} 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & -\frac12 & 1 & -\frac12 & 0\\ 0 & 0 & -1 & -1 & -1 & 1 \end{array} \right)\xrightarrow {Z_3 \rightsquigarrow -Z_3,\ Z_2 \rightsquigarrow Z_2 + \frac12 Z_3,\ Z_1 \rightsquigarrow Z_1 - Z_2}\\ & \left( \begin{array}{ccc|ccc} 1 & 0 & 0 & -\frac12 & 0 & \frac12 \\ 0 & 1 & 0 & \frac32 & 0 & -\frac12\\ 0 & 0 & 1 & 1 & 1 & -1 \end{array} \right) \end{align*}

Wir erhalten

\[ A^{-1} = \left( \begin{array}{ccc} -\frac12 & 0 & \frac12 \\ \frac32 & 0 & -\frac12\\ 1 & 1 & -1 \end{array} \right). \]

Es bietet sich bei dieser Rechnung an, die Probe durchzuführen: Das Produkt $AA^{-1}$ muss die Einheitsmatrix ergeben.

Beispiel 5.56

Seien $K$ ein Körper und $A=\left( \begin{array}{cc} a & b \\ c & d \end{array} \right)$ eine $2\times 2$-Matrix.

Wir setzen $\delta (A) = ad-bc$. Wir haben in Abschnitt 2.5 gesehen, dass das homogene lineare Gleichungssystem zu $A$ genau dann eindeutig lösbar ist, wenn $\delta (A)\ne 0$ gilt. Aus Satz 5.54 und Korollar 5.22 folgt damit, dass

\[ A\ \text{ist invertierbar}\quad \Longleftrightarrow \quad \delta (A)\ne 0. \]

In diesem Fall gilt

\[ A^{-1} = \frac{1}{\delta (A)} \left( \begin{array}{cc} d & -b \\ -c & a \end{array} \right). \]

Um das zu sehen, muss man nur nachrechnen, dass $AA^{-1} = E_2$ gilt, und das ist eine leichte Rechnung.

Den Ausdruck $\delta (A)$ nennt man auch die Determinante der Matrix $A$ (und später schreiben wir $\det (A)$ statt $\delta (A)$). Siehe Kapitel 9 für eine systematische Diskussion und die Verallgemeinerung auf quadratische Matrizen beliebiger Größe.

Lemma 5.57

Sei $A\in M_{n\times n}(K)$ eine invertierbare Matrix. Dann ist auch die transponierte Matrix $A^t$ invertierbar, und es gilt

\[ (A^t)^{-1} = (A^{-1})^t. \]

Beweis

Wir haben $A^t (A^{-1})^t = (A^{-1}A)^t = E_n^t = E_n$ nach Lemma 5.40, analog $(A^{-1})^t A^t = E_n$, und zusammen das zeigt die Behauptung.

Das folgende Korollar ist tiefliegender als es erscheinen mag. Wir werden auf diese Aussage später wieder zurückkommen (und einen anderen Beweis geben), siehe Korollar 7.24.

Korollar 5.58

Sei $A\in M_{n\times n}(K)$ eine Matrix.

Wenn eine Matrix $B\in M_{n\times n}(K)$ existiert mit $AB=E_n$, dann ist $A$ invertierbar und $A^{-1} = B$.
Wenn eine Matrix $B\in M_{n\times n}(K)$ existiert mit $BA=E_n$, dann ist $A$ invertierbar und $A^{-1} = B$.

Beweis

zu (1). Es genügt zu zeigen, dass $A$ invertierbar ist; es ist dann klar, dass $B=A^{-1}$ gelten muss. Für die Invertierbarkeit genügt es wegen Satz 5.54 und Korollar 5.22 zu zeigen, dass das lineare Gleichungssystem $Ax=b$ für alle $b\in K^n$ lösbar ist. Das folgt aber unmittelbar aus der Voraussetzung, denn wir setzen einfach $x = Bb$ und erhalten $Ax = A(Bb) = E_n b= b$.

zu (2). Für diesen Teil können wir wieder Satz 5.54 und Korollar 5.22 anwenden und zeigen diesmal, dass das homogene lineare Gleichungssystem $Ax=0$ eindeutig lösbar ist. In der Tat, ist $x\in K^n$ mit $Ax = 0$, so folgt $x = E_n x = B A x = 0$.

Alternativ kann man Teil (2) aus Teil (1) (oder auch umgekehrt) durch den Übergang zu den transponierten Matrizen erhalten.

Wir können nun auch noch einmal auf die Eindeutigkeit der reduzierten Zeilenstufenform zurückkommen:

Satz 5.59

Die reduzierte Zeilenstufenform einer Matrix $A\in M_{m\times n}(K)$ ist eindeutig bestimmt, also unabhängig von der Wahl der elementaren Zeilenumformungen.

Beweis

Seien $A^\prime $ und $A^{\prime \prime }$ Matrizen in reduzierter Zeilenstufenform, die beide aus $A$ durch elementare Zeilenumformungen erhalten werden können. Dann gibt es invertierbare Matrizen $S^\prime $ und $S^{\prime \prime }$ mit $A^\prime = S^{\prime }A$ und $A^{\prime \prime } = S^{\prime \prime }A$, also

\[ A^\prime = S^\prime (S^{\prime \prime })^{-1} A^{\prime \prime }. \]

Wir bezeichnen mit $B$ die Matrix, die aus den Spalten von $A^{\prime }$ besteht, die eine führende Eins enthalten. Alle anderen Spalten lassen wir weg. Ist $r$ die Anzahl der führenden Einsen in $A^\prime $, so ist $B\in M_{m\times r}(K)$. Wir wissen bereits, dass sich in $A^{\prime }$ und $A^{\prime \prime }$ die Spalten mit führenden Einsen an denselben Positionen befinden (Satz 5.17). Deshalb erhalten wir genau dasselbe Ergebnis, wenn wir $B$ in der gleichen Art und Weise aus $A^{\prime \prime }$ statt aus $A^{\prime }$ konstruieren, und es folgt

\[ B = S^{\prime } (S^{\prime \prime })^{-1} B. \]

Die Matrix $B$ hat eine sehr einfache Form, es handelt sich um eine Blockmatrix, die aus der Einheitsmatrix $E_r$ und der Nullmatrix der Größe $(m-r)\times r$ zusammengesetzt ist: $B=\left( \begin{array}{c} E_r \\ 0 \end{array}\right)$ (und die Zeilen unterhalb der $r$-ten Zeilen sind auch in $A^{\prime }$ und $A^{\prime \prime }$ Nullzeilen).

Die Gleichheit $B = S^{\prime } (S^{\prime \prime })^{-1} B$ übersetzt sich damit in

\[ S^{\prime } (S^{\prime \prime })^{-1} =\left(\begin{array}{cc} E_r & \ast \\ 0 & \ast \end{array}\right), \]

wobei das obere Sternchen eine Matrix in $M_{r\times (m-r)}(K)$ und das untere eine in $M_{(m-r)\times (m-r)}(K)$ bezeichnen, über die wir nichts Genaueres zu sagen brauchen.

Weil die Zeilen unterhalb der $r$-ten Zeile in $A^{\prime }$ und $A^{\prime \prime }$ sowieso Nullzeilen sind, genügt es zu zeigen, dass die ersten $r$ Zeilen übereinstimmen. Wir schreiben (nur für diesen Beweis) $M_{\le r}$ für die Matrix, die aus den ersten $r$ Zeilen der Matrix $M$ besteht. Dann haben wir

\[ (A^\prime )_{\le r} = (S^\prime (S^{\prime \prime })^{-1} A^{\prime \prime })_{\le r} = (S^\prime (S^{\prime \prime })^{-1})_{\le r}\, A^{\prime \prime } = \left(\begin{array}{cc} E_r & \ast \end{array}\right) \left( \begin{array}{c} (A^{\prime \prime })_{\le r} \\ 0 \end{array} \right) = (A^{\prime \prime })_{\le r}, \]

wobei wir ausgiebig von der Schreibweise als Blockmatrizen Gebrauch gemacht haben (Abschnitt 5.3.2 und Lemma 5.41).

5.3.5 Ergänzungen *

Beispiel 5.60

Wir betrachten die Folge $(F_n)_{n\ge 0}$ der Fibonacci Zahlen, die definiert ist durch

\[ F_0 = 0, \quad F_1=1,\quad F_{n} = F_{n-1} + F_{n-2},\ n\ge 2. \]

Wir können die rekursive Definition durch die folgenden Matrixgleichungen formulieren:

\[ \left( \begin{array}{c} F_1 \\ F_0 \end{array} \right) = \left( \begin{array}{c} 1 \\ 0 \end{array} \right),\qquad \left( \begin{array}{c} F_n \\ F_{n-1} \end{array} \right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) \cdot \left( \begin{array}{c} F_{n-1} \\ F_{n-2} \end{array} \right). \]

Setzen wir

\[ A = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right), \]

so erhalten wir dadurch

\[ \left( \begin{array}{c} F_{n+1} \\ F_{n} \end{array} \right) = A^{n} \left( \begin{array}{c} 1 \\ 0 \end{array} \right). \]

Dies kann man ausnutzen, um »schnell« eine Fibonacci-Zahl $F_n$ für großes $n$ zu berechnen, ohne alle vorherigen Fibonacci-Zahlen berechnen zu müssen. Denn die Potenz $A^{n}$ kann man in wesentlich weniger als $n$ Schritten ausrechnen: Wir schreiben $n = \sum _{i=0}^r a_i\cdot 2^i$ mit $a_i\in \{ 0, 1\} $, $a_r \ne 0$ (dies ist die Binärdarstellung der Zahl $n$). Zuerst berechnet man $A^2$, dann $A^4 = A^2 \cdot A^2$, und alle weiteren Potenzen $A^{2^i}$ für $i\le r$. Dies erfordert nur $r$ Matrixmultiplikationen. Dann berechnen wir $A^{n-1}$ als Produkt derjenigen Matrizen $A^{2^i}$, für die $a_i = 1$ ist.

Ist zum Beispiel $n = 16781841 = 2^{24} + 2^{12} + 2^9 + 2^4 + 2^0$, so brauchen wir mit diesem Rezept für die Berechnung von $F_n$ nur 28 Produkte von $(2\times 2)$-Matrizen auszurechnen. Das wäre notfalls noch per Hand machbar (im Gegensatz zu $n$ Additionen, die bei einer Geschwindigkeit von einer Addition pro Sekunde fast 200 Tage dauern würden – wenn Sie rund um die Uhr addieren).

Die Darstellung mithilfe der Matrix $A$ kann man auch benutzen, um Identitäten zwischen verschiedenen Gliedern der Fibonacci-Folge herzuleiten. Dazu bemerken wir zunächst, dass für $n\ge 1$

\[ A^n = \left( \begin{array}{cc} F_{n+1} & F_n \\ F_{n} & F_{n-1} \end{array} \right), \]

wie man unmittelbar per Induktion nachprüft. Damit folgt zum Beispiel für $m, n\ge 1$ aus der Gleichheit $A^{m+n} = A^m A^n$, dass

\[ \left( \begin{array}{cc} F_{m+n+1} & F_{m+n} \\ F_{m+n} & F_{m+n-1} \end{array} \right) = A^m A^n = \left( \begin{array}{cc} F_{m+1} & F_m \\ F_{m} & F_{m-1} \end{array} \right) \left( \begin{array}{cc} F_{n+1} & F_n \\ F_{n} & F_{n-1} \end{array} \right). \]

Nehmen wir nun auf beiden Seiten den Eintrag in der zweiten Zeile und ersten Spalte, so erhalten wir die Formel

\[ F_{m+n} = F_m F_{n+1} + F_{m-1}F_n. \]

Durch Spezialisierung erhält man viele verschiedene Identitäten zwischen den Fibonacci-Zahlen, zum Beispiel für $m=n$: $F_{2n} = (F_{n+1} + F_{n-1}) F_n$.

Ergänzung 5.61 Der Page-rank-Algorithmus, Fortsetzung

Dies ist die Fortsetzung der Diskussion aus Frage 2.7. Wir bezeichnen wie dort mit $x_i$, $i=1,\dots , N$, die Zahlen die wir suchen, um die »Relevanz« von Webseiten zu beschreiben, mit $L_i$ die Menge aller Seiten, die einen Link auf Seite $i$ enthalten, und mit $n_j$ die Zahl der von Seite $j$ ausgehenden Links. Wir arbeiten über dem Körper $K=\mathbb R$.

Der aktuelle Diskussionsstand ist, dass die $x_i$ das lineare Gleichungssystem

\[ x_i = \sum _{j\in L_i} \frac{1}{n_j} x_j,\qquad i=1,\dots , N, \]

erfüllen sollen.

Wir suchen eine Lösung, in der $0 \le x_i {\lt} 1$ für alle $i$ und $\sum x_i = 1$ gilt, und zwar sollte es genau eine Lösung mit dieser Eigenschaft geben. Durch die Zusatzeigenschaften können wir die $x_i$ auch als Wahrscheinlichkeit deuten, dass jemand, der im Internet surft und immer zufällig irgendeinem Link folgt, sich gerade auf der Seite $i$ befindet.

Sei $H$ die Matrix mit Einträgen

\[ H_{ij} = \begin{cases} \frac{1}{n_j} & j\in L_i, \\ 0 & \text{sonst}. \end{cases} \]

Dann können wir das obige lineare Gleichungssystem schreiben als $(H-E_N)x = 0$, wobei $x = (x_i)_i\in K^N$.

Es gibt noch zwei »offensichtliche« Probleme mit diesem Ansatz:

Es lassen sich leicht Beispiele finden, in denen dieses homogene lineare Gleichungssystem keine nicht-triviale Lösung hat, und zwar dann, wenn es Seiten gibt, die gar keine Links enthalten. Zum Beispiel ein »Internet« mit drei Seiten und den Links $1\to 2$, $2\to 1$, $2\to 3$. In diesem Fall würde der Ansatz scheitern.

Wir wollen dieses Problem so lösen, dass wir in jeder Nullspalte der Matrix $H$ alle Einträge durch $\frac1N$ ersetzen. Mit der Interpretation als Wahrscheinlichkeiten können wir uns das so vorstellen, dass die Surfer∗in von einer Seite, die keine Links enthält, zufällig irgendeine Seite im Netz auswählt, und allen Seiten dieselbe Wahrscheinlichkeit zugewiesen wird.

Wenn wir $H$ so abändern:

\[ H_{ij} = \begin{cases} \frac{1}{n_j} & j\in L_i, \\ \frac1N & \text{wenn kein}\ i^\prime \ \text{existiert mit}\ j\in L_{i^\prime },\\ 0 & \text{sonst,} \end{cases} \]

dann hat die Matrix $H$ die Eigenschaft, dass alle Spaltensummen in $H$ gleich $1$ sind, d.h. $\sum _{i=1}^N H_{ij} = 1$ für alle $j$.

In den Spalten, die vorher Nullspalten waren, ist das klar, weil nun dort alle $N$ Einträge den Wert $\frac1N$ haben. In den anderen Spalten ist die Spaltensumme $\sum \frac{1}{n_j}$, wobei über alle $i$ mit $j\in L_i$ summiert wird, also über alle Seiten $i$, auf die die Seite $j$ verlinkt, und nach Definition gibt es genau $n_j$ solche Seiten.
Stellen Sie sich vor, dass das »Netz« von Webseiten, das wir betrachten, verschiedene Komponenten hat, zwischen denen man nicht durch Links hin- und hergelangen kann:

$\begin{tikzpicture} [>=Stealth] \graph[simple necklace layout, nodes={circle,minimum size=.7cm,draw}, node sep=1cm]{ 1,2,6,4,5,3,7; 1->[xshift=1pt,yshift=2pt]3; 3 ->[xshift=-1pt,yshift=-2pt]1; 6 ->[xshift=-1pt,yshift=-2pt] 4; 5 ->[xshift=-1pt,yshift=2pt] 4 ->[xshift=1pt,yshift=2pt] 6; 5 -> 2; 2 -> 4; 1 -> 7 -> 3; 6 -> 5; }; \end{tikzpicture}$

In diesem Fall ist es klar, dass die gegebenen Daten keinen vernünftigen Anhaltspunkt liefern, um die Relevanz von Seiten, die in verschiedenen solchen Komponenten liegen, zu vergleichen. Das Internet hat sehr viele Komponenten, so dass man dieses Problem nicht einfach ignorieren kann.

Der Trick, mit dem wir uns (bzw. Google sich) behelfen, ist dass wir die Matrix $H$ ersetzen durch die Matrix

\[ G:= dH + (1-d)A, \]

wobei $A$ die Matrix ist, deren Einträge alle gleich $\frac1N$ sind, und wobei $d$ eine Zahl ist, die zwischen $0$ und $1$ liegt. Je näher $d$ bei $1$ liegt, desto geringer ist der Unterschied zwischen $G$ und $H$. Interessanterweise ist es für die Qualität des Algorithmus aber sogar hilfreich, $d$ nicht zu nahe bei $1$ zu wählen. Google hat ursprünglich den Wert $d = 0,85$ benutzt.

Das passt auch gut zur Interpretation der $x_i$ als Aufenthaltswahrscheinlichkeiten: Es bedeutet, dass die Surfer∗in mit Wahrscheinlichkeit $1-d$ (also im Beispiel 15%) nicht einem Link auf der Seite folgt, sondern auf irgendeine zufällige Seite im Netz springt.

Wir haben damit die endgültige mathematische Formulierung des Page-Rank-Algorithmus erhalten: Wir möchten das lineare Gleichungssystem $(G-E_N) x = 0$ lösen. In der Matrix $G$ (der »Google-Matrix«) sind alle Einträge positiv, und die Spaltensummen sind alle gleich $1$. Während das nützliche Eigenschaften der Matrix $G$ sind, ist andererseits diese Matrix extrem groß, so groß, dass es aussichtslos ist, einfach den Gauß-Algorithmus auszuführen.

Wir werden später sehen, dass die Lösungsmenge des homogenen linearen Gleichungssystems $(G-E_N)x = 0$ aus den Vielfachen eines einzigen Vektors $x\ne 0$ besteht. Bis auf Skalieren gibt es also eine eindeutig bestimmte Lösung. Genauer werden wir den folgenden Satz beweisen (vergleiche Beispiel 2.8):

Satz 5.62

Es gibt genau eine Lösung $x\in \mathbb R^N$ des linearen Gleichungssystems $(G-E_N)x =0$ mit der Eigenschaft $\sum _{i=1}^N x_i = 1$, und für diese Lösung gilt $0 \le x_i \le 1$ für alle $i$.

(Ist $x^\prime \in K^N$ ein Element, das auch $(G-E_N)x^\prime = 0$ erfüllt, so existiert $\lambda \in \mathbb R$ mit $x^\prime =\lambda x$.)

Den Beweis geben wir wie gesagt später, siehe Korollar 7.70. Dass eine nicht-triviale Lösung existiert, ist jedenfalls leicht zu sehen. Weil die Spaltensummen von $F$ alle $=1$ sind, sind alle Spaltensummen von $G-E_N$ gleich Null. Addieren wir nacheinander die erste, zweite, …, $(N-1)$-te Zeile zur letzten Zeile von $G-E_N$, so entsteht also dort eine Nullzeile. Dies sind elementare Zeilenumformungen, die die Lösungsmenge des zugehörigen linearen Gleichungssystems nicht ändern, und da eine Nullzeile existiert, muss es in der (reduzierten) Zeilenstufenform eine Spalte ohne führende Eins geben.

Ergänzung 5.63 Bildkompression

In dieser Ergänzung besprechen wir eine Methode der Bildkompression mit dem sogenannten Haar-Wavelet. Wir beschränken uns darauf, die Grundidee zu erklären. In der Praxis kann man das Verfahren noch weiter verbessern. Es gibt auch andere sehr gute Kompressionsverfahren, die auf linearer Algebra beruhen, zum Beispiel auf der Singulärwertzerlegung, die wir in der Linearen Algebra 2 kennenlernen werden.

Um das Prinzip zu erläutern und zu illustrieren, beschränken wir uns auf ein Schwarz-Weiß-Bild. Man kann aber genau dieselbe Überlegung auf Farbbilder anwenden, indem man das Bild in mehrere Farben aufspaltet, beispielsweise in Rot, Grün und Blau (RGB), und dann die drei Farben separat behandelt.

Wir betrachten ein Bild (Abbildung 5.1) mit $512 \times 512$ Punkten (»Pixeln«), die jeweils einen Grauwert haben, der durch eine natürliche Zahl zwischen $0$ und $255$ gegeben ist. Dabei ist $0$ gleich schwarz, und $255$ ist gleich weiß. Um die Bildinformation in dieser vollständigen Form abzuspeichern, müssen also ca. $260\, 000$ dieser Grauwerte abgespeichert werden, jeder Wert benötigt ein »Byte« an Speicherplatz. Insgesamt brauchen wir also ca. $260$ Kilobyte für dieses Bild, wenn keine Kompression angewandt wird. (Nehmen Sie statt dieses kleinen Beispiels ein Bild mit beispielsweise 8MP und 3 Farben, so bräuchte man $24$ Megabyte, um das Bild abzuspeichern.)

\includegraphics[width=7cm]{figures/buecher} — Abbildung 5.1 Das Originalfoto

$\includegraphics[width=3.5cm]{figures/detail-orig}$

Die Grundidee vieler Kompressionsverfahren ist es, auszunutzen, dass es in einem typischem Bild viele Bereiche gibt, die mehr oder weniger einfarbig sind, d.h. benachbarte Punkte haben sehr ähnliche Farbwerte bzw. in unserem Fall Grauwerte. Für das hier vorgestellte Verfahren teilen wir das Bild in Blöcke von $8\times 8$ Pixeln auf und behandeln jeden Block einzeln. Ein vergrößerter $8\times 8$-Block aus dem Originalbild ist hier dargestellt.

Wir nehmen nun einen dieser Blöcke her und beginnen damit, die erste Zeile des Blocks folgendermaßen umzuformen: Wir fassen die $8$ Werte als $4$ Paare auf, d.h. die ersten beiden Einträge bilden das erste Paar, der dritte und vierte Eintrag das zweite Paar, usw. Für jedes dieser Paare $(a,b)$ bilden wir den Durchschnitt $\frac{a+b}{2}$ und den Wert $\frac{a-b}{2}$. Aus diesen Werten kann man $a$ und $b$ zurückgewinnen als

\[ a = \frac{a+b}{2} + \frac{a-b}{2}, \quad b = \frac{a+b}{2} - \frac{a-b}{2}, \]

aber diese Ersetzung hat für uns den Vorteil, dass tendenziell oft $\frac{a-b}{2}$ eine kleine Zahl sein wird (sogar gleich Null, wenn $a=b$), weil typischerweise $a$ und $b$ nahe beieinander liegen. Wir schreiben das Ergebnis wieder als eine Zeile mit $8$ Einträgen, wobei wir zuerst die $4$ Durchschnittswerte aufschreiben, und dann die $4$ Terme der zweiten Form.

Mit anderen Worten: Wir ersetzen die Zeile $v = (v_1, \dots , v_8)$ durch

\[ \left( \frac{v_1+v_2}{2}, \frac{v_3+v_4}{2}, \frac{v_5+v_6}{2}, \frac{v_7+v_8}{2}, \frac{v_1-v_2}{2}, \frac{v_3-v_4}{2}, \frac{v_5-v_6}{2}, \frac{v_7-v_8}{2} \right) \]

\includegraphics[width=3.5cm]{figures/detail-1} — Abbildung 5.2 Das Ergebnis, das aus dem vorher gezeigten Block von $8\times 8$ Pixeln wird, wenn alle Werte ${\lt} 1$, bzw. ${\lt} 4$, bzw. ${\lt} 10$, bzw. ${\lt} 18$ auf Null gesetzt werden.

\includegraphics[width=3.5cm]{figures/detail-4} — Abbildung 5.2 Das Ergebnis, das aus dem vorher gezeigten Block von $8\times 8$ Pixeln wird, wenn alle Werte ${\lt} 1$, bzw. ${\lt} 4$, bzw. ${\lt} 10$, bzw. ${\lt} 18$ auf Null gesetzt werden.

Das können wir auch als ein Matrizenprodukt ausdrücken: Wir ersetzen den Zeilenvektor $v$ durch das Produkt $vH_1$, wobei

\[ H_1 = \left( \begin{array}{rrrrrrrr} 0,5 & & & 0,5 \\ 0,5 & & & -0,5 \\ & 0,5 & & & 0,5 \\ & 0,5 & & & -0,5 \\ & & 0,5 & & & 0,5 \\ & & 0,5 & & & -0,5 \\ & & & 0,5 & & & 0,5 \\ & & & 0,5 & & & -0,5 \\ \end{array} \right) \]

Im zweiten Schritt wenden wir dasselbe Verfahren noch einmal auf die ersten $4$ Einträge der neuen Zeile an: Wir teilen diese in zwei Paare auf, und schreiben dann an die ersten beiden Stellen die Durchschnittswerte des ersten und zweiten Paares, und an die dritte und vierte Stelle die Hälfte der Differenzen. Auch dies können wir als Produkt mit einer Matrix ausdrücken, und zwar mit

\[ H_2 = \left( \begin{array}{rrrrrrrr} 0,5 & & 0,5 \\ 0,5 & & -0,5 \\ & 0,5 & & 0,5 \\ & 0,5 & & -0,5 \\ & & & & 1 \\ & & & & & 1 \\ & & & & & & 1 \\ & & & & & & & 1 \\ \end{array} \right) \]

Zum Schluss machen wir das ganze noch einmal für die ersten beiden Einträge der neuen Zeile, das heißt wir multiplizieren mit

\[ H_3 = \left( \begin{array}{rrrrrrrr} 0,5 & 0,5 \\ 0,5 & -0,5 \\ & & 1\\ & & & 1\\ & & & & 1 \\ & & & & & 1 \\ & & & & & & 1 \\ & & & & & & & 1 \\ \end{array} \right) \]

Insgesamt ersetzen wir also $v$ durch $vH_1H_2H_3$. Setzen wir $H:=H_1H_2H_3$, so wird $v$ durch $vH$ ersetzt. Für die anderen Zeilen machen wir dasselbe, das bedeutet, dass wir den Block $A$, aufgefasst als $(8\times 8)$-Matrix, ersetzen durch $AH$. Wie oben erwähnt, lässt sich diese Operation auch wieder umkehren (bis jetzt haben wir also keine Information verloren): die Umkehrung erhält man durch Multiplikation mit der inversen Matrix $H^{-1}$.

\includegraphics[width=7cm]{figures/im-1-180272} — Abbildung 5.3 Von links oben nach rechts unten die »komprimierten« Fotos, wo alle Werte ${\lt} 1$, bzw. ${\lt} 4$, bzw. ${\lt} 10$, bzw. ${\lt} 18$ auf $0$ gesetzt wurden. Damit wurden ca. $68\% $, bzw. $86\% $, bzw. $93\% $, bzw. $96\% $ der Einträge in der beschreibenden Matrix zu Null. (Diese Prozentzahl stimmt nicht genau mit der erreichten Kompressionsrate überein, weil man auch noch speichern muss, wo sich die Nullen befinden und die anderen Einträge in der Regel keine natürlichen Zahlen sind und eventuell mehr Speicherplatz erfordern. Sie ist aber ein guter Indikator für die erreichbare Einsparung.)
Im dritten und vierten Bild sieht man bereits die deutlich niedrigere Qualität, an mehreren Stellen zeigen sich »Kompressionsartefakte«. Allerdings wurde die Datenmenge in diesen Fällen auch sehr stark verkleinert. Natürlich müsste man nun, wenn man die Qualität dieses Kompressionsverfahrens bewerten wollte, Vergleiche mit anderen Verfahren durchführen, insbesondere mit dem »naiven« Ansatz, die Datenmenge dadurch zu verkleinern, dass man das Bild auf eine kleinere Auflösung herunterrechnet. Das würde hier ein bisschen zu weit führen, aber ich stelle gerne den Python-Code zur Verfügung, wenn Sie diese Frage aufgreifen und selbst experimentieren möchten.

\includegraphics[width=7cm]{figures/im-4-226627} — Abbildung 5.3 Von links oben nach rechts unten die »komprimierten« Fotos, wo alle Werte ${\lt} 1$, bzw. ${\lt} 4$, bzw. ${\lt} 10$, bzw. ${\lt} 18$ auf $0$ gesetzt wurden. Damit wurden ca. $68\% $, bzw. $86\% $, bzw. $93\% $, bzw. $96\% $ der Einträge in der beschreibenden Matrix zu Null. (Diese Prozentzahl stimmt nicht genau mit der erreichten Kompressionsrate überein, weil man auch noch speichern muss, wo sich die Nullen befinden und die anderen Einträge in der Regel keine natürlichen Zahlen sind und eventuell mehr Speicherplatz erfordern. Sie ist aber ein guter Indikator für die erreichbare Einsparung.)
Im dritten und vierten Bild sieht man bereits die deutlich niedrigere Qualität, an mehreren Stellen zeigen sich »Kompressionsartefakte«. Allerdings wurde die Datenmenge in diesen Fällen auch sehr stark verkleinert. Natürlich müsste man nun, wenn man die Qualität dieses Kompressionsverfahrens bewerten wollte, Vergleiche mit anderen Verfahren durchführen, insbesondere mit dem »naiven« Ansatz, die Datenmenge dadurch zu verkleinern, dass man das Bild auf eine kleinere Auflösung herunterrechnet. Das würde hier ein bisschen zu weit führen, aber ich stelle gerne den Python-Code zur Verfügung, wenn Sie diese Frage aufgreifen und selbst experimentieren möchten.

Zum Schluss führen wir dasselbe Verfahren für alle Spalten des neu erhaltenen Blocks durch. Das bedeutet, dass wir $AH$ ersetzen durch $H^t AH$, wobei $H^t$ die zu $H$ transponierte Matrix bezeichnet. In derselben Weise formt man nun alle $(8\times 8)$-Blöcke der Bilddatei um.

Bis zum jetzigen Zeitpunkt haben wir die vorhandene Information nur in eine andere Form gebracht und können die Ausgangsdaten vollständig rekonstruieren. Trotzdem ergibt sich in der Regel auch dadurch schon die Möglichkeit, die Daten platzsparender abzuspeichern, weil die neue $512\times 512$-Matrix in der Regel viele Nulleinträge haben wird. Dann kann man »sich merken«, dass gewisse Bereiche gleich Null sind, statt jeden Eintrag einzeln zu speichern.

Seine volle Kraft entfaltet das Verfahren allerdings, wenn man in $H^t AH$ alle Einträge auf Null setzt, deren Absolutbetrag kleiner ist als ein vorgegebener Wert, beispielweise alle Einträge, die betragsmäßig kleiner sind als $1$. Dadurch erhält man normalerweise einen deutlich größeren Anteil an Nullen, so dass die Matrix wesentlich platzsparender abgespeichert werden kann, siehe die Abbildungen 5.2, 5.3. Trotzdem kann man, wenn man es nicht übertreibt, das ursprüngliche Bild ohne großen Qualitätsverlust zurückgewinnen, wenn man dasselbe Verfahren zur Rücktransformation anwendet.

Es ist zwar nicht zwingend, dieses Verfahren mithilfe des Matrizenprodukts zu beschreiben, und die ganze Sache ist auch mathematisch nicht sehr tiefliegend. Sie ist aber in der Praxis nützlich, lässt sich wie schon angedeutet auch noch weiter verbessern, und die Formulierung mit dem Matrizenprodukt ist einerseits eine klare und einfache Beschreibung, und ermöglicht es andererseits, auf die Theorie des Matrizenprodukts zurückzugreifen, und für die praktische Implementierung Programmbibliotheken zu benutzen, in denen schnelle Matrizenoperationen zur Verfügung gestellt werden.

Quelle: [ VK ] . Siehe auch D. Austin, Image Compression: Seeing What’s Not There,
http://www.ams.org/publicoutreach/feature-column/fcarc-image-compression.

Ergänzung 5.64 Quaternionen, Fortsetzung

Wir können nun auch noch einmal auf die Hamiltonschen Quaternionen zurückkommen (siehe Ergänzung 4.11) und erklären, wie man recht einfach zeigen kann, dass $\mathbb H$ ein Schiefkörper ist. Wir betrachten die injektive (warum?) Abbildung

\[ \iota \colon \mathbb H\to M_2(\mathbb C),\qquad (a, b, c, d) \mapsto \left( \begin{array}{cc} a+bi & -c-di \\ c-di & a-bi \end{array} \right). \]

Es ist leicht nachzurechnen, dass $\iota $ verträglich ist mit der Addition und Multiplikation in $\mathbb H$ und in $M_2(\mathbb C)$:

\[ \iota (x+y) = \iota (x) +\iota (y),\quad \iota (xy) = \iota (x) \iota (y). \]

Daraus folgen (ganz ähnlich wie in Bemerkung 5.42) das Assoziativgesetz der Multiplikation und das Distributivgesetz.

Es bleibt noch zu zeigen, dass jedes Element in $\mathbb H\setminus \{ 0\} $ ein multiplikatives Inverses besitzt. Dazu genügt es zu zeigen, dass jede Matrix $\ne 0$, die im Bild von $\iota $ liegt, invertierbar ist und dass die inverse Matrix ebenfalls im Bild von $\iota $ liegt. Dazu benutzen wir Beispiel 5.56 und die dort eingeführte Determinante einer $(2\times 2)$-Matrix. Es gilt

\[ \delta (\iota ((a,b,c,d))) = \delta \left(\left( \begin{array}{cc} a+bi & -c-di \\ c-di & a-bi \end{array} \right)\right) = a^2+b^2 + c^2 + d^2, \]

und dies ist eine nicht-negative reelle Zahl, die genau dann $=0$ ist, wenn $(a,b,c,d)=0$ ist.

Ist der Wert von $\delta $ nicht Null, so gilt

\begin{align*} \left( \begin{array}{cc} a+bi & -c-di \\ c-di & a-bi \end{array} \right)^{-1} & = (a^2+b^2 + c^2 + d^2)^{-1} \left( \begin{array}{cc} a-bi & c+di \\ -c+di & a+bi \end{array} \right)\\ & = (a^2+b^2 + c^2 + d^2)^{-1} \iota (a, -b, -c, -d). \end{align*}

Es ist auch leicht, das Inverse von $(a,b,c,d)\ne 0$ direkt anzugeben:

\[ (a,b,c,d)^{-1} = \left(\frac{1}{a^2+b^2+c^2+d^2}, \frac{-b}{a^2+b^2+c^2+d^2}, \frac{-c}{a^2+b^2+c^2+d^2}, \frac{-d}{a^2+b^2+c^2+d^2}\right). \]

Damit haben wir vollständig bewiesen, dass $\mathbb H$ ein Schiefkörper ist.

Lineare Algebra I, WS 2020/21

Inhalt

5.3 Das Matrizenprodukt

5.3.1 Rechnen mit Matrizen

5.3.2 Spezielle Matrizen

5.3.3 Bild und Kern einer Matrix

5.3.4 Invertierbare Matrizen

5.3.5 Ergänzungen *