Lineare Algebra I Herbstsemester 2016 Universität Basel Philipp Habegger 7. November 2016 Inhaltsverzeichnis 0 Einführung 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, 1.1 Logische Aussagen und Beweise . . . . . . . . . . 1.2 Mengen und Abbildungen . . . . . . . . . . . . . 1.3 Gruppen . . . . . . . . . . . . . . . . . . . . . . . 1.4 Ringe und Körper . . . . . . . . . . . . . . . . . . 5 Körper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 7 10 14 22 2 Matrizenkalkül 31 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt . . . . . . . . . . . 33 2.2 Lineare Gleichungssysteme und Zeilenstufenform . . . . . . . . . . . . . . 44 2.3 Eine Anwendung: PageRank . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 Die Determinante einer Matrix 63 3.1 Permutationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.2 Die Definition der Determinante . . . . . . . . . . . . . . . . . . . . . . . 71 3 0 Einführung Diese erste Version dieses Skripts zur Vorlesung “Lineare Algebra” ist an der Goethe Universität Frankfurt am Main im Sommersemester 2011 entstanden. Inzwischen gab es kleinere Revisionen und ich gehe davon aus, dass auch in Zukunft Teile des Skripts angepasst/korrigiert/erweitert werden. Es wird noch einige Zeit dauern, bis die gröbsten Fehler korrigiert sind. Sie benutzen dieses Skript auf eigene Gefahr! Korrekturvorschläge nehme ich gerne entgegen. Bitte teilen Sie mir solche per Email oder persönlich nach der Vorlesung mit. Folgende zwei Bücher dienten als Grundstruktur dieser Vorlesung. Ich kann den Titel von Artin auch als weiterführende Lektüre empfehlen. 1 Michael Artin, Algebra, Birkhäuser Verlag, 1999. 2 Gerd Fischer, Lineare Algebra, Vieweg Verlag. 5 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Bevor wir mit dem Studium linearer Abbildungen im Sinne der linearen Algebra loslegen, müssen wir die nötigen Grundlagen erarbeiten. Dabei werden wir uns von den Rechenoperationen wie Addition, Multiplikation im vertrauten Rahmen der rationalen oder reellen Zahlen lösen müssen. Ziel dieses Kapitels ist es algebraische Strukturen einzuführen, die Rechenoperationen wie Addition oder Multiplikation verallgemeinern. Die lineare Algebra wird sich in diesem Kontext abspielen. 1.1 Logische Aussagen und Beweise Welche der folgenden Aussagen ist wahr und welche ist falsch? (i) Der Himmel ist blau. (ii) Alle Menschen sind sterblich. (iii) Die Erde ist eine Scheibe. Unsere Erfahrungen aus dem Alltag (und unsere Bildung) legen nahe, dass (i) und (ii) wahr sind und (iii) falsch ist. Mehrere Aussagen kann man mit und und oder zu einer Aussage verknüpfen. Z.B.: (iv) Der Himmel ist blau und die Erde ist eine Scheibe. (v) Der Himmel ist blau oder Feuer ist kalt. (vi) Die Erde ist eine Scheibe oder Feuer ist kalt. Hier sind Aussagen (iv) und (vi) falsch und (v) ist wahr. Eine Aussage ist genau dann wahr, wenn ihre Negation falsch ist. So lautet die (wahre) Negation von (iv): “Der Himmel ist nicht blau oder die Erde ist keine Scheibe”. Die (falsche) Negation von (v) ist: “Der Himmel ist weder blau noch ist Feuer kalt”. Ein mathematischer Beweis ist eine Kette logischer Schlüsse zwischen Aussagen. Ein einfacher Schluss ist: Euler ist ein Mensch und Menschen sind sterblich. Also ist Euler sterblich. 7 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Die Schlussfolgerung wird in der Mathematik oft durch einen Implikationspfeil abgekürzt. Euler ist ein Mensch und Menschen sind sterblich =⇒ Euler ist sterblich. Sind P und Q zwei beliebige Aussagen, so ist P =⇒ Q gleichbedeutend mit P ist falsch oder Q ist wahr. Man sagt auch, dass die Aussage P die Aussage Q impliziert. Oder dass Q aus P folgt. Der Implikationspfeil =⇒ bedeutet nicht, dass die Aussage auf der rechten Seite durch die Aussage links begründet wird. Daher ist die etwas seltsam anmutende Aussage Menschen sind sterblich =⇒ Feuer ist heiss wahr, da die Aussage rechts des Implikationspfeils wahr ist. Weiterhin sind Die Erde ist flach =⇒ Feuer ist heiss und Die Erde ist flach =⇒ die Erde ist eine Kugel beide wahr, denn eine falsche Aussage impliziert alle Aussagen. Aus diesem Grund ist es wichtig, Widersprüche zu vermeiden. Aus einem Widerspruch kann man jede Aussage herleiten und dies würde die gesamte Mathematik zerstören. Der “Äquivalenzpfeil” ⇐⇒ wird eingesetzt, wenn zwei Aussagen gleichbedeutend sind. Für eine ganze Zahl n gilt n = 0 ⇐⇒ n2 = 0. Obwohl Aussagen wie “Die Erde ist eine Kugel” oder “Menschen sind sterblich” auf den ersten Blick korrekt sind, sind Begriffe aus dem Alltag tückisch. Die Erde ist nicht wirklich eine Kugel sondern nur annäherungsweise, der Radius am Äquator ist grösser als am Nordpol. Dass Menschen sterblich sind, kann man nicht zweifelsfrei belegen, solange es noch lebendige Menschen gibt. In der Mathematik beschäftigt man sich mit Idealen Grössen, welche unsere Vorstellung der Welt annähern und einen (möglichst aussagekräftigen) Querschnitt der Realität liefern. Über diese Objekte können wir Vorhersagen treffen, die zweifelsfrei wahr sind. Unser Werkzeug dafür ist der mathematische Beweis. Dieses Werkzeug werden wir im Laufe des Semesters immer wieder antreffen. Es gibt verschiedene Beweisstrategien. Wir behandeln hier zuerst den Induktionsbeweis. Behauptung: Für jede ganze Zahl n ≥ 1 gilt 1 + 2 + 3 + ··· + n = 8 n(n + 1) . 2 1.1 Logische Aussagen und Beweise Beweis: Der Beweis ist mittels Induktion auf n. Wir überprüfen daher zuerst die Aussage im Fall n = 1, das ist die sogenannte Induktionsverankerung. Für n = 1 ist die Summe in der Behauptung gleich 1. Auch der rechten Seite steht ebenfalls 1 und damit stimmt unsere Behauptung zumindest für n = 1. Nun kommen wir zum Induktionsschritt. Dafür nehmen wir an, dass unsere Behauptung für n − 1 ≥ 1 wahr ist. Wir müssen nun zeigen, dass sie auch für den erhöhten Wert n stimmt. Die Summe links ist (n − 1)n +n 1 + 2 + 3 + · · · + (n − 1) + n = 2 wobei wir die Induktionsvoraussetzung im Fall n − 1 verwendet haben. Nun gilt nach einer Umformung 1 + 2 + 3 + ··· + n = n2 − n + 2n n2 + n n(n + 1) (n − 1)n +n= = = . 2 2 2 2 Was zu zeigen war. Induktion ist ein mächtiges Mittel, es gibt aber Fallstricken. Können Sie den Fehler in der Argumentation unten finden? Behauptung: Alle Hosen haben die gleiche Farbe. 1 Beweis: Wir wollen mittels Induktion über n ≥ 1 zeigen, dass n beliebige Hosen die gleiche Farbe haben. Die Verankerung n = 1 ist leicht, da es sich bei nur einer Hose keine Frage stellt. Nun müssen wir den Induktionsschritt machen. Wir nehmen an, dass die Aussage für n− 1 ≥ 1 bereits bewiesen ist. Seien also n Hosen gegeben. Wir bilden einen Kleiderhaufen mit n − 1 Hosen. Aus der Induktionsvoraussetzung müssen alle Hosen auf dem Haufen die gleiche Farbe besitzen. Es bleibt aber eine Hose übrig und wir müssen überprüfen, dass sie die gleiche Farbe wie die übrigen Hosen hat. Dazu bilden wir einen zweiten Kleiderhaufen mit n − 1 Hosen, darunter die besagte Hose. Wieder haben alle Hosen auf dem neuen Haufen die gleiche Farbe. Da die im ersten Durchlauf vergessene Hose darunter liegt, haben alle Hosen die gleiche Farbe. Eine weitere Technik ist mittels Widerspruchsbeweis. Dabei nehmen wir die Negation der Schlussfolgerung an und leiten einen Widerspruch her. √ Behauptung: 2 ist keine rationale Zahl. Beweis: Wir werden die Negation √ der Aussage annehmen, und einen Widerspruch herleiten. Die Negation besagt, dass 2 eine rationale Zahl ist. Also existieren ganze Zahlen √ p ≥ 1 und q ≥ 1 mit 2 = p/q. Wären p und q beide gerade Zahlen, so könnten wir den Faktor 2 im √ Quotienten p/q kürzen. Dies würde zu einem neuen Paar führen, dessen Quotient 2 ist. Man kann 1 Natürliche ist die Aussage kreuzfalsch! 9 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper nicht beliebig oft durch zwei teilen, also dürfen wir annehmen, dass p und q nicht beide gerade Zahlen sind. Wir quadrieren und erhalten 2 = p2 /q 2 , also p2 = 2q 2 . Folglich ist p2 eine gerade Zahl. Das Quadrat einer ungeraden Zahl ist wieder ungerade, wie man leicht überprüft. Also ist p gerade und damit von der Form p = 2p0 . Wir setzen ein und erhalten 2q 2 = (2p0 )2 = 4p0 2 2 also q 2 = 2p0 . Jetzt sehen wir, dass q 2 eine gerade Zahl ist. Mit dem gleichen Argument wir oben folgt, dass q gerade ist. Die widerspricht jedoch unserer Annahmen, dass p und q nicht beide gerade sind. 1.2 Mengen und Abbildungen Die Mengelehre ist ein mögliches Fundament, um Mathematik zu betreiben. Für uns ist jedes mathematische Objekt schlussendlich eine Menge. Entgegen vieler Versprechungen bezüglich der Rigorosität im Einführungskapitel, werden wir den Begriff der Menge nicht definieren. Wir betreiben naive Mengenlehre, d.h. für uns ist eine Menge eine “Ansammlung” von Objekten. Wir benutzen die aus der Schule bekannten Symbole. Sind M und N Mengen, so schreiben wir M ⊆ N , falls jedes Element aus M ein Element aus N ist. Dies ist keine mathematisch korrekte Definition. Wir müssen uns mit einer naiven Vorstellung des Mengenbegriffs begnügen. Eine präzise Behandlung würde uns zu weit vom eigentlichen Thema wegführen. Einige der folgenden Mengen werden wir im Laufe der Vorlesung immer wieder antreffen. Beispiel 1.1. (i) Die leere Menge ∅ = {} enthält keine Elemente. Für jede Menge M gilt ∅ ⊆ M . (ii) Die Menge der natürlichen Zahlen ist N = {1, 2, 3, . . . }. Es gibt bei dieser Definition (wie auch vielen anderen in der Mathematik) keinen Konsens, da einige Autoren auch die Null zu den natürlichen Zahlen zählen. Die Menge der ganzen Zahlen ist Z = {0, ±1, ±2, . . . }. Hier gilt N ⊆ Z. (iii) Die Menge der Primzahlen ist {2, 3, 5, . . . }. Die Eins ist keine Primzahl. (iv) Die rationalen Zahlen sind Brüche von ganzen Zahlen. Ihre Gesamtheit wird mit Q = {a/b : a, b ∈ Z und b 6= 0} bezeichnet. Es gilt Z ⊆ Q. (v) In der Analysis spielt die Menge R der reellen Zahlen eine wichtige Rolle. Hier gilt Q ⊆ R. (vi) Es gibt auch exotischere Mengen, z.B. die Menge {{}} deren einziges Element die leere Menge ist. Eine alternative Schreibweise ist {∅}. Es ist wichtig, die zwei Mengen {{}} = 6 {} nicht zu verwechseln. 10 1.2 Mengen und Abbildungen Hat man zwei Mengen gegeben, so gibt es viele Möglichkeiten weitere daraus zu gewinnen. Definition 1.2. Seien M und N Mengen. Ihre Vereinigung ist M ∪ N = {m : m ∈ M oder m ∈ N } und ihr Schnitt ist M ∩ N = {m : m ∈ M und m ∈ N }. Wir setzen auch M r N = {m ∈ M : m 6∈ N }. Beispiel 1.3. (i) Es gilt {1, 2, 3} ∪ {a, b, c} = {1, 2, 3, a, b, c} = {b, a, 3, c, 2, 1}. (Bei Mengen spielt die Reihenfolge der Elemente keine Rolle.) (ii) Die Menge der positiven und negativen reellen Zahlen sind disjunkt, d.h. sie haben kein gemeinsames Element. In Notationsschreibweise {x ∈ R : x > 0} ∩ {x ∈ R : x < 0} = ∅. (iii) Es gilt {p ∈ N : p eine Primzahl} ∩ {n ∈ N : n ist gerade} = {2}. (iv) Ganz allgemein haben wir M ∪ ∅ = M und M ∩ ∅ = ∅ für jede Menge M . Eine weitere wichtige Konstruktion ist die des Produkts zweier Mengen. Definition 1.4. Seien M und N Mengen. Das kartesische Produkt der Mengen M und N besteht aus allen Paaren bestehend aus einem Element aus M und aus N , es wird mit M × N bezeichnet. D.h. M × N = {(m, n) : m ∈ M und n ∈ N }. Eine für die lineare Algebra wichtige Situation erhält man, wenn das Produkt aus Kopien der reellen Zahlen nimmt. Beispiel 1.5. (i) Es gilt R × R = {(x, y) : x, y ∈ R}. Also besteht jedes Element von R × R aus zwei “Koordinaten”. Dies legt nahe, dass R × R als Ebene betrachtet werden soll. (ii) Jedes Element aus R × R × R hat drei “Koordinaten”. Und deshalb soll man sich R × R × R als den dreidimensionalen Raum vorstellen. (iii) Natürlich kann man jetzt beliebig lange weitergehen und R × R × R × R usw. definieren. Unser Vorstellungsvermögen lässt uns im Stich, da der vierdimensionalen Raum schwer vorstellbar ist. Um die Notation zu erleichtern schreiben wir Rn für R × R × ··· × R {z } | n Faktoren für n ∈ N. Ganz allgemein ist M n das n-fache kartesische Produkt M × M × ··· × M | {z } n Faktoren einer Menge M mit sich selbst. 11 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Wir werden später den Begriff eines Vektorraums einführen. Der n-dimensionale reelle Raum Rn ist ein klassisches Beispiel eines Vektorraums. Mengen fallen in zwei Kategorien. Es gibt endliche und unendliche Mengen. D.h. Mengen, die endlich viele bzw. unendlich viele Elemente enthalten. Wir werden den Begriff “endliche Menge” nicht präzise definieren. Definition 1.6. Ist M eine endliche Menge, so bezeichnet #M oder |M | die Anzahl Elemente in M . Diese Anzahl heisst auch Kardinalität von M . Mengen werden interessanter, wenn man sie in Beziehung zu anderen Mengen bringen kann. Definition 1.7. Seien M und N Mengen. Eine Abbildung f : M → N ordnet jedem Element m ∈ M genau ein Element f (m) ∈ N zu. Die Menge M nennt man gerne den Definitionsbereich von f und N heisst Wertebereich. Bemerkung 1.8. Sei Γ ⊆ M × N eine Teilmenge mit der Eigenschaft, dass es für jedes m ∈ M genau ein n ∈ N mit (m, n) ∈ Γ gibt. Die Zuordnung m 7→ das eindeutige n ∈ N mit (m, n) ∈ Γ ist eine Abbildung im Sinne der Definition oben. Umgekehrt liefert jede Abbildung f : M → N in Sinne unserer Definition eine Menge, der Graph von f , {(m, f (m)) : m ∈ M } welche die besagte Eigenschaft oben erfüllt. Wir stellen fest, dass Abbildungen (wie alle mathematischen Objekte) Mengen sind! Nicht jedes Element von N muss als Wert angenommen werden. Es ist nur wichtig, dass jedes Element aus M ein Bildpunkt in N besitzt. Auch erlaubt ist es, dass f mehrere (oder sogar alle) Elemente von M auf dasselbe Element in N abbildet. Beispiel 1.9. (i) Sei V die Menge aller Vorlesungen. Dann gibt es eine Abbildung f : V → N die jeder Vorlesung die vorgesehene Anzahl Kreditpunkte zuordnet. Z.B. gilt f (Lineare Algebra I) = 8. (ii) Die Abbildung f (x) = 1/x kann nicht Definitionsbereich R haben, denn Division durch Null ist nicht erlaubt. Der grösstmögliche Definitionsbereich ist R r {0}. Definition 1.10. Sei f : M → N eine Abbildung zwischen Mengen M und N . Dann heisst f surjektiv, falls jedes Element von N Bildpunkt ist, d.h. für jedes n ∈ N gibt es (mindestens) ein m ∈ M mit f (m) = n. Die Abbildung f heisst injektiv falls f (m) = f (m0 ) ⇒ m = m0 . Eine surjektive und injektive Abbildung heisst bijektiv. 12 1.2 Mengen und Abbildungen Bemerkung 1.11. Eine bijektive Abbildung f : M → N lässt sich invertieren. Für jedes genau ein m ∈ M n∈N gibt es | {z } | {z } da f surjektiv da f injektiv mit f (m) = n. Die Zuordnung n 7→ m definiert die sogenannte Umkehr- oder Inverseabbildung f −1 : N → M . Zwei Abbildungen f : M → N und g : N → P lassen sich zu einer Abbildung g ◦ f : M → P verketten f G M → N → P. Konkret setzt man (g ◦ f )(m) = g(f (m)) für jedes m ∈ M . Dabei muss der Wertebereich von f gleich dem Definitionsbereich von g sein. Ansonsten könnte man g nicht bei f (m) auswerten. Achtung. Verkettungen “liest” man von rechts nach links. In der Notation oben, also bei g ◦ f wird zuerst f und dann g angewendet. Beispiel 1.12. Ist f : M → N bijektiv und f −1 : N → M die Umkehrabbildung, so ist (f −1 ◦ f )(m) = m für m ∈ M und (f ◦ f −1 )(n) = n für n ∈ N . Definition 1.13. Die “triviale” Selbstabbildung f : M → M , die durch f (m) = m definiert ist, heisst Identitätsabbildung. Sie wird mit 1M , idM , Id, id oder sogar nur 1 bezeichnet. Zwischen zwei Mengen M und N kann es “sehr viele” Abbildungen geben. Ihr Gesamtheit ist selber eine Menge Abb(M, N ) = {f : f : M → N ist eine Abbildung}. Beispiel 1.14. (i) Die Menge Abb(R, R) wird man als Mathematiker wahrscheinlich nie direkt benutzen. Diese Menge ist zu unüberschaubar. Es fehlt hier zusätzliche Struktur die wirklich interessante Abbildungen heraus filtert. Stattdessen gibt es zu viele “wilde” Abbildungen R → R. (ii) Es gibt keine Abbildung mit Definitionsbereich N und Wertebereich {}. Um dies einzusehen, überlege man sich welchen Bildpunkt das Element 1 ∈ N haben würde, falls eine derartige Abbildung existieren würde. (iii) Überlegen sie sich, ob eine Abbildung ∅ → ∅ existiert oder nicht! (iv) Sind M und N zwei endliche Mengen und f : M → N eine bijektive Abbildung, so gilt #M = #N . Sind M und N unendliche Mengen, so können kuriose Dinge passieren. Die Abbildung f : N = {1, 2, 3, . . . } → {2, 4, 6, . . . } gegeben durch f (n) = 2n 13 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper ist bijektiv obwohl N auf den ersten Blick gesehen doppelt so viele Elemente enthält wie wie {2, 4, 6, . . .}. Noch kurioser ist die Tatsache, dass es sogar ein bijektive Abbildung N → N2 gibt. Rein als Menge lässt sich N nicht von N2 unterscheiden! Mengen bilden die Grundlage der ganzen Mathematik. Im Prinzip ist jedes Objekt, welches wir untersuchen werden, eine Menge. Diese wird jedoch meistens zusätzliche Struktur verschlüsseln. Die erste “Struktur”, die wir behandeln werden, ist die Gruppenstruktur. 1.3 Gruppen Bislang haben wir Z = {0, ±1, ±2, . . . } als Menge behandelt. Dabei haben wir den folgenden wichtigen Aspekt vergessen. Zwei ganze Zahlen a, b ∈ Z lassen sich zu einer ganzen Zahl a + b summieren. (1.1) Diese einfache Tatsache wird vom Mengenbegriff nicht berücksichtigt. Betrachten wir (1.1) nüchtern aus der Perspektive der Mengenlehre an, so fällt auf, dass die Addition eigentlich eine Abbildung ist: m : Z × Z → Z definiert durch m(a, b) = a + b. Man nennt m auch die Verknüpfungsabbildung. Diese ist keineswegs beliebig, sie besitzt viele Eigenschaften, die man aus der Schule kennt und formal beschreiben kann. Diese Eigenschaften werden im Gruppenbegriff elegant verpackt. Schauen wir nun einige der Eigenschaften an. Seien a und b in Z. (N) Es gilt m(a, 0) = a + 0 = a und m(0, b) = 0 + b = b (Neutrales Element). (K) Es gilt m(a, b) = a + b = b + a = m(b, a) (Kommutativität). (I) Es gilt m(−a, a) = (−a) + a = 0 (Inverses). Diese dritte Eigenschaft legt nahe, eine weitere Abbildung einzuführen. Wir setzen i : Z → Z wobei i(a) = −a. Mit dieser Notation sagt uns (iii) nichts anderes als m(i(a), a) = 0. Es gibt eine vierte Eigenschaft, die man nicht übersehen sollte. (A) Für alle a, b, c ∈ Z gilt m(m(a, b), c) = (a + b) + c = a + (b + c) = m(a, m(b, c)) (Assoziativität). 14 1.3 Gruppen Würde man nur mit den ganzen Zahlen arbeiten, so würde es sich nicht lohnen, die Abbildungen m und i einzuführen. Wir können die Addition bzw. Inversion mit denen aus der Schule bekannten Symbole + und − ebenso gut beschreiben. Die vier Eigenschaften oben bilden die Schablone für den Begriff der abelschen Gruppe. Definition 1.15. Eine Gruppe ist ein Tupel (G, e, m). Hier ist G eine Menge, m : G×G → G eine Abbildung und e ∈ G ein Element. Diese erfüllen folgende Eigenschaften (auch Gruppenaxiome genannt). (A) Für alle a, b, c ∈ G gilt m(m(a, b), c) = m(a, m(b, c)). (Assoziativgesetz) (N) Für alle a ∈ G gilt m(e, a) = a. (Neutrales Element) (I) Für jedes a ∈ G gibt es ein a0 ∈ G mit m(a0 , a) = e. (Inverses Element) Die Abbildung m : G → G → G heisst Verknüpfungsabbildung der Gruppe und e heisst neutrales Element der Gruppe. Jedes Element a0 wie in (I) heisst ein zu a Inverses Element. Wir werden später sehen, dass jedes a ∈ G genau ein Inverses besitzt. Dann dürfen wir von dem Inversen von a sprechen. Gilt zusätzlich (K) Für alle a, b ∈ G gilt m(a, b) = m(b, a). so nennt man G kommutativ. Anstatt kommutativ wird auch der synonyme Begriff abelsch verwendet. Bemerkung 1.16. (i) Die Kommutativität wird nicht ausdrücklich als Gruppenaxiom verlangt. Sie schliesst zu viele interessante Beispiele aus. (ii) In unserem Beispiel der ganzen Zahlen war das neutrale Element e = 0 ∈ Z. (iii) Die Symbole e und m in der Definition der Gruppe sind schwerfällig. Oft nutzt man a ·G b oder a · b oder ab oder a +G b oder a + b für die Verknüpfungsabbildung. Die Symbole +G und + sind für abelsche Gruppen reserviert; die Schreibweise a ·G b oder ab kommt jedoch auch bei nicht abelschen Gruppen vor. Ist die Notation “multiplikativ” (d.h. wird ab für die Verknüpfung verwendet), so schreiben wir a−1 für das Inverse von a und 1 anstatt e. Ist die Notation “additiv”, so schreiben wir −a für das Inverse von a und 0 für e. Es ist wichtig sich davon zu überzeugen, dass die Begriff “multiplikativ” und “additiv” keine Eigenschaft der Gruppe sind. Welches Symbol wir schlussendlich für die Verknüpfung brauchen, ist aus mathematischer Sicht irrelevant. Denkbar wären auch die Symbole a♦b oder a♣b als Symbole für die Verknüpfung von a und b. 15 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper (iv) In der Praxis erwähnt man oft nur die Menge G des Tupels (G, e, m). D.h. es wird meistens von einer Gruppe G die Rede sein, wobei implizit klar ist, wie die Verknüpfung und das neutrale Element zu verstehen sind. Wir haben schon ein Beispiel einer Gruppe gesehen. Es gibt aber weitere Gruppen, die wir zumindest implizit kennen. Beispiel 1.17. (i) Die Gruppe (Q, 0, +) der rationalen Zahlen mit der Addition. (ii) Die Gruppe der rationalen Zahlen ungleich Null mit Multiplikation (Qr{0}, 1, m). Hier gilt m(a, b) = ab für zwei rationale Zahlen a, b ∈ Q r {0}. Das Inverse von a ist 1/a für a ∈ Q r {0}. Natürlich darf die Null nicht in der Gruppe enthalten sein. Denn wäre a ein Inverses bezüglich der Multiplikation von 0, so hätten wir 1 = a0 = 0 was natürlich absurd ist. Man darf nicht durch Null dividieren! (iii) Sei M eine beliebige Menge. Wir können aus M wie folgt eine Gruppe gewinnen. Die Elemente dieser Gruppe sind bijektive Selbstabbildungen von M . D.h. SM = {f : M → M : f ist bijektiv}. Die Verknüpfung unserer Gruppe wird die Verknüpfung von Abbildungen sein: m(f, g) = f ◦ g für f, g ∈ SM . Das neutrale Element ist die Identitätsabbildung 1M : M → M und das Inverse von f ist f −1 wobei f −1 die Inverseabbildung von f ist. Diese existiert, da f bijektiv ist. Behauptung: Das Tupel (SM , 1M , m) ist eine Gruppe. Beweis: Wir müssen die Axiome (A), (N) und (I) nachweisen. Falls f und g bijektive Selbstabbildungen von M sind, so ist auch f ◦ g eine Selbstabbildung von M . Diese Verknüpfung ist auch bijektiv. Somit ist f ◦ g ∈ SM und m : SM × SM → SM ist eine wohldefinierte Abbildung. Falls f, g, h ∈ SM und m ∈ M so gilt ((f ◦ g) ◦ h)(m) = (f ◦ g)(h(m)) = f (g(h(m))) = f ((g ◦ h)(m)) = (f ◦ (g ◦ h))(m). Da dies für jedes m ∈ M gilt, haben wir (f ◦ g) ◦ h = f ◦ (g ◦ h). Somit ist das Axiom (A) gezeigt. Es gilt 1M ◦ f = f da 1M die Identitätsabbildung ist. Daraus folgt Axiom (N). Schliesslich haben wir f −1 ◦ f = 1M da f −1 die Umkehrabbildung von f ist. Wir folgern das Axiom (I) und somit ist (SM , 1M , m) eine Gruppe. Die Gruppe SM heisst die symmetrische Gruppe auf M . Sie ist genau dann abelsch, wenn #M ≤ 2. 16 1.3 Gruppen (iv) Die triviale Gruppe ist die simpelste Gruppe, die man sich vorstellen kann. Sie besteht aus nur einem Element G = {e}. Dadurch ist die Verknüpfungsabbildung durch m(e, e) = e festgelegt. Natürlich muss e das neutrale Element sein und das eigene Inverse sein. Man überprüft alle Axiome leicht nach. Die triviale Gruppe ist sogar eine abelsche Gruppe. Eine Gruppe (G, e, m) mit G = {e = g1 , . . . , gn } endlich lässt sich mit Hilfe der Verknüpfungstabelle untersuchen: g1 .. . g1 ··· m(g1 , g1 ) · · · .. . gn m(g1 , gn ) .. . gn m(gn , g1 ) · · · m(gn , gn ) Diese Tabelle unterliegt Symmetriebedingungen, die sich aus den Axiomen ergeben. Da g1 = e das neutrale Element der Gruppe ist, ist die erste Spalte gleich g1 , . . . , gn . Eine abelsche Gruppe ergibt eine Verknüpfungstabelle, die symmetrisch bezüglich der Diagonale von oben links nach unten rechts ist. Beispiel 1.18. (i) Es gibt auch eine Gruppe mit zwei Elementen. Dazu betrachten wir G = {−1, 1} ⊆ Q. Die Multiplikation auf den rationalen Zahlen (die für die Verknüpfung in (Q r {1}, 1, ·) verantwortlich ist) definiert eine Verknüpfung auf G, da 1 · 1 = (−1) · (−1) = 1 und 1 · (−1) = (−1) · 1 = −1. D.h. wir erhalten eine Abbildung m : G × G → G. Da die Multiplikation auf Q das Assoziativitätsgesetzt erfüllt, ist die eben definierte Verknüpfung auch assoziativ. Schliesslich zeigt 1 · 1 = 1 und 1 · (−1) = −1, dass 1 ein neutrales Element ist. Wegen 1 · 1 = (−1) · (−1) = 1 existiert stets ein Inverses. Damit ist bewiesen, dass (G, 1, m) eine Gruppe ist. Sie ist ebenfalls abelsch. Hier ist ihre Verknüpfungstabelle 1 −1 1 1 −1 −1 −1 1 (ii) Wir betrachten die zweielementige Menge M = {♣, ♠}. In Beispiel 1.17(iii) haben wir die symmetrische Gruppe SM kennengelernt. Es sind die bijektiven Selbstabbildungen {♣, ♠} → {♣, ♠}. Es gibt genau zwei mögliche Abbildungen f (♣) = ♣, f (♠) = ♠ (die Identitätsabbildung auf M ) und g(♣) = ♠, g(♠) = ♣. Wir stellen fest, dass g ◦ g = f , da zweimal Vertauschen die Identitätsabbildung ergibt. Die Verknüpfungstabelle hat die folgende Gestalt f g f f g g g f 17 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Also ist S{♣,♠} eine abelsche Gruppe. Weiterhin stellen wir fest, dass die Verknüpfungstabelle aus dem erste Beispiel bis auf ein Vertauschen der Symbole 1 ↔ f und −1 ↔ g gleich sind. Die zwei Gruppen unterscheiden sich lediglich in der Notation und sind aus gruppentheoretischer Sicht ununterscheidbar. Man nennt sie isomorph, mehr dazu später. Es gibt bis auf Isomorphismus nur eine Gruppe mit zwei Elementen. Kommen wir nun zum ersten Lemma. Lemma 1.19. Sei (G, e, m) eine Gruppe. Wir benutzen die multiplikative Schreibweise, d.h. m(a, b) = ab für alle a, b ∈ G. (i) Sei a ∈ G. Wegen (I) gibt es a0 , a00 ∈ G mit a0 a = e und a00 a0 = e. Es gilt aa0 = e, a00 = a und ae = a. (ii) Sei e0 ∈ G mit e0 a = a für alle a ∈ G. Dann ist e0 = e. (Das neutrale Element ist eindeutig.) (iii) Seien a, a0 , ae0 ∈ G mit a0 a = e = ae0 a. Dann ist a0 = ae0 . (Es gibt genau ein zu a inverses Element.) (iv) Seien a, b, c ∈ G mit ab = ac, dann gilt b = c. Haben wir ba = ca, so gilt ebenfalls b = c. (Man darf kürzen.) Beweis. Der Beweis von (i) ist eine trickreiche Rechnung. Wir nutzen die Abkürzung ab für m(a, b). Es gilt a00 a0 = e und damit (N ) s.o. (A) (A) (I) (N ) (I) aa0 = e(aa0 ) = (a00 a0 )(aa0 ) = a00 (a0 (aa0 )) = a00 ((a0 a)a0 ) = a00 (ea0 ) = a00 a0 = e. Es folgt also die erste Behauptung in (i). Die zweite Behauptung ist eine Übungsaufgabe. Die dritte Behauptung ergibt sich aus (I) (A) s.o. (N ) ae = a(a0 a) = (aa0 )a = ea = a. Nun beweisen wir Teil (ii). Sei also ẽ ein alternatives neutrales Element: d.h. ẽa = a für alle a ∈ G. Für a = e erhalten wir ẽe = e. Aus der dritten Behauptung von (i) folgt aber ẽe = ẽ und somit ẽ = e. Nun kommen wir zu Teil (iii). Seien a ∈ G und a0 , ae0 ∈ G mit a0 a = e = ae0 a. Wir erhalten (A) (i) (N ) (N ) a0 = ea0 = (ae0 a)a0 = ae0 (aa0 ) = ae0 e = ae0 und somit ist Teil (iii) erledigt. Die erste Situation in Teil (iv) impliziert ab = ac. Wir erhalten also a0 (ab) = a0 (ac) wobei a0 ein zu a inverses Element ist. Nutzt man nun auf beiden Seiten (A), so erhält 18 1.3 Gruppen man (a0 a)b = (a0 a)c. Das Gruppenaxiom (I) impliziert a0 a = e und (N) ergibt eb = b und ec = c. Wir erhalten b = c. Die zweite Situation in (iv) ist ba = ca. Nun haben wir (ba)a0 = (ca)a0 . Wir argumentieren wie in der ersten Situation, nutzen aber Teil (i) diese Lemmas anstelle von (I) um b = c zu folgern. Der Beweis des Lemmas wäre für abelsche Gruppen viel einfacher gewesen. Definition 1.20. Sei (G, e, m) eine Gruppe und a ∈ G. Wir benutzen die multiplikative Schreibweise. Das wegen Teil (iii) des vorherigen Lemmas eindeutig bestimmte Element a0 mit a0 a = e heisst Inverses von a. Nutzen wir die additive Schreibweise für G so schreiben wir −a für das Inverse. In multiplikativer Schreibweise wird das Inverse mit a−1 bezeichnet. Bemerkung 1.21. Aus (ii) und (iii) des vorherigen Lemmas folgt, dass die Verknüpfungsabbildung m : G × G → G einer Gruppe das neutrale Element und die Inverseabbildung a 7→ a0 festlegt. Insbesondere wird eine endliche Gruppe durch ihre Verknüpfungstabelle eindeutig festgelegt. Für eine feste Tabellengrösse n gibt es nur endlich viele Möglichkeiten, die Tabelle mit Elementen aus G zu füllen. Natürlich ist nicht jede beliebige Tabelle bestehend aus Elementen von G die Verknüpfungstabelle einer Gruppe. Auf jeden Fall gibt es zu festem n nur endlich viele “verschiedene” Gruppen der Kardinalität n. Einen ersten Einblick in was es bedeutet, dass zwei Gruppe “gleich” sind, haben wir in Beispiel 1.18 gehabt. Für grössere n kann die genaue Anzahl durchaus schwierig zu bestimmen sein.2 n 1 2 3 4 5 6 7 8 .. . 60 .. . 2 Anzahl “verschiedener” Gruppen mit Kardinalität n 1 (die triviale Gruppe) 1 (Gruppe aus Bsp. 1.18) 1 2 1 2 (Erste nicht abelsche Gruppe) 1 5 .. . 13 (Erste nicht-triviale einfache Gruppe) .. . 256 .. . 56092 .. . 2016 2017 .. . 6538 1 .. . Quelle für 256 und 2016 H.-U. Besche and I. Panchenko: https://oeis.org/A000001. 19 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Dieses unregelmässige Verhalten steht im Kontrast zur Einfachheit des Gruppenbegriffs. Ähnlich wie bei Mengen, können Gruppen mittels Abbildungen verglichen werden. Definition 1.22. Seien (G, eG , ·G ) und (H, eH , ·H ) Gruppen. Eine Abbildung f : G → H heisst Gruppenhomomorphismus (oder kurz Homomorphismus) falls f (g1 ·G g2 ) = f (g1 ) ·H f (g2 ) für alle g1 , g2 ∈ G. Ist f bijektiv, so nennt man f einen Gruppenisomorphismus (oder kurz Isomorphismus) und G und H heissen isomorph. Beispiel 1.23. (i) Seien G und H die Gruppe der ganzen Zahlen mit der Addition. Genauer G = H = (Z, 0, +). Falls n ∈ Z so erfüllt die Abbildung f : Z → Z gegeben durch f (a) = na die Gleichung f (a + b) = n(a + b) = na + nb = f (a) + f (b) für alle a, b ∈ Z. Also ist f ein Gruppenhomomorphismus. (ii) Sei nun G wie in Beispiel (i) und H die Gruppe Q r {0} mit der Multiplikation und 1 als neutrales Element. Wir definieren f (a) = 2a für a ∈ Z. Dann ist f ein Gruppenhomomorphismus weil f (a + b) = 2a+b = 2a 2b = f (a)f (b) für alle a, b ∈ Q r {0}. Wir bestimmen erste Eigenschaften eines Gruppenhomomorphismus. Lemma 1.24. Seien (G, eG , ·G ) und (H, eH , ·H ) Gruppen und sei f : G → H ein Gruppenhomomorphismus. (i) Es gilt f (eG ) = eH und f (a−1 ) = f (a)−1 für alle a ∈ G. (ii) Seien a1 , a2 ∈ {a ∈ G : f (a) = eH } = f −1 (eH ), dann ist a1 ·G a2 ∈ f −1 (eH ) Beweis. Wegen Axiom (N) gilt eG ·G eG = eG . Also eH ·H f (eG ) = f (eG ) = f (eG ·G eG ) = f (eG ) ·H f (eG ). Wir berufen uns auf Teil (iv) des vorherigen Lemmas um f (eG ) zu kürzen. Daraus ergibt sich eH = f (eG ) und die erste Hälfte von Teil (i) folgt. Die zweite Hälfte ergibt sich aus f (a−1 ) ·H f (a) = f (a−1 ·G a) = f (eG ) = eH . und Teil (iii) von Lemma 1.19. Teil (ii) ist wiederum ein Spiel mit den Axiomen. Denn a1 und a2 erfüllen f (a1 ) = eH und f (a2 ) = eH . Deren Produkt liefert eH = eH ·H eH = f (a1 ) ·H f (a2 ) = f (a1 ·G a2 ). 20 1.3 Gruppen Definition 1.25. Die Menge f −1 (eH ) = {g ∈ G : f (g) = eH } aus dem letzten Lemma heisst Kern von f . Die Schreibweise ist Ker(f ). Das Bild von f ist die Menge ihrer Bildpunkte {f (g) : g ∈ G} und wird mit Bild(f ) bezeichnet. Der Kern eines Gruppenhomomorphismus enthält das neutrale Element der Gruppe und ist abgeschlossen unter der Verknüpfung- und der Inversionsabbildung. Die Elemente des Kerns bilden also wieder eine Gruppe wobei die Verknüpfung und Inversion von der umliegenden Gruppe G geerbt wird. Beispiel 1.26. Seien G, H und f wie in Teil (i) des letzten Beispiels. Also gilt f (a) = na für alle a ∈ Z. Falls n = 0 so ist f konstant 0. In anderen Worten, Ker(f ) = Z. Falls n 6= 0 so haben wir a ∈ Ker(f ) ⇔ na = 0 ⇔ a = 0. Also gilt Ker(f ) = {0}. Lemma 1.27. Seien (G, eG , ·G ) und (H, eH , ·H ) Gruppen und f : G → H ein Gruppenhomomorphismus. Dann ist f injektiv ⇐⇒ Ker(f ) = {eG } Beweis. Wir wissen von Lemma 1.24(i), dass f (eG ) = eH gilt. In anderen Worten eG ∈ Ker(f ). Sei g ∈ Ker(f ), es gilt also f (g) = eH . Falls f injektiv ist, so muss g = eG gelten. Damit haben wir die Implikation “=⇒” bewiesen. Nehmen wir nun an, dass Ker(f ) = {eG } gilt und dass g, h Element aus G sind, die f (g) = f (h) erfüllen. Hieraus folgt eH = f (h)−1 ·H f (g) = f (h−1 ) ·H f (g) = f (h−1 ·G g), die zweite Gleichung folgt aus Lemma 1.24(i) und die letzte aus der Definition des Gruppenhomomorphismus. Weil eG das einzige Element von Ker(f ) ist, folgt h−1 ·G g = eG . Nach Linksmultiplikation mit h und wegen h ·G h−1 = eG (Lemma 1.19(i)) folgt g = h. Damit ist bewiesen, dass f injektiv ist. Definition 1.28. Sei (G, e, ·) eine Gruppe (in multiplikativer Schreibweise). Eine Untergruppe dieser Gruppe ist eine Teilmenge H ⊆ G die folgende Eigenschaften erfüllt. (i) Es gilt e ∈ H. (ii) Für alle a, b ∈ H gilt ab ∈ H. (iii) Für alle a ∈ H gilt a−1 ∈ H. Beispiel 1.29. (i) Sicher ist 0 ∈ Z durch zwei teilbar. Weiterhin ist die Summe zweier geraden Zahlen wieder gerade und falls a durch zwei teilbar ist, so ist auch −a durch zwei teilbar. Also bildet die Menge der durch zwei teilbaren Zahlen {a ∈ Z : a gerade} eine Untergruppe von Z. (ii) Ein beliebige Gruppe (G, e, m) besitzt immer {e} als Untergruppe. Zu dem ist G selbst eine Untergruppe. Beide Behauptungen folgen direkt aus den Definitionen. Diese Untergruppen nennt man die trivialen Untergruppen. 21 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Bemerkung 1.30. (i) Eine Untergruppe H einer Gruppe (G, e, m) definiert, zusammen mit dem neutralen Element und der Verknüpfung selbst eine Gruppe. Der Beweis dafür folgt leicht: die Verknüpfung zweier Elemente aus H liegt in H wegen Eigenschaft (ii). Die Verknüpfungsabbildung erfüllt (A), weil G eine Gruppe ist. Weiterhin ist auch (N) erfüllt, weil es auf G gilt. Schliesslich gilt auch (I). (iii) Der Kern jedes Gruppenhomomorphismus ist eine Untergruppe. Dies folgt aus Lemma 1.24. Wir haben schon ein genügend grosses Vokabular zur Behandlung von Gruppen in der linearen Algebra. Es folgt nun ein kleiner Abschnitt, der verdeutlichen soll, dass der Gruppenbegriff zwar elementar, aber sehr facettenreich ist. Heute ist das Studium endlicher Gruppen ein aktuelles Forschungsgebiet. Wir haben oben gesehen, dass jeder Kern eines Gruppenhomomorphismus eine Untergruppe liefert. Nun kann man sich fragen, ob umgekehrt jede Untergruppe einer Gruppe als Kern eines Gruppenhomomorphismus auftaucht. Man kann sich davon überzeugen, dass die trivialen Untergruppen, d.h. die ganze Gruppe und {e}, als Kern auftauchen. Im Allgemeinen muss eine Untergruppe einer Gruppe jedoch kein Kern eines Gruppenhomomorphismus sein. Es gibt sogar nicht-triviale Gruppen, bei denen jede nicht-triviale Untergruppe kein Kern ist. Solche Gruppen nennt man einfach. Einfache endliche Gruppen spielen die Rolle der Elementarteilchen in der Physik oder der Primzahlen in der Arithmetik, sie sint die Bausteine der Gruppentheorie. Die Klassifikation aller endlichen einfachen Gruppen war für lange Zeit ein wichtiges Problem. Satz (Klassifikationssatz für endliche einfache Gruppen ca. 2006). Sei G eine endliche einfache Gruppe. Dann ist G in einer von 18 Familien enthalten oder G ist eine der 26 sporadischen endlichen einfachen Gruppen. Beweis. 10.000 Seiten. Die grösste sporadische Gruppe heisst Monstergruppe und wird üblicherweise mit M bezeichnet. Ihre Existenz wurde in 1983 von Griess bewiesen, nachdem sie von Bernd Fischer in der Dekade zuvor vermutet wurde. Ihre Ordnung ist #M = 246 · 320 · 59 · 76 · 112 · 133 · 17 · 19 · 23 · 29 · 31 · 41 · 47 · 59 · 71. Sie beschreibt die Symmetrie eines Objekts im 196883-dimensionalem Raum. 1.4 Ringe und Körper Im letzten Abschnitt haben wir die Menge Z mit zusätzlicher Struktur einer Gruppe versehen. Wir haben dabei schon wieder etwas vernachlässigt. Wir können zwei Elemente in Z auch miteinander multiplizieren und erhalten ein neues Element in Z. Diese Verknüpfung 22 1.4 Ringe und Körper definiert jedoch keine Gruppe, denn das multiplikative Inverse zu 2 ist 1/2 und liegt ausserhalb von Z. Der Ringbegriff berücksichtigt dieses Phänomen und auch die Tatsache, dass die Addition und Multiplikation in Z durch das Distributivgesetz verbunden sind: a · (b + c) = a · b + a · c für a, b, c ∈ Z. (1.2) In der Definition eines Rings tauchen nun zwei Operationen auf. Die eine entspricht der Addition in Z und die andere der Multiplikation. Nun kommen wir zur formalen Definition eines Rings. Definition 1.31. Ein Ring ist ein Tupel (R, 0, s, 1, m) bestehend aus einer Menge R, einem Element 0 ∈ R genannt Nullelement, einer Abbildung s : R × R → R genannt Addition, einem Element 1 ∈ R genannt Einselement und einer Abbildung m : R × R → R genannt Multiplikation mit den folgenden Eigenschaften. (i) Das Tupel (R, 0, s) ist eine abelsche Gruppe, wir nennen sie die additive Gruppe von R. (ii) (Assoziativität der Multiplikation) Für alle a, b, c ∈ R gilt m(m(a, b), c) = m(a, m(b, c)) oder (ab)c = a(bc) in der üblichen Notation. (iii) (Neutrales Element der Multiplikation.) Für alle a ∈ R gilt m(1, a) = m(a, 1) = a oder 1a = a1 = a in der üblichen Notation. (iv) (Distributivgesetz) Für alle a, b, c ∈ R gilt m(a, s(b, c)) = s(m(a, b), m(a, c)) und m(s(b, c), a) = s(m(b, a), m(c, a)) oder a(b + c) = (ab) + (ac) und (b + c)a = (ba) + (ca) in der üblichen Notation. Der Ring heisst kommutativ, falls zusätzlich die folgende Eigenschaft erfüllt ist. (v) (Kommutativgesetz) Für alle a, b ∈ R gilt m(a, b) = m(b, a) oder ab = ba in der üblichen Notation. Spätestens jetzt wird die Notation wegen den zwei Operationen s (die Summation) und m (die Multiplikation) schwerfällig. Deshalb werden wir ab jetzt fast ausschliesslich mit der für uns natürlichen Notation schreiben. Konkret schreiben wir a · b oder ab anstatt m(a, b) 23 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper und a + b anstatt s(a, b) für a und b Elemente eines Rings. Es ist auch sehr praktisch −a für das additive Inverse von a zu schreiben. Weiterhin setzen wir a + (−b) = a − b. Dabei gilt wie üblich die Konvention “Punkt vor Strich”. D.h. wir kürzen (ab) + c durch ab + c ab. Aus diesem Grund wurde vorsorglich das neutrale Element bezüglich + mit der 0 und das neutrale Element bezüglich der Multiplikation mit der 1 bezeichnet. Achtung. Dennoch sollte man sich im Klaren sein, dass + oder · möglicherweise nichts mit den aus der Schule bekannten Rechenoperationen auf den ganzen, rationalen oder reellen Zahlen gemeinsam haben. Um die Notation weiter zu vereinfachen, werden wir oft, wie bei den Gruppen, einen Ring mit der Menge R identifizieren. D.h. steht irgendwo “Sei R ein Ring . . . ”, so meinen wir damit ein Tupel wie in der Definition. Achtung. Die Definition eines Rings ist nicht ganz ohne Kontroversen. So ist in manchen Quellen die Kommutativität der Multiplikation Bestandteil der Definition während andere Quelle so weit gehen, und nicht die Existenz eines neutralen Elements bezüglich der Multiplikation fordern. Wir werden uns hauptsächlich mit kommutativen Ringen beschäftigen. Ringe, die mittels Matrizenmultiplikation definiert werden, werden jedoch im Allgemeinen nicht kommutativ sein. Beispiel 1.32. (i) Wir kennen implizit schon viele kommutative Ringe, wie Z, Q und R mit den klassischen Operationen. (ii) Wie immer gibt es ein pathologisches Beispiel: der Nullring. Die zugrunde liegende Menge ist R = {0}. Es gibt nur eine Wahl für eine Abbildung R × R → R und für eine Abbildung R → R. Und man überprüft leicht nach, dass diese sowohl die Eigenschaften der Addition und der Multiplikation erfüllen. Folglich ist der Nullring ein Ring und sogar ein kommutativer Ring. Beachte, dass 1 = 0 im Nullring gilt! Der Nullring ist der einzige Ring, in welchem 1 = 0 gilt. Diese Aussage werden wir in Kürze beweisen. (iii) Sei R ein Ring und sei X zunächst ein Symbol. Wir können den Ring R[X] der Polynome über R wie folgt definieren. Die Elemente von R[X] sind Polynome in 24 1.4 Ringe und Körper einer Variable X und Koeffizienten in R. In anderen Worten, die Elemente von R[X] sind von der Form n an X + an−1 X n−1 + · · · + a1 X + a0 = n X ak X k k=0 wobei n P∈n N∪{0}k und Pma0 , . . . k, an ∈ R. Die Addition auf R[X] ist wie folgt definiert. Seien k=0 ak X , k=0 bk X ∈ R[X]. Man setzt ! ! max{m,n} n m X X X ak X k + bk X k = (ak + bk )X k k=0 k=0 k=0 wobei ak = 0 für k > n und bk = 0 für k > m gesetzt wird. Nun müssen wir auch eine Multiplikationsabbildung definieren. Dies geschieht wie folgt. Wir setzen ! m ! n+m k ! n X X X X ak X k bk X k = al bk−l X k k=0 k=0 k=0 l=0 Das neutrale Element der Addition von R[X] definieren wir als 0 ∈ R und das neutrale Element der Multiplikation als 1 ∈ R. Es wird eine Übungsaufgabe sein nachzuprüfen, dass R[X] zusammen mit diesen Operationen einen Ring definiert. Falls R kommutativ ist, so wird R[X] kommutativ sein. Falls A = an X n + · · · + a1 X + a0 ∈ R[X] mit an 6= 0 so definieren wir den Grad des Polynoms A als deg(A) = n ≥ 0. Beachten Sie, dass wir den Grad des Polynoms 0 ∈ R[X] nicht definiert haben. Wir halten nun einige formale Konsequenzen der Ringaxiome fest. Dabei wird man einige bekannte Rechenregeln wiedererkennen. Lemma 1.33. Sei R ein Ring und a ∈ R. (i) Es gilt 0 · a = a · 0 = 0. (ii) Gemäss Definition ist das additive Inverse von a gleich −a. Es gilt −a = (−1)·a = a · (−1) und (−1) · (−1) = 1. Beweis. Distributivität ergibt 0 · a = (0 + 0) · a = 0 · a + 0 · a. Addiert man nun −0 · a zu dieser Gleichung, so erhält man 0 = 0 · a. Der Beweis für a · 0 = 0 ist völlig analog. Daraus ergibt sich Teil (i). Gemäss Definition und Teil (i) haben wir ((−1) + 1) · a = 0 · a = 0. Wenden wir Distributivität an, so folgt 0 = (−1) · a + 1 · a = (−1) · a + a. Wegen Lemma 1.19(iii) ist das additive Inverse in einer Gruppe eindeutig bestimmt. Daraus folgt −a = (−1) · a und −a = a · (−1) lässt sich analog zeigen. 25 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Wir müssen noch (−1) · (−1) = 1 zeigen. Aus Teil (i) und Distributivität folgt 0 = 0 · 0 = ((−1) + 1) · ((−1) + 1) = (−1) · (−1) + (−1) · 1 + 1 · (−1) + 1 · 1. Da 1 das neutrale Element bezüglich Multiplikation ist, haben wir 0 = (−1) · (−1) + (−1) + (−1) + 1 = (−1) · (−1) + (−1). Also muss (−1) · (−1) = 1 gelten. Bemerkung 1.34. Jeder Ring R ist mit einer Multiplikationsabbildung ausgestattet. Diese definiert jedoch fast nie eine Gruppenstruktur auf R. Nehmen wir mal an, dass sie es doch tut. Dann besitzt 0 ein multiplikatives Inverses x, also muss 0 · x = 1 gelten. Teil (i) des letzten Lemmas impliziert 0 = 1. Jedes a ∈ R ist von der Form a = 1·a = 0·a = 0. Also ist R der Nullring. Wir halten fest: ist R nicht der Nullring, so definiert die Multiplikation keine Gruppenstruktur mit neutralem Element 1. Wenn wir das Nullelement 0 vernachlässigen, dann gibt es interessante Ringe, bei denen die Multiplikation eine Gruppe definiert. Diese nennt man Körper und sie haben in der linearen Algebra eine besondere Bedeutung. Definition 1.35. Ein kommutativer Ring K heisst Körper, falls die folgende Eigenschaft erfüllt ist. (vi) Es gilt 0 6= 1 und für jedes a ∈ K r {0} gibt es ein a0 ∈ K mit a0 a = 1. Lemma 1.36. Sei K ein Körper. (i) Sind a, b ∈ K mit ab = 0 so gilt a = 0 oder b = 0. (ii) Die Menge K r {0} zusammen mit dem Element 1 ∈ K r {0} und der Multiplikation, ist eine abelsche Gruppe. Wir nennen sie multiplikative Gruppe von K und schreiben K × = K r {0}. Beweis. Seien a, b ∈ K mit ab = 0. Wir möchten a = 0 oder b = 0 beweisen. Wir können also a 6= 0 annehmen, ansonsten ist die Aussage schon bewiesen. Axiom (iv) in der Definition eines Körpers impliziert, dass es ein a0 ∈ K gibt mit a0 a = 1. Aus Lemma 1.33(i) erhalten wir 0 = a0 0 = a0 (ab) = (a0 a)b = 1b = b. Hieraus folgt Teil (i). Teil (i) lässt sich wie folgt umformulieren: falls a, b ∈ K mit a 6= 0 und b 6= 0, so gilt ab 6= 0. Also nimmt die Multiplikationsabbildung m(a, b) = ab Werte in K r {0} an, falls a, b ∈ K r {0}. Sie definiert also eine Abbildung (K r {0}) × (K r {0}) → K r {0}. Gemäss Definition von K gilt 0 6= 1, also liegt 1 ∈ K r {0}. 26 1.4 Ringe und Körper Für a ∈ K r {0} gibt es ein a0 ∈ K mit a0 a = 1. Wir definieren eine Abbildung i : K r {0} → K durch i(a) = a0 . Wir halten aber fest, dass i(a) 6= 0 gelten muss, den andererseits wäre 1 = i(a)a = 0a = 0 wegen Lemma 1.33(i). Also ist i eine Abbildung K r {0} → K r {0}. Um Teil (ii) zu beweisen, müssen wir zeigen, dass K r {0} mit den soeben beschrieben Abbildungen eine Gruppe mit neutralem Element 1 ist. Die Assoziativität der Multiplikation (A) folgt aus (ii) in der Definition eines Rings, Axiom (N) im Gruppenbegriff folgt aus (iii) in derselben Definition, schliesslich folgt (I) aus (iv) in der Definition eines Körpers. Bemerkung 1.37. (i) Wir halten nochmals das Kontrapositiv von Teil (i) im obigen Lemma fest. Sind a, b Elements eines Körper mit a 6= 0 und b 6= 0, so ist ab 6= 0. (ii) Aus unserer Definition folgt, dass 1 ∈ K r {0}. Insbesondere besitzt ein Körper mindestens zwei Elemente. (iii) Da K r {0} (mit der Multiplikation) eine Gruppe bildet, können wir kürzen, siehe dazu Lemma 1.19(iv). Konkret, falls a, b, c ∈ K mit a 6= 0 und ab = ac so gilt b = c. (iv) Gemäss Definition ist jeder Körper ein Ring. Die Umkehrung gilt nicht, d.h. wir werden unten in einem Beispiel sehen, dass es Ringe gibt, die keine Körper sind. Beispiel 1.38. (i) Der Ring der rationalen Zahlen Q ist ein Körper. Das gleiche gilt für den Ring der reellen Zahlen R. (ii) Die komplexen Zahlen C (siehe Vorlesung Analysis) bilden einen Körper. (iii) Der Ring der ganzen Zahlen Z ist kein Körper, da 1/2 ∈ Q r Z. (iv) Bis jetzt kennen wir nur Körper mit unendlich vielen Elementen. Ein Körper muss per Definition mindestens zwei Elemente enthalten. Das lässt eine grosse Lücke zu. Wir zeigen nun, dass es einen Körper F2 mit genau zwei Elementen gibt. Wir machen den Ansatz F2 = {0, 1} mit 0 6= 1 zwei Symbole. Bezüglich der Addition muss F2 eine abelsche Gruppe sein. Die folgende Additionstabelle (die wir schon einmal gesehen haben) definiert diese Gruppenstruktur: + 0 1 0 1 0 1 1 0 Somit ist Axiom (i) in der Definition eines Rings erfüllt. Für die Multiplikationstabelle gibt es wegen Lemma 1.33 nur eine Möglichkeit: · 0 1 0 1 0 0 0 1 27 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Also definiert die Multiplikation auf F2 r {0} = {1} eine Gruppenstruktur: die der trivialen Gruppe. Daraus folgt Axiom (vi) in der Definition des Körpers. Die Axiome (ii), (iii) und (v) in der Definition des Ringbegriffs folgen im Fall a = b = c = 1, da F2 r {0} eine Gruppe ist. Die Aussagen dieser drei Axiome gelten auch, falls a = 0, b = 0 oder c = 0, da 0x = 0 für alle x ∈ F2 . Für das Distributivgesetz, also Axiom (iv), reicht es wegen der Kommutativität der Multiplikation a(b + c) = ab + ac für alle a, b, c ∈ F2 zu zeigen. Für a gibt es nur die Möglichkeiten 0 und 1. Ist a = 0, so steht links und rechts 0 wegen Lemma 1.33(i). Ist a = 1, so gilt a(b + c) = 1(b + c) = b + c = 1b + 1c = ab + ac, was zu zeigen war. Dieses Argument impliziert Axiom (iv). Also sind alle Axiome erfüllt. Daher ist F2 ein Körper, der kleinste Körper, den es gibt. In F2 gilt die bemerkenswerte Gleichung 1+1=0 oder, was äquivalent ist, −1 = 1. Es können also keine Vorzeichenfehler passieren! Sei K ein Körper. Da K auch ein Ring ist, erhalten wir aus der Konstruktion aus dem vorigen Abschnitt den Ring K[X] der Polynome mit Koeffizienten in K. Zur Erinnerung, Elemente aus K[X] sind von der Form an X n + an−1 X n−1 + · · · + a1 X + a0 mit an , . . . , a0 ∈ K für ein n ∈ N ∪ {0}. Wir werden weiter unten sehen, dass K[X] nie ein Körper ist. Lemma 1.39. Sei K ein Körper. (i) Seien A, B ∈ K[X] r {0}. Dann gilt AB 6= 0 und deg(AB) = deg(A) + deg(B). (ii) Der Ring K[X] ist kein Körper. Beweis. Um Teil (i) zu beweisen, schreiben wir A = an X n + · · · + a0 mit an 6= 0 und B = bm X m + · · · + b0 mit bm 6= 0. Die Definition des Grads impliziert deg(A) = n und deg(B) = m. Wir berechnen das Produkt AB = (an X n + · · · + a0 )(bm X m + · · · + b0 ) = an bm X n+m + (an bm−1 + an−1 bm )X n+m−1 + · · · + (a1 b0 + a0 b1 )X + a0 b0 . (1.3) Nun sind an 6= 0 und bm 6= 0. Somit ist das Produkt an bm 6= 0 weil K ein Körper ist, cf. Lemma 1.36(i). Da der Term an bm X n+m nicht durch die weiteren Summanden in AB weggekürzt werden kann, haben wir AB 6= 0. Insbesondere ist der Grad deg(AB) wohldefiniert. Schliesslich sehen wir aus (1.3), dass deg(AB) = n+m = deg(A)+deg(B) gilt. Somit ist Teil (i) bewiesen. Nun kommen wir zu (ii). Wäre K[X] ein Körper, so gäbe es A ∈ K[X] mit XA = 1. Dies wird zu einem Widerspruch führen. Es gilt deg(1) = 0 und deg(X) = 1. Wenden wir Teil (i) an, so erhalten wir 1 + deg(A) = 0 und somit deg(A) = −1. Dies ist ein Widerspruch, da der Grad eines Polynoms nie negativ sein kann. 28 1.4 Ringe und Körper Definition 1.40. Eine natürliche Zahl p nennt man Primzahl, falls p ≥ 2 und falls p in N nur die Teiler 1 und p besitzt. Bemerkung 1.41. (i) In einem Körper K kann man wie “gewohnt” rechnen. Sind a, b ∈ K mit b 6= 0 so schreiben wir b−1 für das multiplikative Inverse von b und wir kürzen a ab. b−1 a = ab−1 durch b (ii) Es gibt weitere endliche Körper. Für jede Primzahl p ∈ {2, 3, 5, 7, . . .} und jede natürliche Zahl n ∈ N gibt es einen Körper Fpn der Kardinalität pn . Das sind schon sämtliche endliche Körper. Die Existenz der Fp werden wir im Laufe des Semesters beweisen. Die restlichen Aussagen dieser Bemerkung werden vielleicht in höheren Vorlesungen behandelt. Wir haben gesehen, dass in F2 die Gleichung 1 + 1 = 0 gilt. Das Element 2 kommt nicht in der Definition des Körpers vor. Jedoch können wir 2=1+1 in einem beliebigen Körper K definieren und somit hat 2 eine Bedeutung als Element von K. Dasselbe kann man für jede natürliche Zahl n ∈ N ∪ {0} machen n := |1 + ·{z · · + 1} ∈ K. (1.4) n Summanden Hier ist 0 = 0 in K. Für negative n ∈ Z definieren wir n := − (1 + · · · + 1) ∈ K | {z } −n > 0 Summanden In dieser Notation gilt 2 = 0 im Körper F2 . Später werden wir einfach n für n schreiben. Hier spielt uns die Notation einen Streich: das “n” ist je nach Situation ein Element in K und darf dann nicht mit der natürlichen Zahl, die wir auch mit n bezeichnen, verwechselt werden! Dieses Phänomen führt zu einer wichtigen Invariante eines Körpers, die Charakteristik. Lemma 1.42. Sei K ein Körper. Angenommen es gibt eine natürliche Zahl n ∈ N mit n = 0 als Element von K. Dann gibt es eine kleinste natürliche Zahl mit dieser Eigenschaft und diese ist eine Primzahl. Beweis. Falls es n ∈ N mit n = 0 in K gibt, so gibt es sicherlich ein kleinstes n mit dieser Eigenschaft. Es reicht also zu zeigen, dass dieses n eine Primzahl ist. Sicher gilt n 6= 1 da 1 = 1 6= 0 in einem Körper. Also haben wir n ≥ 2. Falls n = tt0 mit t, t0 ∈ N so zeigt man rasch, dass n = t · t0 = 0. Aus Lemma 1.36(i) folgt nun t = 0 oder t0 = 0. Aus der Symmetrie der Situation können wir annehmen, dass t = 0 gilt. Aus der Minimalität von n folgt t ≥ n. Aber t ist ein Teiler von n, also t ≤ n. Somit gilt t = n und t0 = 1. Hieraus folgt, dass n nur zwei Teiler hat. Also ist n eine Primzahl. 29 1 Algebraische Grundlagen: Mengen, Gruppen, Ringe, Körper Definition 1.43. Sei K ein Körper. Falls es n ∈ N gibt mit n = 0 in K. Dann nennt man die Primzahl, welche wir aus dem letzten Lemma erhalten, die Charakteristik von K. Falls n 6= 0 für alle n ∈ N gilt, so wird die Charakteristik von K als 0 definiert. Beispiel 1.44. C. (i) Die Charakteristik von Q ist 0. Dasselbe gilt für die Körper R und (ii) Die Charakteristik von F2 ist 2. 30 2 Matrizenkalkül Bislang haben wir algebraische Strukturen wie Gruppen, Ringe und Körper eingeführt. In diesem Kapitel werden wir hauptsächlich in einem Körper K arbeiten und lineare Abbildungen sowie lineare Gleichungen systematisch untersuchen. Lineare Gleichungen und Abbildungen tauchen überall in der Mathematik auf. Sie spielen auch in der Physik und anderen Naturwissenschaften eine wichtige Rolle. Lineare Gleichungen gehören zu den einfachsten Gleichungen, die untersucht werden. Ihre Bedeutung stammt aus der Tatsache, dass sie die einzigen Gleichungen sind, die sich systematisch lösen lassen. Grob gesagt sind lineare Abbildungen, die einfachste Art Abbildung. Die lineare Algebra ist das Studium von linearen Gleichungen und Abbildungen. Das wichtigste Hilfsmittel bei der Untersuchung von linearen Abbildungen und Gleichungen ist die Matrix. Beispiel 2.1. (i) Als einführendes Beispiel untersuchen wir die Drehung der Ebene um einen Winkel θ ∈ R. Als Ebene verstehen wir das kartesische Produkt R2 = R× R. Die in der Mathematik natürliche Einheit für die Drehung ist der Bogenwinkel, d.h. eine Drehung um π/2 entspricht einer Drehung um 90 Grad, eine Drehung um π entspricht einer Drehung um 180 Grad, usw. Wir untersuchen den Fall√der Drehung um θ = π/4 (also um 45 Grad). Dabei √ √ √ wird der Punkt (1, 0) auf ( 2/2, 2/2) gedreht und (0, 1) wird auf (− 2/2, 2/2) gedreht. Wir schreiben √ √ √ √ Dπ/4 ((1, 0)) = ( 2/2, 2/2) und Dπ/4 ((0, 1)) = (− 2/2, 2/2). Wie wird ein allgemeiner Punkt (x, y) ∈ R2 gedreht? Hier nutzen wir die Linearität aus, dieses Konzept steht im Zentrum der linearen Algebra. Es gilt Dπ/4 ((x + x0 , y + y 0 )) = Dπ/4 (x, y) + Dπ/4 (x0 , y 0 ) für zwei Punkte (x, y), (x0 , y 0 ) der Ebene R2 , wobei komponentenweise addiert wird. Wir schreiben (x, y) = (x + 0, 0 + y) und erhalten √ √ √ √ Dπ/4 (x, y) = Dπ/4 (x, 0) + Dπ/4 (0, y) = ( 2x/2, 2x/2) + (− 2y/2, 2y/2), da (x, 0) aus (1, 0) durch Streckung um den Faktor x entsteht, und Drehung und Streckung vertauschen (analoges gilt für (0, y)). Wir finden, dass (x, y) durch Drehung um π/4 in √ √ √ √ ! 2 2 2 2 x− y, x+ y 2 2 2 2 31 2 Matrizenkalkül überführt wird. Diese Drehung ist ein typisches Beispiel einer linearen Abbildung. Ihr Studium bildet den Kern der linearen Algebra. Wir werden diese Abbildung durch eine Matrix √ ! √ 2 −√ 22 √2 2 2 2 2 repräsentieren. (ii) Für θ ∈ R ist die Drehung um den Winkel θ durch (x, y) 7→ (x0 , y 0 ) = cos(θ)x + (− sin θ)y, sin(θ)x + cos(θ)y gegeben. Ordnung wir die Einträge zusammen, erhalten wir die Matrix cos θ − sin θ Dθ = , sin θ cos θ welche unsere Drehung repräsentiert. (iii) Für reelle Zahlen a, b, c, d ∈ R erhalten wir eine durch (x, y) 7→ (x0 , y 0 ) = (ax + by, cx + dy). definierte Abbildung R2 → R2 . Wir werden sie später als lineare Abbildung erkennen und sie durch die Matrix a b c d repräsentieren. (iv) Ein Beispiel eines linearen Gleichungssystems mit Koeffizienten im Körper Q und zwei Unbekannten ist 3x + 5y = 0. (2.1) Hier sind x und y die unbekannten Variablen. Dieses Gleichungssystem besitzt unendliche viele Lösungen: für jedes λ ∈ Q wird durch x = −5λ und y = 3λ eine Lösung gegeben. Auch Gleichungssysteme lassen sich durch Matrizen repräsentieren. Die entsprechende Matrix lautet hier 3 5 . Man möchte jedoch auch mehrere Gleichungen gleichzeitig behandeln: x + 2y = 0 −3x + 5y = 0. (2.2) (2.3) Dieses Gleichungssystem hat genau eine Lösung x = y = 0. Im letzten Beispiel erhalten wir die Matrix 1 2 . −3 5 32 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt Matrizen sind wichtige Werkzeuge, um lineare Abbildungen und Gleichungen zu studieren. Sie besitzen aber auch ein Eigenleben und werden in späteren Kapiteln eine neuen Rolle annehmen. Ziel dieses Kapitels ist es, • Matrizen zu definieren • mit Matrizen zu rechnen, d.h. Addition, Skalarmultiplikation und Matrixprodukt werden eingeführt, • und lineare Gleichungssystem mit der Hilfe von Matrizen zu lösen und Matrizen in die sogenannte Zeilenstufenform zu bringen. 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt Definition 2.2. Sei K ein beliebiger Körper Koeffizienten in K ist ein Element a1,1 a1,2 a2,1 a2,2 A = .. .. . . am,1 am,2 und m, n ∈ N. Eine m × n Matrix mit ··· ··· ... a1,n a2,n .. . ··· am,n des mn-fachen Kartesischen Produkts K mn . Das heisst, die ai,j sind Elemente von K. Die Menge der m × n Matrizen mit Koeffizienten in K wird mit Matm,n (K) bezeichnet. Ist m = n so nennt man m × m Matrizen quadratisch und benutzt die abkürzende Schreibweise Matm (K) = Matm,m (K). Bemerkung 2.3. Elemente in Matm,n (K) sind Matrizen mit m Zeilen und n Spalten, beachten Sie die Reihenfolge der Anzahl Zeilen und Spalten in der Schreibweise Matm,n (K). Ist A ∈ Matm,n (K) wie in der Definition, so bezeichnet ai,j den Koeffizienten in der i-ten Zeile und j-ten Spalte von A. Beispiel 2.4. (i) Die Matrix 3 5 ∈ Mat1,2 (Q) besitzt als Koeffizienten die rationalen Zahlen, die im Beispiel (2.1) auftauchen. (ii) Die Matrix 1 2 −3 5 ∈ Mat2,2 (Q) besitzt als Koeffizienten genau die rationalen Zahlen, die im Beispiel (2.2) auftauchen. Diese Matrix ist, im Gegensatz zur Matrix im ersten Beispiel, quadratisch. Es gibt zwei Matrizen, die eine besondere Rolle spielen. 33 2 Matrizenkalkül Definition 2.5. Sei K ein Körper und m, n ∈ N. (i) Die Nullmatrix ist durch 0m,n 0 ··· 0 = ... . . . ... ∈ Matm,n (K) 0 ··· 0 gegeben, d.h. alle Koeffizienten sind 0. Oft werden wir die Indizes in 0m,n weglassen und das Symbol 0 für die Nullmatrix verwenden. (ii) Sei m = n, also sind die Elemente von Matm (K) quadratische Matrizen. Die Einheitsmatrix oder Einsmatrix oder Identitätsmatrix ist durch 1 0 ··· 0 0 1 ··· 0 .. . . . . Em = . ∈ Matm (K) . . 0 ··· 1 0 0 ··· 0 1 gegeben, d.h. alle Koeffizienten auf der Diagonale sind 1 und die restlichen sind 0. Auch hier werden wir oft E anstatt Em schreiben. Beachten Sie, dass die Einheitsmatrix nicht ausschliesslich aus der 1 ∈ K besteht! Die Erklärung dafür werden wir sehen, sobald wir das Produkt zweier Matrizen kennen. Zwei Matrizen mit Koeffizienten im selben Körper und welche die gleiche Anzahl Zeilen und Spalten besitzen lassen sich summieren. Definition 2.6. Sei a1,1 a2,1 A = .. . am,1 K ein Körper und m, n ∈ N. Sind a1,2 · · · a1,n b1,1 b1,2 b2,1 b2,2 a2,2 · · · a2,n .. .. und B = .. .. .. . . . . . am,2 · · · am,n bm,1 bm,2 in Matm,n (K) so ist ihre Summe komponentenweise durch a1,1 + b1,1 a1,2 + b1,2 · · · a1,n + b1,n a2,1 + b2,1 a2,2 + b2,2 · · · a2,n + b2,n A+B = .. .. .. ... . . . am,1 + bm,1 am,2 + bm,2 · · · am,n + bm,n ··· ··· .. . b1,n b2,n .. . ··· bm,n ∈ Matm,n (K) gegeben. Achtung. Zwei Matrix müssen die gleiche Anzahl Spalten und Zeilen haben, um summierbar zu sein. 34 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt Beispiel 2.7. (i) Seien 1 2 A= ∈ Mat2 (Q) 3 4 und B= −4 2 −9 15 ∈ Mat2 (Q) (2.4) so gilt A+B = −3 4 −6 19 ∈ Mat2 (Q). (ii) Zwei nicht quadratische Matrizen mit Koeffizienten in F2 lassen sich auch summieren. Falls 1 1 A= und B = 0 1 mit A, B ∈ Mat2,1 (F2 ) so ist A+B = 1+1 0+1 = 0 1 . 1 0 (iii) Sei E2 = die 2 × 2 Einheitsmatrix mit Koeffizienten in Q. Nach dem 0 1 Rezept von Beispiel 2.1 können wir eine Abbildung R2 → R2 wie folgt definieren (x, y) 7→ (1 · x + 0 · y, 0 · x + 1 · y) = (x, y). Es handelt sich um die Identitätsmatrix. Dies ist die Begründung für die Bezeichnung “Einheitsmatrix”. Wir werden nun die Skalarmultiplikation eines Elements aus K mit einer Matrix mit Koeffizienten aus K definieren. Definition 2.8. Sei K ein Körper und a1,1 a2,1 A = .. . am,1 m, n ∈ N. Ist λ ∈ K und a1,2 · · · a1,n a2,2 · · · a2,n .. .. .. . . . am,2 · · · am,n so ist das Skalarmultiplikation von λ λa1,1 λa2,1 λA = .. . λam,1 mit A durch ··· ··· ... λa1,n λa2,n .. . λam,2 · · · λam,n λa1,2 λa2,2 .. . gegeben. In anderen Worten, wir multiplizieren jeden Eintrag von A mit dem “Skalar” λ. 35 2 Matrizenkalkül Beispiel 2.9. (i) Seien A und B wie in (2.4). Es gilt 2 4 4 −2 2A = und (−1)B = . 9 −15 6 8 (ii) Sei K ein beliebiger Körper, m, n ∈ N und A ∈ Matm,n (K). Aus den Resultaten über Körper des letzten Kapitels folgern wir 0A = 0m,n und (−1)A + A = 0m,n . (2.5) Das letzte Beispiel legt nahe, dass Matrizen bezüglich der Addition eine Gruppe bilden. Lemma 2.10. Sei K ein Körper und m, n ∈ N. Die Menge der Matrizen Matm,n (K) zusammen mit der Matrizenaddition, dem Element 0m,n , und der durch (2.5) definierten Abbildung ist eine abelsche Gruppe. Beweis. Die Summe zweier Matrizen in Matm,n (K) liegt wieder in Matm,n (K). Dass die Summe assoziativ ist und dass 0m,n ein neutrales Element ist, folgt aus der Definition des Körpers. Jedes Element in Matm,n (K) besitzt zu dem ein additives Inverses (2.5). Nun stellt sich die Frage, ob man auch Matrizen miteinander multiplizieren kann. Als Ausgangslage steht die Repräsentation einer linearen Abbildung als Matrix, wie wir sie in Beispiel 2.1(i)–(iii) gesehen haben. Da wir Matrizen als Abbildung auffassen wollen, liegt es nahe, das Verhalten von Matrizen unter Verkettung zweier solcher Abbildungen zu untersuchen und dieses Verhalten als Vorlage für das Matrixprodukt zu nehmen. Beispiel 2.11. (i) Wir untersuchen zwei Abbildungen f : R2 → R2 und g : R2 → R2 , sie sollen durch f (x, y) = (ax + by, cx + dy) und g(x, y) = (a0 x + b0 y, c0 x + d0 y) definiert sein, wobei a, b, c, d, a0 , b0 , c0 , d0 ∈ R. Die Verkettung f ◦ g : R2 → R2 erhält man durch Einsetzung. (f ◦ g)(x, y) = a(a0 x + b0 y) + b(c0 x + d0 y), c(a0 x + b0 y) + d(c0 x + d0 y) = (aa0 + bc0 )x + (ab0 + bd0 )y, (ca0 + dc0 )x + (cb0 + dd0 )y . Die Abbildungen f und g werden vermöge dem Rezept in Beispiel 2.1(iii) durch 0 0 a b a b F = und G = c d c0 d0 36 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt repräsentiert. Schliesslich ist M= aa0 + bc0 ab0 + bd0 ca0 + dc0 cb0 + dd0 die Matrix, welche f ◦ g repräsentiert. Wir werden das Matrixprodukt aus F und G, also M definieren. Das Produkt zweier Matrizen entspricht das hintereinanderausführen von zwei Abbildungen. (ii) Wir untersuchen (i) im Spezialfall f = Dα und g = Dβ , also die Drehung der Ebene um α bzw. β. Die Verkettung Dα ◦ Dβ wird durch die Matrix cos(α) cos(β) − sin(α) sin(β) − cos(α) sin(β) − sin(α) cos(β) . sin(α) cos(β) + cos(α) sin(β) − sin(α) sin(β) + cos(α) cos(β) Die Additionstheorem vom Sinus und Kosinus implizieren, dass diese Matrix gleich cos(α + β) − sin(α + β) . sin(α + β) cos(α + β) Diese Matrix entspricht Drehung und den Winkel α + β. Dies ist dadurch erklärt, dass wir bei der Verkettung zuerst um β und dann um α gedreht haben, und dass zwei verkettete Drehungen der Ebene eine Drehung um die Summe der Drehwinkeln ist. Das Matrixprodukt verschlüsselt hier die Additionstheorem aus der Trigonometrie. Nun kommen wir zur Definition der Matrizenmultiplikation. Definition 2.12. Sei K ein Körper und m, n, p ∈ N. Das Produkt der zwei Matrizen a1,1 · · · a1,n b1,1 · · · b1,p .. ∈ Mat (K) und B = .. .. ∈ Mat (K). A = ... . m,n n,p . . am,1 · · · am,n bn,1 · · · bn,p ist a1,1 b1,1 + a1,2 b2,1 + · · · + a1,n bn,1 · · · .. AB = . am,1 b1,1 + am,2 b2,1 + · · · + am,n bn,1 · · · a1,1 b1,p + a1,2 b2,p + · · · + a1,n bn,p .. ∈ Matm,p (K). . am,1 b1,p + am,2 b2,p + · · · + am,n bn,p Völlig äquivalent schreiben wir C = AB mit C = (ci,k )1≤i≤m,1≤k≤p und ci,k = n X ai,j bj,k . j=1 Diese etwas eigentümlich Definition werden wir weiter unten an Beispielen üben. 37 2 Matrizenkalkül Bemerkung 2.13. (i) In der Definition oben ist zu beachten, dass die Anzahl Spalten n des ersten Faktors A gleich den Anzahl Zeilen des zweiten Faktors ist. Das Produkt aus B und A ist nur dann wohldefiniert, wenn m = p. (ii) Gilt m = n = p, sind also A und B quadratische Matrizen der gleichen Grösse, so lässt sich sowohl AB wie auch BA bilden. Beispiel 2.14. (i) Seien 1 2 A= ∈ Mat2 (Q) und 3 4 B= 8 7 6 5 ∈ Mat2 (Q) so gilt AB = 1·8+2·6 1·7+2·5 3·8+4·6 3·7+4·5 8·1+7·3 8·2+7·4 6·1+5·3 6·2+5·4 = 20 17 48 41 29 44 21 32 . Berechnen wir jedoch BA = = , so fällt AB 6= BA sofort ins Auge. Das Matrixprodukt ist für quadratische n × n Matrizen nicht kommutativ, falls n = 2. Es ist für n ≥ 3 ebenfalls nicht kommutativ. (ii) Sei A wie im Beispiel (i) und B= dann ist AB = −1 7 ∈ Mat2,1 (Q) 1 · (−1) + 2 · 7 3 · (−1) + 4 · 7 = 13 25 . Beachten Sie, dass das Produkt von B mit A nicht definiert ist! Die Anzahl Spalten von B ist ungleich der Anzahl Zeilen von A. (iii) Sei B wie in (ii) und C= 5 3 . Die Matrix B hat eine Spalte und C hat eine Zeile. Also ist BC definiert und gemäss Definition eine 2 × 2 Matrix. Es gilt −5 −3 BC = . 35 21 Da B zwei Zeilen hat, ist CB eine wohldefiniert 1 × 1 Matrix. Wir haben CB = ((−1) · 5 + 3 · 7) ∈ Mat1 (Q). Eine 1 × 1 Matrix können wir mit einem Element des Grundkörpers identifizieren. 38 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt (iv) Natürlich können wir auch Matrizen mit Koeffizienten in F2 multiplizieren. Seien 1 1 1 0 A= und 1 1 1 0 B= so gilt AB = 1·1+1·1 1·1+1·0 1·1+0·1 1·1+0·0 = 0 1 1 1 . (v) Sei K ein beliebiger Körper und A= a b c d ∈ Mat2 (K). Weiter oben haben wir die Einheitsmatrix in Matn (K) definiert. Für n = 2 erhalten wird E2 = E = 1 0 0 1 . Da A und E quadratische Matrizen mit der selben Anzahl Zeilen sind, sind sowohl AE wie auch EA definiert. Wir rechnen leicht nach, dass a·1+b·0 a·0+b·1 a b AE = = = A. c·1+d·0 c·0+d·1 c d Wie sieht es mit dem Produkt EA aus? 1·a+0·c 1·b+0·d a b EA = = = A. 0·a+1·c 0·b+1·d c d Dieses Beispiel zeigt, dass En ein neutrales Element bezüglich der Multiplikation ist für n = 2. Dies wird auch für jedes n ≥ 1 richtig sein. (vi) Ist A wie im Beispiel (v) so überrascht es nicht, dass A02,2 = 02,2 und 02,2 A = 02,2 gilt. Hier ist 02,2 die 2 × 2 Nullmatrix. Definition 2.15. Sei K ein Körper und m ∈ N. Eine Matrix in Mat1,m (K) nennt man auch Zeilenvektor (der Länge m). Entsprechend nennt man eine Matrix in Matm,1 (K) auch Spaltenvektor (der Länge m). Bemerkung 2.16. Sei K ein Körper und m, n ∈ N. Ist A = (ai,j )1≤i≤m,1≤j≤n ∈ Matm,n (K) so ist Av wohldefiniert für jeden Spaltenvektor v der Länge n. Das Produkt ist eine Matrix Matm,1 (K), d.h. ein Spaltenvektor der Länge m. 39 2 Matrizenkalkül Beispiel 2.17. Sei A= 1 2 3 3 2 1 und 1 v= 0 −1 so gilt Av = −2 2 . Wir halten im nächsten Lemma einige Rechenregeln des Matrixprodukts fest. Lemma 2.18. Sei K ein Körper und m, n, p, q ∈ N. (i) Sei A ∈ Matm,n (K), B ∈ Matn,p (K) und C ∈ Matp,q (K). Dann gilt das Assoziativgesetz (AB)C = A(BC). (Man soll sich davon überzeugen, dass alle vier Produkte wohldefiniert sind, wie vielen Spalten bzw. Zeilen hat das Produkt (AB)C?.) (ii) Sind A, B ∈ Matm,n (K) und C ∈ Matn,p (K), so haben wir Distributivität (A + B)C = AB + AC. Liegt C in Matp,m (K), so gilt analog C(A + B) = CA + CB. (iii) Ist A ∈ Matm,n (K) so gilt Em A = A = AEn . D.h. Em ist ein neutrales Element falls m = n. (iv) Für jedes A ∈ Matm,n (K) gilt A0n,p = 0m,p und 0p,m A = 0p,n . Beweis. Die vier Aussagen lassen sich formal mit der Definition der Matrizenaddition bzw. -multiplikation beweisen. Teil (iv) folgt, da a0 = 0a = 0 für alle a ∈ K. Wir zeigen nur die Assoziativität des Matrixprodukts sowie AEn = A aus Teil (iii). Die anderen Aussagen lassen sich ähnlich durch direktes “Ausrechnen” beweisen. Um (i) zu zeigen, schreiben wir A = (ai,j )1≤i≤m , 1≤j≤n 40 B = (bj,k )1≤j≤n 1≤k≤p und C = (ck,l )1≤k≤p . 1≤l≤q 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt Aus der Definition des MatrixproduktsPfolgt, dass der Eintrag von AB ∈ Matm,p (K) in der i-ten Zeile und k-ten Spalte gleich nj=1 ai,j bj,k ist. Entsprechend ist der Eintrag von (AB)C in der i-ten Zeile und l-ten Spalte gleich ! p p n n X X X X ai,j bj,k ck,l (2.6) ai,j bj,k ck,l = k=1 k=1 j=1 j=1 hier haben wir die Körperaxiome verwendet. Wir müssen überprüfen, dass es sich bei (2.6) auch um den Eintrag von A(BC) in der i-ten Zeilen l-ten Spalte handelt. Der Eintrag von BC in der j-ten Zeile und l-ten Pund p Spalte ist k=1 bj,k ck,l und entsprechend ist der Eintrag der i-ten Zeile und l-ten Spalte von A(BC) gleich ! p p n n X X X X ai,j bj,k ck,l = ai,j bj,k ck,l j=1 j=1 k=1 k=1 Aber diese Doppelsumme ist gleich (2.6), da die Summationsreihenfolge vertauscht werden darf. Um die zweite Identität in (iii) zu zeigen, nehmen wir wie oben an, dass A = (ai,j )1≤i≤m 1≤j≤n gilt mit ai,j ∈ K. Der Eintrag von En in der j-ten Zeile und k-ten Spalte soll mit ej,k bezeichnet werden. Es gilt 1 : falls j = k, ej,k = 0 : sonst. Wir schreiben AEn = A0 mit A0 = (ai,k )1≤i≤m . Aus der Definition erhalten wir 1≤k≤n a0i,k = n X ai,j ej,k . j=1 In dieser Summe überlebt nur der Faktor mit j = k, ansonsten ist ej,k = 0. Es gilt daher a0i,k = ai,k für alle möglichen j und k. Bemerkung 2.19. Die Assoziativität der Matrizenmultiplikation und die Eigenschaften der Einheitsmatrix lassen erhoffen, dass irgendwo eine Gruppe versteckt ist. Dies ist tatsächlich der Fall. Diese korrekt zu definieren, wird jedoch Zeit beanspruchen. Definition 2.20. Sei K ein Körper und m ∈ N. Gegeben seien quadratische Matrizen A, B ∈ Matm (K). Man sagt, dass B ein Rechtsinverses von A ist, falls AB = Em . Analog bezeichnet man B als Linksinverses von A, falls BA = Em . Schliesslich nennt man B Inverses von A, falls AB = BA = Em . Im letzten Fall sagen wir, dass A invertierbar ist. Es gibt zunächst keinen Grund anzunehmen, dass es zu einer Matrix A ein Links- oder Rechtsinverses gibt! 41 2 Matrizenkalkül Beispiel 2.21. Hier wollen wir an Beispielen erkunden, wann es ein Inverses bezüglich der Matrizenmultiplikation gibt. Wir wollen uns dabei auf quadratische Matrizen in Matn (K) beschränken, hier ist K wie immer ein Körper. (i) Natürlich gilt En En = En2 = En . Dass heisst, En ist ihr eigenes Inverses. (ii) Sei 0n die Nullmatrix. Für jede Matrix A ∈ Matn (K) gilt 0n A = A0n = 0n . Somit besitzt 0n weder ein Links- noch ein Rechtsinverses. (iii) Es gibt aber auch Matrizen ungleich der Nullmatrix, die weder ein Links- noch ein Rechtsinverses besitzt. Dies lässt sich mit der Matrix 1 1 A= ∈ Mat2 (Q) 1 1 beweisen. Nehmen wir an, dass es B ∈ Mat2 (Q) mit AB = E2 gibt. Wir definieren die Hilfsmatrix 1 −1 C= ∈ Mat2 (Q). −1 1 Dann gilt (CA)B = C(AB) = CE2 = C wegen Assoziativität, und weil E2 die Einheitsmatrix ist, siehe Lemma 2.18. Berechnen wir nun 0 0 CA = = 02 , 0 0 so erhalten wir 02 = 02 B = C. Dies ist ein Widerspruch. Also kann A kein Rechtsinverses besitzen. Unter Verwendung von CA = 02 zeigt eine ähnliche Rechnung, dass A kein Linksinverses besitzt. (iv) Die Matrix 1 1 0 1 ∈ Mat2 (Q) ist invertierbar. Ein Inverses ist durch 1 −1 ∈ Mat2 (Q), 0 1 gegeben wie man leicht nachrechnet. Lemma 2.22. Sei K ein Körper und m ∈ N. (i) Sind A, B ∈ Matm (K) beide invertierbar, so ist auch AB invertierbar. (ii) Ist A ∈ Matm (K) invertierbar, so ist auch jedes Inverse A0 von A invertierbar. (iii) Die Menge der invertierbaren Matrizen zusammen mit dem Matrizprodukt bildet eine Gruppe mit neutralem Element Em . 42 2.1 Matrizen: Summe, Skalarmultiplikation und Produkt Beweis. Seien A0 und B 0 Inverse zu A und B 0 . Das heisst, A0 A = AA0 = Em und B 0 B = BB 0 = Em . Wir behaupten, dass B 0 A0 ein Inverses zu AB ist. Dazu berechnen wir (AB)(B 0 A0 ) = A((BB 0 )A0 ) = A(Em A0 ) = AA0 = Em und (B 0 A0 )(AB) = B 0 ((A0 A)B) = B 0 (Em B) = Em , was für Teil (i) zu zeigen war. Teil (ii) folgt sofort aus der Definition des Inversen. Um Teil (iii) zu zeigen, muss man die Gruppenaxiome nachprüfen. Dass das Produkt zweier invertierbaren Matrix wieder invertierbar ist, folgt aus Teil (i). Damit ist die Teilmenge der invertierbaren Matrizen in Matn (K) abgeschlossen unter dem Matrixprodukt. Also ist die Verknüpfung wohldefiniert. Die Assoziativität dieser Verknüpfung folgt aus Lemma 2.18(i). Dass Em ein neutrales Element ist, folgt aus Lemma 2.18(iii). Das ein Inverses Elemente einer invertierbaren Matrix ebenfalls invertierbar ist, folgt aus Teil (ii) dieses Lemmas. Bemerkung 2.23. Aus dem Kapitel über Gruppentheorie, genauer aus Lemma 1.19(iii), folgt nun, dass das Inverse einer invertierbaren Matrix eindeutig bestimmt ist. Definition 2.24. Die Gruppe aus der vorherigen Definition wird mit GLn (K) bezeichnet. Sie heisst allgemeine lineare Gruppe. Die Inverse von A ∈ GLn (K) bezeichnen wir mit A−1 . Das letzte Lemma ist unbefriedigend, da es kein Rezept angibt, zu entscheiden wann eine Matrix invertierbar ist. Wir wissen also abstrakt, dass die Gruppe GLn (K) existiert. Wir können jedoch noch nicht sagen, welche Matrizen ihr angehören. Für 2 × 2 Matrizen lässt sich GL2 (K) jedoch leicht bestimmen. Später werden wir mit Hilfe der Determinante eine ähnliche Aussage für alle n erhalten. Lemma 2.25. Sei K ein Körper und a b A= ∈ Mat2 (K). c d Dann gilt A ∈ GL2 (K) ⇐⇒ ad − bc 6= 0. Beweis. Da wir die Äquivalenz zweier Aussagen beweisen wollen, müssen wir beide Implikationen “⇐=” und “=⇒” beweisen. Wir beginnen mit “⇐=”. Dazu setzen wir δ = ad − bc. Dies ist ein Element von K r {0} nach Voraussetzung. Deshalb ist δ −1 ein wohldefiniertes Element von K. Wir setzen −1 δ d −δ −1 b d −b −1 B= =δ −δ −1 c δ −1 a −c a 43 2 Matrizenkalkül und werden nun nachweisen, dass B das Inverse von A ist. Dazu rechnen wir ad − bc −ab + ba 1 0 −1 = = E2 . AB = δ cd − dc ad − bc 0 1 Also ist B zumindest ein Rechtsinverses von A. Eine ähnliche Rechnung zeigt BA = E2 und daraus folgt, dass A invertierbar ist. Nun zeigen wir die andere Implikation “=⇒”. Nach Voraussetzung gibt es ein B ∈ Mat2 (K) mit AB = E2 . Wir definieren die Hilfsmatrix d −b C= . −c a Diese erfüllt CA = ad − bc db − db −ca + ca ad − bc = δ 0 0 δ (2.7) mit δ = ad − bc. Wir möchten beweisen, dass δ 6= 0. Um dies zu tun nehmen wir das Gegenteil an, und folgern einen Widerspruch. Falls δ = 0 so gilt wegen (2.7) CA = 02 = 0. Also haben wir 0 = 0B = (CA)B = C(AB) = CE2 = C. Aus der Definition von C folgt nun A = 0. Aber die Nullmatrix kann unmöglich invertierbar sein. Dies haben wir schon weiter oben gesehen und daraus folgt der gewünschte Widerspruch. Daher ist δ 6= 0 und das Lemma ist bewiesen. 2.2 Lineare Gleichungssysteme und Zeilenstufenform Ziel dieses Abschnitts ist es, lineare Gleichungssysteme systematisch mittels Matrizen zu studieren. Definition 2.26. Sei K ein Körper und m, n ∈ N. sowie xj , bi ∈ K für 1 ≤ i ≤ m und 1 ≤ j ≤ n. Gilt a1,1 x1 + a1,2 x2 + · · · + a2,1 x1 + a2,2 x2 + · · · + .. . a x + a x + ··· + m,1 1 m,2 2 Gegeben seien Elemente ai,j ∈ K a1,n xn a2,n xn = b1 = b2 (2.8) am,n xn = bm so sagt man, dass (x1 , . . . , xn ) ∈ K n eine Lösung des inhomogenen linearen Gleichungssystems (2.8) ist. Sind b1 = b2 = · · · = bm = 0 so nennt man (x1 , . . . , xn ) ∈ K n eine Lösung des homogenen Gleichungssystems (2.8). Lineare Gleichungssysteme sind die einfachsten Gleichungen, die man nur unter Verwendendung der Körperaxiome aufschreiben kann. Lässt man höhere Potenzen xkj oder 44 2.2 Lineare Gleichungssysteme und Zeilenstufenform gar gemischte Terme xk11 · · · xknn zu, so redet man von polynomialen Gleichungen. Diese lassen sich nur mit viel grösserer Mühe behandeln; die dazugehörige Vorlesung heisst Algebraische Geometrie. Matrizen lassen sich verwenden, um das System (2.8) viel effizienter zu beschreiben. Sei dazu A ∈ Matm,n (K) die Matrix A = (ai,j )1≤i≤m und 1≤j≤n b1 .. b = . ∈ Matm,1 (K) bm ein Spaltenvektor. Sei x = (x1 , . . . , xn ) ∈ Mat1,n (K) ein Zeilenvektor. Dann gilt Ax = b ⇐⇒ (x1 , . . . , xn ) ist eine Lösung von (2.8). Der Grund für diese Äquivalenz liegt in der Beobachtung, dass das Produkt der zwei Matrizen A und x genau durch die linke Seite von (2.8) gegeben ist. Natürlich ist die Notation Ax = b viel kompakter wie (2.8). Matrizen dienen jedoch nicht nur der Kosmetik. Sie werden uns später helfen, lineare Gleichungssysteme zu lösen. Definition 2.27. In Zukunft werden wir das inhomogene System (2.8) durch [A|b] abkürzen. Das homogene System (b = 0) lässt sich durch A alleine ausdrücken. Bevor wir zur allgemeinen Theorie kommen, werden wir ein relativ einfaches Gleichungssytem von Hand lösen. Die Schritte, die wir dabei durchlaufen, werden wir später verallgemeinern. Beispiel 2.28. Wir betrachten das homogene Gleichungssystem, welches durch die Matrix 0 2 −2 A= ∈ Mat2,3 (Q) 2 4 6 gegeben ist. Wir wollen alle Lösungen des homogenen Systems 2x2 − 2x3 = 0 2x1 + 4x2 + 6x3 = 0 bestimmen. Zuerst nehmen wir an, dass der Spaltenvektor x1 x = x2 x3 eine Lösung mit rationalen Koeffizienten ist. D.h. Ax = 0. 45 2 Matrizenkalkül Natürlich ist x auch eine Lösung des homogenen Gleichungssystems, welches wir durch das Vertauschen der zwei Zeilen von A erhalten: 2 4 6 0 A = 0 2 −2 Es gilt 2x1 + 4x2 + 6x3 = 0 und somit auch x1 + 2x2 + 3x3 = 0 nach Division durch 2. Dies entspricht Multiplikation der ersten Zeile von A0 mit 1/2. Also gilt A00 x = 0 mit 1 2 3 00 A = 0 2 −2 Es gilt x1 + 2x2 + 3x3 = 0 und 2x2 − 2x3 = 0. Falls wir die zweite Gleichung von der ersten subtrahieren, so erhalten wir x1 + 5x3 = 0. Wir haben A000 x = 0 mit 000 A = 1 0 5 0 2 −2 Als letztes multiplizieren wir, ähnlich wie vorhin, die zweite Zeile von A000 mit 1/2 und erhalten 1 0 5 0000 A = 0 1 −1 wobei immer noch A0000 x = 0 gelten muss. Setzen wir x hier ein, so ergibt sich x1 = −5x3 und x2 = x3 . Wir haben bewiesen, dass jede Lösung x ∈ Q3 von Ax = 0 von der Form −5 x = 1 t ist für ein t ∈ Q. 1 (2.9) Hier haben wir x3 durch t ersetzt. Umgekehrt sieht man sofort, dass jeder Spaltenvektor der Form (2.9) eine Lösung von Ax = 0 ist. Wir sagen, dass A0000 in Zeilenstufenform ist. Diesen Begriff werden wir später für allgemeine Matrizen definieren. Somit ist die Lösungsmenge bestimmt. Insgesamt mussten wir drei verschiedene Zeilenumformungen durchführen, bis unsere Matrix A in Zeilenstufenform war. Wir fassen diese zusammen. A 46 Z1 und Z2 vertauschen A0 Z1 mal 1/2 A00 Z1 durch Z1-Z2 ersetzen A000 Z2 mal 1/2 A0000 . 2.2 Lineare Gleichungssysteme und Zeilenstufenform Wie schon angedeutet, kann man diese drei Zeilenumformungen in einem allgemeineren Kontext durchführen. Definition 2.29. Sei K ein Körper und m, n ∈ N. Sei A ∈ Matm,n (K) eine Matrix mit Zeilen a1 , . . . , am (wir betrachten die ai als Zeilenvektoren). Wir sagen, dass eine Matrix A0 ∈ Matm,n (K) durch Zeilenumformungen aus A entstehe, falls: (I) die i-te Zeile ai von A durch ai +λaj ersetzt wurde, wobei λ ∈ K und 1 ≤ i 6= j ≤ n, oder (II) die i-te und j-te Zeilen von A vertauscht wurden wobei 1 ≤ i 6= j ≤ n, oder (III) die i-te Zeile ai durch λai ersetzt wurde, wobei λ ∈ K r {0} und 1 ≤ i ≤ n. Diese Umformungen werden wir als Zeilenumformung vom Typ I, II oder III bezeichnen. Ein wichtiger Fakt im Zusammenhang mit Zeilenumformungen ist, dass sie durch Matrizenmultiplikation der sogenannten Elementarmatrizen entstehen. Definition 2.30. Sei K ein Körper, m ∈ N 0 .. ei,j = . 0 und 1 ≤ i, j ≤ m. Wir definieren ··· 0 . 1 .. ··· 0 wobei sich die 1 in der i-ten Zeile und j-ten Spalte befindet, alle weiteren Einträge sind 0. Wir definieren drei Typen von Elementarmatrizen der Grösse m. (I) Für 1 ≤ i 6= j ≤ m und λ ∈ K definieren wir 1 ... 1 λ E I (i, j, λ) = .. . = Em + λei,j . 1 In Worten: die Diagonaleinträge von E(i, j, λ) sind 1, ausserhalb der Diagonale sind die Einträge 0, ausser in der i-ten Zeile und j-ten Spalte wo λ steht. (II) Für 1 ≤ i 6= j ≤ m definieren wir 1 .. . 0 1 II . .. E (i, j) = 1 0 ... = Em − ei,i − ej,j + ei,j + ej,i . 1 47 2 Matrizenkalkül (iii) Für 1 ≤ i ≤ m und λ ∈ K r {0} definieren 1 .. . III λ E (i, λ) = .. . = Em − ei,i + λei,i . 1 Nun werden wir beweisen, dass die drei Zeilenumformungen durch Linksmultiplikation der Elementarmatrizen induziert werden. Lemma 2.31. Sei K ein Körper, m, n ∈ N und A ∈ Matm,n (K). (i) Seien 1 ≤ i 6= j ≤ n und λ ∈ K. Dann entsteht E I (i, j, λ)A durch A mittels einer Zeilenumformung des Types I. (ii) Seien 1 ≤ i 6= j ≤ n. Dann entsteht E II (i, j)A durch A mittels einer Zeilenumformung des Typs II. (iii) Seien 1 ≤ i ≤ n und λ ∈ K r {0}. Dann entsteht E III (i, λ)A durch A mittels einer Zeilenumformung des Typs III. Beweis. Wir schreiben a1,1 · · · .. A= . am,1 · · · Seien 1 ≤ i 6= j ≤ n dass i < j. Es gilt 1 .. . 1 λ .. . 1 und λ ∈ K. Wir nehmen ohne Beschränkung der Allgemeinheit an, a1,1 .. . ai,1 . .. ··· am,1 ··· hieraus folgt (i). Wir berechnen 1 .. . 0 1 ... 1 0 .. . 48 a1,n .. ∈ Mat (K). m,n . am,n ··· a1,1 a1,n .. .. . . ai,n = ai,1 + λaj,1 .. .. . . am,n am,1 a1,1 .. . ai,1 · · · . .. a j,1 · · · . .. 1 am,1 ··· ··· ai,n + λaj,n .. . ··· am,n ··· ai,i · · · ai,j · · · aj,i · · · aj,j · · · ··· a1,n .. . a1,n .. . ai,n .. . = aj,n .. . am,n . 2.2 Lineare Gleichungssysteme und Zeilenstufenform a1,n .. . aj,n .. . . ai,n .. . am,n ··· a1,1 .. . aj,1 · · · . .. a i,1 · · · . .. am,1 aj,i · · · aj,j · · · ai,i · · · ai,j · · · ··· Somit ist (ii) bewiesen. Schlussendlich, sei λ ∈ K r {0}. Dann gilt a1,1 .. . ai,1 . .. ··· am,1 ··· 1 ... λ .. . 1 ··· a1,n a1,1 .. .. . . ai,n = λai,1 . .. . .. am,n am,1 ··· ··· ··· a1,n .. . λai,n . .. . am,n Also ist (iii) wahr. Beispiel 2.32. Sei A= 3 7 −1 2 ∈ Mat2 (Q). Für λ ∈ Q gilt I E (2, 1, λ)A = 1 0 λ 1 0 1 1 0 1 0 0 λ und II E (2, 1)A = und E III (2, λ)A = 3 7 −1 2 = 3 7 −1 2 3 7 −1 2 3 7 −1 + 3λ 2 + 7λ −1 2 3 7 3 7 −λ 2λ = = falls λ 6= 0. Was passiert, wenn man hintereinander zweimal die Zeilen i und j vertauscht? Man erhält natürlich die ursprüngliche Matrix. Im nächsten Lemma verallgemeinern wir diese Beobachtung. Lemma 2.33. Sei K ein Körper, wir betrachten Elementarmatrizen der Grösse m ∈ N. (i) Für 1 ≤ i 6= j ≤ m und λ ∈ K gilt E I (i, j, −λ)E I (i, j, λ) = Em . 49 2 Matrizenkalkül (ii) Für 1 ≤ i 6= j ≤ m gilt E II (i, j)E II (i, j) = Em . (iii) Für 1 ≤ i ≤ m und λ ∈ K r {0} gilt E III (i, λ−1 )E III (i, λ) = Em . Weiterhin sind alle Elementarmatrizen invertierbar, d.h. sie liegen in GLm (K). Beweis. Addiert man −λ mal die j-te Zeile zur i-ten Zeile von E I (i, j, λ) so erhält man Em . Also folgt (i) Vertauscht man zweimal hintereinander die selben zwei Zeilen so erhält man die ursprüngliche Matrix. Hieraus folgert man (ii) Multipliziert man die i-te Zeile einer Matrix zuerst mit λ und anschliessend mit λ−1 , so erhält man wiederum die ursprüngliche Matrix. Daraus folgt (iii) Die Invertierbarkeit der Elementarmatrizen folgt schnell aus (i), (ii) und (iii). Wenden wir bspw. (i) auf λ und −λ an, so folgt E I (i, j, −λ)E I (i, j, λ) = Em = E I (i, j, λ)E I (i, j, −λ), also ist E I (i, j, λ) invertierbar. Da E II (i, j) sein eigenes Rechts- und Linksinverses ist, folgt, dass E II (i, j) invertierbar ist. Schliesslich folgt E III (i, λ−1 )E III (i, λ) = Em = E III (i, λ)E III (i, λ−1 ). aus (iii) angewendet auf λ und λ−1 . Nun folgt leicht, dass Zeilenumformungen die Lösungsmenge eines linearen Gleichungssystems nicht verändern. Lemma 2.34. Sei K ein Körper, m, n ∈ N, A ∈ Matm,n (K) und b ∈ Matm,1 (K) = K m ein Spaltenvektor. Entsteht die ergänzte Matrix (A0 , b0 ) ∈ Matm,n+1 (K) durch endlich viele Zeilenumformungen aus der ergänzten Matrix (A, b) so gilt Ax = b ⇐⇒ A0 x = b0 für alle x ∈ Matn,1 (K). Beweis. Nach Voraussetzung und Lemma 2.31 gilt A0 = LA und b0 = Lb wobei L ein endliches Produkt aus Elementarmatrizen E I (· · · ), E II (· · · ) und E III (· · · ) ist. Wir wissen aus Lemma 2.33, dass Elementarmatrizen invertierbar sind. D.h. die Menge aller invertierbarer Matrizen liegt in der Gruppe GLm (K). Also liegt auch L in GLm (K). Insbesondere ist L invertierbar, d.h. L−1 existiert. Wir erhalten Ax = b =⇒ LAx = Lb =⇒ A0 x = b0 und andererseits −1 0 −1 0 A0 x = b0 =⇒ L | {zA} x = L b =⇒ Ax = b. =L−1 (LA) 50 2.2 Lineare Gleichungssysteme und Zeilenstufenform Wir haben weiter oben in einem Beispiel die Matrix 0 2 −2 2 4 6 durch geeignete Zeilenumformungen in besonders einfache Form gebracht. Wir wollen dies nun für alle Matrizen machen. Definition 2.35. Gestalt 0 ··· 0 1 0 ··· 0 0 0 ··· 0 0 0 ··· 0 0 .. .. .. . . . Sei K ein Körper und m, n ∈ N. Wir sagen, dass eine Matrix der ? 0 0 0 .. . ··· ··· ··· ··· ? 0 0 0 .. . 0 1 0 0 .. . ? ? 0 0 .. . ··· ··· ··· ··· ? ? 0 0 .. . 0 0 1 0 .. . ? ? ? 0 .. . ··· ··· ··· ··· ? ? ? 0 0 0 0 1 ··· ··· ··· ··· .. . ∈ Matm,n (K) in Zeilenstufenform ist. In Worten: Eine Matrix A ∈ Matm,n (K) ist in Zeilenstufenform genau dann, wenn folgende drei Bedingungen erfüllt sind. (i) Der erste Eintrag ungleich Null jeder Zeile von A ist 1. Diesen Eintrag nennt man Pivoteintrag. (N.B.: nicht jede Zeile muss ein Pivoteintrag besitzen, d.h. es darf Nullzeilen geben. Aber es gibt stets höchstens ein Pivoteintrag. In der Matrix oben sind die Pivoteinträge in einem Quadrat hevorgehoben.) (ii) Ist die i-te Zeile ungleich Null und i ≥ 2, so ist auch die (i − 1)-te Zeile ungleich Null. Weiterhin steht der Pivoteintrag der i-ten Zeile rechts des Pivoteintrags der (i − 1)-ten Zeile. (iii) Die Einträge oberhalb eines Pivoteintrags sind 0. Beispiel 2.36. (i) Die Matrizen 1 0 0 0 0 0 1 0 5 1 1 0 , 0 1 0 , 0 0 0 , 0 1 −1 0 0 1 0 0 1 0 0 0 sind in Zeilenstufenform. Die Matrix 0 0 0 0 1 0 0 0 0 ist nicht in Zeilenstufenform. Vertauscht erhält man 0 1 0 0 0 0 man jedoch die ersten zwei Zeilen so 0 0 0 und diese Matrix ist in Zeilenstufenform. 51 2 Matrizenkalkül (ii) Wir werden das inhomogene lineare Gleichungssystem x 1 2 −2 3 1 y 5 7 −3 1 1 z =b= 2 6 −8 0 1 | {z } w =A lösen. 1 2 −2 3 1 (A|b) = 5 7 −3 1 1 . 2 6 −8 0 1 Oben links in A steht bereits eine Eins. Schritt 1: Wir führen zweimal eine Typ I Zeilenumformung auf (A|b) an. Wir addieren −5 mal Zeile 1 zu 2 und −2 mal Zeile 1 zu Zeile 3. und Also 1 1 2 −2 3 (A0 |b0 ) = 0 −3 7 −14 −4 . 0 2 −4 −6 −1 Schritt 2: Nun führen wir eine Typ II Zeilenumformung auf (A0 |b0 ) aus. Genauer, wir vertauschen die Zeilen 2 und 3 und erhalten 1 1 2 −2 3 (A00 |b00 ) = 0 2 −4 −6 −1 . 0 −3 7 −14 −4 Schritt 3: Wir führen eine Zeilenumformung vom Typ III an und multiplizieren Zeile 2 mit 1/2 und erhalten 1 1 2 −2 3 (A000 |b000 ) = 0 1 −2 −3 −1/2 . 0 −3 7 −14 −4 Schritt 4: Jetzt möchten wir in der zweiten Spalte oben und unten eine Null erzwingen. Hierfür sind zwei Typ I Zeilenumformungen nötig. Wie addieren −2 mal Zeile 2 zu Zeile 1 und 3 mal Zeile 2 zu Zeile 3. Das Ergebnis ist 2 1 0 2 9 (A0000 |b0000 ) = 0 1 −2 −3 −1/2 . 0 0 1 −23 −11/2 Schritt 5: Schliesslich addieren wir −2 zu Zeile 2. Wir erhalten 1 0 (A00000 |b00000 ) = 0 1 0 0 52 mal Zeile 3 zu Zeile 1 und 2 mal Zeile 3 13 0 55 0 −49 −23/2 . 1 −23 −11/2 2.2 Lineare Gleichungssysteme und Zeilenstufenform Diese Matrix ist nun in Zeilenstufenform. hat die Form x +55w y −49w z −23w Das entsprechende Gleichungssystem = 13 = −23/2 = −11/2. Die Lösungsmenge des ursprünglichen (wie auch des neuen) Gleichungssystems ist −55w + 13 49w − 23/2 : t ∈ Q ⊆ Q4 . 23w − 11/2 w Wir zeigen jetzt, dass sich jede Matrix durch Zeilenumformungen in Zeilenstufenform bringen lässt. Später werden wir sehen, wie man durch hinstarren lineare Gleichungssyteme lösen kann, wenn die dazugehörige Matrix in Zeilenstufenform ist. Lemma 2.37. Sei K ein Körper, m, n ∈ N und A ∈ Matm,n (K). Dann lässt sich jede Matrix in Matm,n (K) nach endlich vielen Zeilenumformungen in Zeilenstufenform bringen. Beweis. Der Beweis ist per Induktion auf m + n. Im Fall A = 0 gibt es nichts zu zeigen. Also nehmen wir A 6= 0 an. Die erste Spalte von A könnte Null sein. Aber nachdem wir, falls nötig, eine Zeilenvertauschung (Typ II) gemacht haben, enthält die erste Spalte die ungleich Null ist ein Element ungleich Null in der ersten Zeile. Das heisst, wir erhalten A Typ II (falls nötig) A0 = 0 ··· 0 ··· .. . 0 ··· a ··· ? ··· .. . 0 ? ··· 0 0 .. . mit a 6= 0. Da a 6= 0 erlauben wir uns eine Zeilenumformung des Typs III und multiplizieren die erste Zeile mit a−1 . Wir erhalten A0 Typ III A00 = 0 ··· 0 ··· .. . 0 ··· 0 1 ··· 0 a2 · · · .. .. . . 0 am · · · mit a2 , . . . , am ∈ K. Nun wenden wir Zeilenumformungen des Typs I an und subtrahieren a2 mal Zeile eins von Zeile zwei. Dann subtrahieren wir a3 mal Zeile eins von Zeile drei, usw. usw. Dies hat zur Folge, dass unter der führenden 1 der erste Zeile nur die 0 steht. Also 53 2 Matrizenkalkül 00 Typ I A | ·{z ·· }A = Typ I m−1 mal 000 1 ··· 0 ··· 0 1 b = .. 0 0 C . 0 0 ··· 0 ··· 0 ··· .. . 0 0 .. . 0 ··· wobei b ein Zeilenvektor und C eine Matrix mit m − 1 Zeilen ist. Nun wenden wir das oben angegebene Vorgehen induktiv auf C an. Die dabei auftretenden Zeilenumformungen beeinflussen die erste Zeile von A000 nicht. Nach einer Induktion auf m erhalten wir 0 ··· 0 1 ? ··· ? ? ? ··· ? ? ? ··· ? ? ··· 0 ··· 0 0 0 ··· 0 1 ? ··· ? 0 ? ··· ? 0 ··· induktiv A000 A0000 = 0 · · · 0 0 0 · · · 0 0 0 · · · 0 1 ? · · · ? 0 · · · . 0 ··· 0 0 0 ··· 0 0 0 ··· 0 0 0 ··· 0 1 ··· .. .. .. .. .. .. .. .. .. .. .. . . . . . . . . . . . Die Matrix A0000 ist noch nicht ganz in Zeilenstufenform: die markierten Einträge oberhalb der Pivoteinträge von C sind vielleicht noch nicht 0. Dieses Problem lässt sich jedoch leicht lösen. Mit Hilfe von Zeilenumformungen des Typs I lassen sich auch auf diese Werte eliminieren: A0000 Typ I ··· Typ I A00000 ist in Zeilenstufenform. Proposition 2.38. Sei K ein Körper, m, n ∈ N und A ∈ Matm,n (K) eine Matrix in Zeilenstufenform. Sei r die grösste ganze Zahl in {1, . . . , m} mit der Eigenschaft, dass die r-te Zeile von A keine Nullzeile ist. Sei b1 b = ... bm ein Spaltenvektor. Das lineare Gleichungssystem Ax = b mit x1 x = ... ∈ Matm,1 (K) xn (2.10) hat genau dann eine Lösung x, wenn br+1 = br+2 = · · · = bm = 0. Nehmen wir an, dass eine Lösung existiert und seien j1 < j2 < · · · < jk die Spalten von A, welche keinen Pivoteintrag enthalten. Dann gibt es zu jeder Wahl von xj1 , . . . , xjk ∈ K genau eine Lösung x wie in (2.10). 54 2.2 Lineare Gleichungssysteme und Zeilenstufenform Beweis. Eine Lösung des Gleichungssystem erfüllt xt1 + a1,t1 +1 xt1 +1 · · · = b1 , = b2 , xt2 + a2,t2 +1 xt2 +1 + · · · ... xtr + ar,tr +1 xtr +1 · · · = br , 0 = br+1 , .. . 0 = bm wobei t1 , t2 , . . . die Spalten von A bezeichnen, die ein Pivoteintrag enthalten. Somit ist br+1 = · · · = bm = 0 ein notwendiges Kriterium für die Existenz einer Lösung. Umkehrt ist dies auch ein hinreichendes Kriterium. Nehmen wir also br+1 = · · · = bm = 0 an. Sind xtr +1 , . . . , xm ∈ K beliebig, so lässt sich ein eindeutiges xtr ∈ K finden, so dass die letzte nichttriviale Gleichung oben erfüllt ist. Man findet also ein xtr−1 ∈ K welches die zweitletzte nichttriviale Gleichung löst, dabei kann man xtr−1 +1 , . . . , xtr −1 frei wählen. Dieses “rückwärts-aufwärts” Lösen setzt man fort, bis man ganz oben links angelangt ist. Beispiel 2.39. Die Matrix A= 1 0 2 0 0 1 5 −2 ∈ Mat2,4 (Q) ist in Zeilenstufenform; die Pivoteinträge sind umrandet. Wir wollen das inhomogene System x1 x2 7 Ax = in x = x3 −3 x4 lösen. Gemäss Proposition 2.38 existiert eine Lösung und wir können x2 und x4 frei wählen. Die Lösungsmenge ist also −2x − 5x + 7 2 4 x 2 ; x2 , x4 ∈ Q . 2x4 − 3 x4 Zur Erinnerung, gegeben eine Matrix A ∈ Matm,n (K) mit K ein Körper, so definiert Ax = 0 mit x ∈ Matn,1 (K) ein lineares Gleichungsssytem bestehend aus m homogenen linearen Gleichungen in n Unbekannten. Der Nullvektor x ist natürlich immer eine Lösung. Diese Lösung nennt man die triviale Lösung. Folgendes Korollar impliziert, dass ein überbestimmtes homogenes lineares Gleichungssystem (diejenige mit n > m) eine nicht triviale Lösung besitzt. 55 2 Matrizenkalkül Korollar 2.40. Sei K ein Körper m, n ∈ N mit n > m und A ∈ Matm,n (K). Dann existiert ein Spaltenvektor x ∈ K n r {0} mit Ax = 0. Beweis. Wegen Lemmata 2.34 und 2.37 dürfen wir annehmen, dass A in Zeilenstufenform ist. Jetzt werden wir Proposition 2.38 anwenden. Sei k die Anzahl Spalten von A welche keinen Pivoteintrag enthalten. Wäre nun k = 0, so enthielte jede Spalte von A einen Pivoteintrag und es gäbe deren insgesamt mindestens n Stück. Da es mindestens soviele Zeilen wie Pivoteinträge geben muss, folgt m ≥ n. Dies ist ein Widerspruch. Es muss also k ≥ 1 gelten. Nun sind k Einträge von x wie in Proposition 2.38 frei wählbar. Inbesondere gibt es eine Lösung von Ax = 0 mit x 6= 0. Nun können wir eine für die Theorie wichtige Aussage beweisen. Eine quadratische Matrix besitzt ein Rechtsinverses genau dann, wenn sie ein Linksinverses besitzt. Proposition 2.41. Sei K ein Körper und m ∈ N. Seien A, B ∈ Matm (K) quadratische Matrizen mit AB = Em . Dann gilt BA = Em . Insbesondere sind A und B invertierbar. Beweis. Wegen Lemmata 2.31 und 2.37 gibt es ein Produkt L ∈ Matm (K) aus endlich vielen Elementarmatrizen mit LA in Zeilenstufenform. Die Matrix L ist invertierbar, weil sie ein endliches Produkt aus Elementarmatrizen ist, siehe Lemma 2.33. Der Pivoteintrag eine Zeile ungleich Null von LA steht rechts des Pivoteintrags der vorhergehenden Zeile von LA. Weil LA quadratisch ist, muss eine der zwei folgenden Aussagen wahr sein. (i) Das Produkt LA ist die Einheitsmatrix Em . (ii) Die letzte Zeile von LA ist 0. Wir wollen den zweiten Fall ausschliessen. Trifft er doch zu, so ist auch die letzte Zeile von (LA)B = L(AB) = L (2.11) Null. Also müsste auch die letzte Zeile von LL−1 = Em gleich 0 sein. Dies ist ein Widerspruch. Folglich sind wir im Fall (i) und es gilt LA = Em . Wir multiplizieren von links mit L−1 und erhalten L−1 = L−1 (LA) = (L−1 L)A = A. Also ist zumindest A invertierbar, da L und L−1 invertierbar sind. Aus AB = Em folgt nun L = L(AB) = (LA)B = B und somit ist auch B invertierbar. Also liegen A und B in der Gruppe GLm (K). Lemma 1.19(i) impliziert BA = Em . Die eben bewiesene Proposition und deren Beweis impliziert folgende Aussage. Lemma 2.42. Sei A ∈ Matm (K) eine Matrix und L ein endliches Produkt aus Elementarmatrizen mit der Eigenschaft, dass LA in Zeilenstufenform ist. Dann ist genau dann A invertierbar, wenn LA die Einheitsmatrix ist. In diesem Fall gilt L = A−1 . Is A nicht invertierbar, so ist die letzte Zeile von LA eine Nullzeile. 56 2.2 Lineare Gleichungssysteme und Zeilenstufenform Beweis. Ist A invertierbar, so folgt die Aussage wie im Beweis der Proposition. Ist LA die Einheitsmatrix, so L = A−1 wegen der Aussage besagter Proposition. Falls A nicht invertierbar ist, so folgt die letzte Aussage wie im Beweis der Proposition. Wir halten zwei nützliche Konsequenzen fest. (i) Bringen wir eine quadratische Matrix in Zeilenstufenform, so können wir entscheiden, ob die ursprüngliche Matrix invertierbar ist oder nicht. (ii) Ist eine quadratische Matrix A invertierbar, und ist L ein Produkt aus Elementarmatrizen mit der Eigenschaft, dass LA Zeilenstufenform hat, so ist die Matrix L die Inverse von A. Diese Bemerkung erläutern wir an einem Beispiel. Beispiel 2.43. Sei 1 1 1 A = 2 3 4 ∈ Mat3 (Q). 4 9 16 Wir wollen die Erkenntnis aus der letzten Bemerkung benutzen, um zu entscheiden ob A invertierbar ist. Also bringen wir A durch Zeilenumformungen in Zeilenstufenform. Wir werden jede Zeilenumformung parallel an der Einheitsmatrix E3 durchführen. Dies wird schlussendlich die Matrix L aus der Bemerkung liefern. Schritt 1. Wir subtrahieren 2 mal Zeile 1 von Zeile 2 und 4 mal Zeile 1 von Zeile 3. Wir erhalten 1 1 1 Typ I Typ I A A0 = E I (3, 1, −4)E I (2, 1, −2)A = 0 1 2 0 5 12 und parallel E3 Typ I 1 0 0 Typ I E 0 = E I (3, 1, −4)E I (2, 1, −2)E3 = −2 1 0 . −4 0 1 Schritt 2. Der Eintrag in Zeile 2, Spalte 2 von A0 ist schon 1. Somit bleiben uns Zeilenumformungen des Typs II und III erspart. Wir subtrahieren Zeile 2 von Zeile 1 und dann 5 mal Zeile 2 von Zeile 3. Dies ergibt 1 0 −1 Typ I Typ I A0 A00 = E I (3, 2, −5)E I (1, 2, −1)A0 = 0 1 2 . 0 0 2 Wir führen wieder die selben Umformungen parallel an E 0 aus und erhalten 3 −1 0 Typ I Typ I E0 E 00 = E I (3, 2, −5)E I (1, 2, −1)E 0 = −2 1 0 . 6 −5 1 57 2 Matrizenkalkül Schritt 3. Der Eintrag in Zeile 3 und Spalte 3 von A00 Zeile 3 mit 1/2 in A00 und E 00 und erhalten dabei 1 00 Typ III 000 III 00 0 A A = E (3, 1/2)A = 0 und ist 2. Wir multiplizieren also 0 −1 1 2 0 1 3 −1 0 Typ III 1 0 . E 000 = E III (3, 1/2)E 00 = −2 E 00 3 −5/2 1/2 Schritt 4. Die Matrix A000 ist fast in Zeilenstufenform. Wir müssen noch 2 mal eine Zeilenumformung des Types I durchführen. Explizit müssen wir Zeile 3 zu Zeile 1 addieren und dann 2 mal Zeile 3 von Zeile 2 subtrahieren. Also 1 0 0 Typ ITyp I A000 A0000 = E I (2, 3, −2)E I (1, 3, 1)A000 = 0 1 0 0 0 1 und schon ist A0000 in Zeilenstufenform. Folglich ist A invertierbar. Dieselbe Umformungen führen wir an E 000 aus und kriegen 6 −7/2 1/2 Typ ITyp I 6 −1 . E 000 E 0000 = E I (2, 3, −2)E I (1, 3, 1)E 000 = −8 3 −5/2 1/2 Weshalb haben wir die Einheitsmatrix mittransformiert? Wenn man den ganzen Prozess betrachtet so haben wir E3 = A0000 = E I (2, 3, −2) · · · E I (2, 1, −2) A {z } | L die gleichen Umformungen haben wir an E3 unternommen, also E 0000 = E I (2, 3, −2) · · · E I (2, 1, −2)E3 . Somit ist E 0000 = L die Inverse von A. Eine kurze Kontrollrechnung zeigt auch 6 −7/2 1/2 1 1 1 1 0 0 −8 6 −1 2 3 4 = 0 1 0 . 3 −5/2 1/2 4 9 16 0 0 1 Lemma 2.44. Sei K ein Körper, m ∈ N und A ∈ Matm (K). Die folgenden Aussagen sind äquivalent. (i) Die Matrix A ist invertierbar. 58 2.3 Eine Anwendung: PageRank (ii) Das homogene Gleichungssystem Ax = 0 hat nur die Lösung x = 0 ∈ K m . Beweis. Wir zeigen zuerst die einfachere Richtung “(i)⇒(ii)”. Sei also x ∈ K m eine Lösung Ax = 0. Wir multiplizieren diese Gleichung von links mit A−1 und erhalten A−1 Ax = A−1 0 = 0. Es folgt x = 0. Nun zu “(ii)⇒(i)”. Wegen Lemmata 2.31 und 2.37 gibt es ein endliches Produkt L ∈ Matm (K) aus Elementarmatrizen mit LA in Zeilenstufenform. Es gibt nichts zu zeigen, falls A invertierbar ist. Nehmen wir also die Negation aus, daraus wird ein Widerspruch folgen. Aus Lemma 2.42 folgt, dass unsere neue Matrix die Gestalt 0 A LA = 0 hat, wobei A0 ∈ Matm−1,m (K). Wegen Korollar 2.40 gibt es ein x ∈ K m r {0} mit A0 x = 0. Die letzte Zeile von LA bereitet keine Probleme: es gilt auch LAx = 0. Nun ist L invertierbar, somit haben wir 0 = L−1 LAx = Ax. Dies ist ein Widerspruch zu Teil (ii). 2.3 Eine Anwendung: PageRank Eine Suchanfrage bei Google kann mehrere millionen Suchtreffen liefern. Erfahrungsgemäss sind die Suchergebnisse meistens so sortiert, dass die relevanten Resultate weiter vorne auftauchen. Wie bewertet Google die Seiten nach ihrer Relevanz? Der Algorithmus, den Google einsetzt heisst PageRank und ist eine prominente Anwendung der linearen Algebra. Wir werden in diesem Abschnitt eine vereinfachte Version des PageRank Algorithmus vorstellen. Das Ziel dieses Algorithmus ist es, jeder Webseite einen “Bekanntheitsgrad” zuzordnen. Die Menge aller Webseiten wird mit {1, 2, . . . , M } bezeichnet. Jeder Webseite i ∈ {1, 2, . . . , M } wird eine reelle Zahl xi mit 0 ≤ xi ≤ 1 zugeordnet, dies ist der Bekanntheitsgrad von i. Je höher der Bekanntheitsgrad, desto weiter oben im Suchergebnis wird die Webseite auftauchen, falls sie dem Suchkriterion entspricht. D.h. die Resultate werden in absteigender Reihenholge ihrer Bekanntheit dargestellt. Die Berechnung des Bekanntheitsgrad basiert auf dem folgenden Modell. Bekanntlich sind Webseiten untereinander verlinkt. Webseite auf die besonders häufig verwiesen werden, sollen als wichtiger gewichtet werden. Eine Webseite i ∈ {1, 2, . . . , M } verlinkt dabei auf Ni ≥ 0 verschiedene Webseiten. Die xi erfüllen die folgenden zwei Regeln. (i) Eine Webseite j verteilt an alle Webseiten auf die j verlinkt seinen Bekanntheitsgrad mit Gewicht 1/Nj . Hat eine Webseite j keine Verweise nach aussen (also Nj = 0), so verteilt diese Seite seinen Bekanntheitsgrad gleichmässig, also mit Gewicht 1/(M − 1), auf alle anderen Seiten. Der Sachverhalt drückt sich in folgender 59 2 Matrizenkalkül Gleichung aus xi = M X j=1,j6=i j verlinkt auf i M X xj xj + Nj j=1,j6=i M − 1 für alle i ∈ {1, . . . , M }. (2.12) Nj =0 (ii) Der gesamte Bekanntheitsgrad im Internet ist auf 1 normiert. Dies drückt sich durch x1 + x2 + · · · + xM = 1 (2.13) aus. Die Gleichungen (2.12) und (2.13) bilden ein inhomogenes lineares Gleichungssystem. Ingesamt gibt es M + 1 Gleichungen und M Unbekannte.1 An dieser Stelle begnügen wir uns damit, ein Beispiel mit M = 5 Webseiten durchzurechnen. Schwarze Pfeile repräsentieren Verweise. 4. www.mathoverflow.net 1. www.unibas.ch 5. www.google.com 3. www.arxiv.org 2. www.wikipedia.org Wir stellen das zum Beispiel zugehörige inhomogene Gleichungssystem auf. Dazu halten wir zuerst N1 = 2, 1 N2 = 3, N3 = 0, N4 = 1, N5 = 4 Man kann ganz allgemein beweisen, dass diese System eine eindeutige Lösung besitzt. Wir werden dieses Problem in einem späteren Kapitel aufgreifen. 60 2.3 Eine Anwendung: PageRank fest −x1 + x32 + x43 x1 − x2 + x43 2 x1 + x32 − x3 + x4 2 x3 − x4 4 x3 x2 + 3 4 x1 + x2 + x3 + x 4 + x45 + x45 + x45 + x45 − x5 + x5 = 0, = 0, = 0, = 0, = 0, = 1. Die (eindeutige) Lösung ist 4 3 34 5 16 (x1 , x2 , x3 , x4 , x5 ) = , , , , = (0.19 . . . , 0.21 . . . , 0.32 . . . , 0.11 . . . , 0.15 . . .) 21 14 105 42 105 Die Reihenfolge ist also 1. www.arxiv.org 2. www.wikipedia.org 3. www.unibas.ch 4. www.google.com 5. www.mathoverflow.net 61 3 Die Determinante einer Matrix Sei K ein Körper. Eine 1 × 1 Matrix (a) besteht aus nur einem Eintrag a ∈ K. Diese Matrix ist genau dann invertierbar, wenn a 6= 0. Für eine 2 × 2 Matrix a b A= ∈ Mat2 (K) c d ist die Situation schon etwas komplizierter, wie wir in Lemma 2.25 gesehen haben. In der Tat ist A invertierbar, genau dann wenn ad − bc 6= 0. (3.1) Wir können für eine beliebige m × m Matrix A ∈ Matm (K) entscheiden, ob sie invertierbar ist oder nicht, in dem wir sie in Zeilenstufenform bringen. Das ist aber nicht in jeder Situation praktikabel. In diesem Kapitel werden wir jeder quadratischen Matrix A ein Element aus K zuordnen, welches genau dann ungleich 0 ist, wenn A invertierbar ist. Dieses Element heisst Determinante von A. Wir definieren zuerst ad hoc die Determinante einer 1 × 1 und einer 2 × 2 Matrizen: det(a) = a. und det a b c d = ad − bc. Im Laufe des Kapitels werden wir die Determinante auf quadratische Matrizen beliebiger Grösse verallgemeinern. Diese Definition stimmt mit den zwei ad hoc Definitionen oben überein. Eine zentrale Eigenschaft der Determinanten von 2×2 Matrizen ist die Multiplikativität. Lemma 3.1. Sei K ein Körper und A, B ∈ Mat2 (K). Es gilt det(AB) = det(A) det(B). Beweis. Übungsaufgabe auf Serie 7. Auch diese Eigenschaft verallgemeinert sich auf quadratische Matrizen beliebiger Grösse. 63 3 Die Determinante einer Matrix 3.1 Permutationen Es gibt mehrere (äquivalente) Definitionen für die Determinante einer m×m Matrix. Wir werden die Determinante über die sogenannte Leibnizformel einführen. Ein alternativer Zugang ist über die Laplaceentwicklung. Wir werden im Laufe des Kapitels beweisen, dass beide Definitionen den gleichen Wert liefern. Um die Determinante mittels der Leibnizformel einzuführen, brauchen wir den Begriff der Permutation und der symmetrischen Gruppe. Wir haben im Kapitel über Gruppentheorie die symmetrische Gruppe auf einer beliebigen Menge kennengelernt, cf. Beispiel 1.17(iii). Im Zusammenhang mit der Determinante reicht es aus, die symmetrische Gruppe auf endlichen Mengen zu betrachten. Definition 3.2. Sei n ∈ N = {1, 2, . . . }. Die symmetrische Gruppe Sn (auf {1, 2, . . . , n}) besteht aus allen bijektiven Abbildungen σ : {1, 2, . . . , n} → {1, 2, . . . , n}, die sogenannten Permutationen. Die Verknüpfung ist durch die Verknüfung von Abbildungen gegeben. Das Einselement der Gruppe ist die Identitätsabbildung Id(i) = i für i ∈ {1, . . . , n}. Die Inversionsabbildung ordnet jeder Permutation σ ihre Umkehrabbildung σ −1 zu. Es handelt sich um die Gruppe S{1,2,...,n} aus Beispiel 1.17(iii). Sind σ1 , σ2 ∈ Sn zwei Permutationen so bezeichnet σ2 ◦ σ1 ∈ Sn ihre Verknüpfung Eine Permutation σ : {1, 2, . . . , n} → {1, 2, . . . , n} können wir tabellarisch wie folgt darstellen k σ(k) 1 2 3 ··· σ(1) σ(2) σ(3) · · · n σ(n) Dabei kommt in der zweiten Zeile jedes Element von {1, 2, . . . , n} genau einmal vor. Die Zahlen in der zweiten Zeile sind womöglich nicht mehr in aufsteigender Reihenfolge. Daher der Begriff Permutation. Beispiel 3.3. Die Gruppe S2 enthält nur Id und σ mit k Id(k) 1 2 1 2 und k σ(k) 1 2 2 1 Hier ist Id die Identitätsabbildung. Was ist σ ◦ σ = σ 2 ? Rechnen wir nach! Es gilt σ 2 (1) = σ(σ(1)) = σ(2) = 1 und σ 2 (2) = σ(σ(2)) = σ(1) = 2 und somit σ 2 = Id. Die Kardinalität der symmetrische Gruppe Sn nimmt mit wachsendem n stark zu. Lemma 3.4. Für n ∈ N gilt #Sn = n! = n · (n − 1) · · · · · 2 · 1. 64 3.1 Permutationen Beweis. Die Kardinalität #Sn ist die Anzahl bijektiver Abbildungen {1, . . . , n} → {1, . . . , n}. Wieviele Möglichkeiten gibt es hierfür? Für σ(1) gibt es zunächst die n Möglichkeiten {1, . . . , n}. Ist σ(1) einmal “gewählt” so darf σ(2) jeden Wert in {1, . . . , n} ausser der σ(1) annehmen; wir wollen, dass σ injektiv ist. Also bleiben n − 1 Möglichkeiten für σ(2). Analog gibt es für σ(3) genau n − 3 mögliche Werte, nämlich {1, . . . , n} r {σ(1), σ(2)}. Dies führen wir weiter und finden insgesamt n(n − 1) · · · 2 · 1 = n! Möglichkeiten für die Werte von σ. Hieraus ergibt sich die Behauptung. Also hat #S10 mit 3628800 mehr als drei Millionen Elemente! Die Gruppen Sn werden also schnell unübersichtlich gross. Wir können aber trotzdem mit diesen Gruppen arbeiten, den ihre Elemente sind aus einfachen Bausteinen aufgebaut: den Transpositionen. Definition 3.5. Sei n ∈ N. Eine Transposition ist eine Permutation τ ∈ Sn , die genau zwei Elemente aus {1, . . . , n} vertauscht. D.h. es gibt i, j ∈ {1, . . . , n} mit i 6= j und τ (i) = j, τ (j) = i Bemerkung 3.6. sowie τ (k) = k für alle k ∈ {1, . . . , n} r {i, j}. (i) Ist τ eine Transposition, so werden nur zwei Zahlen vertauscht k τ (k) 1 ··· 1 ··· i − 1 i i + 1 ··· i − 1 j i + 1 ··· j − 1 j j + 1 ··· j − 1 i j + 1 ··· n n hier wurde der Fall 1 < i < j < n dargestellt. (ii) Für jede Transposition τ gilt τ 2 = Id, denn wenn man die selben Zahlen zweimal hintereinander vertauscht, passiert insgesamt nichts. Beispiel 3.7. (i) Das Elemente von S2 welches nicht das Einselement ist, ist eine Transposition. (ii) Die Permutation σ ∈ S3 die durch k σ(k) 1 2 3 2 3 1 gegeben ist, ist keine Transposition. Die folgenden zwei Permutationen sind Tranpositionen k τ1 (k) 1 2 3 1 3 2 und k τ2 (k) 1 2 3 2 1 3 Deren Produkt ist τ2 ◦ τ1 = σ. 65 3 Die Determinante einer Matrix Obwohl nicht jede Permutation in Sn eine Transposition ist, kann man jede Permutation als Produkt von endlich vielen Transpositionen schreiben. Dies ist der Inhalt des nächsten Lemmas. Lemma 3.8. Sei n ∈ N und σ ∈ Sn . Dann gibt es Transpositionen τ1 , . . . , τN ∈ Sn mit σ = τN ◦ · · · ◦ τ1 . Beweis. Wir beweisen das Lemma über Induktion. Die Induktion ist über den Defekt einer Permutation. Diese definieren wir wie folgt. Sei σ ∈ Sn . Falls σ = Id, so defineren wir D(σ) = 0. Falls σ 6= Id dann gibt es einen Index i ∈ {1, . . . , n} mit σ(1) = 1, σ(2) = 2, ... σ(i − 1) = i − 1 und σ(i) 6= i. (3.2) Es muss zwangsläufig i ≤ n − 1 gelten. Der Defekt von σ ist D(σ) = n − i ≥ 1. Sei nun σ ∈ Sn beliebig. Falls D(σ) = n, so ist σ = Id. In diesem Fall ist nichts zu zeigen, da σ das leere Produkt aus Transpositionen ist. Wir nehmen nun an, dass D(σ) ≥ 1 und dass jede Permutation in Sn mit Defekt höchstens D(σ) − 1 ein Produkt aus Transpositionen ist. Sei i = n − D(σ). Nach Definition gilt σ(i) = j 6= i. Da σ injektiv ist, muss j > i gelten. Sei nun τ ∈ Sn die Transposition, welche i und j vertauscht. Wir behaupten D(τ ◦ σ) < D(σ). (3.3) Falls k ∈ {1, . . . , i − 1} so gilt σ(k) = k wegen (3.2) und τ (σ(k)) = τ (k) = k weil k < i < j. Weiterhin haben wir τ (σ(i)) = τ (j) = i nach der Wahl von τ . Also ist τ ◦ σ entweder die Identität, und damit D(τ ◦ σ) = 0 < D(σ) oder der kleinste Index i0 mit τ ◦ σ(i0 ) 6= i0 erfüllt i0 > i, also D(τ ◦ σ) = d − i0 < d − i = D(σ). In beiden Fällen folgt (3.3). Nach Induktionsvoraussetzung ist τ ◦σ = τN −1 ◦· · ·◦τ1 mit τ1 , . . . , τN −1 Transpositionen. Wir multiplizieren diese Gleichung von links mit τ und nutzen τ 2 = Id, um σ = τ ◦τN −1 ◦ · · · τ1 zu erhalten. Achtung. Die Faktorisierung einer Permutation als Produkt von Transpositionen ist im Allgemeinen nicht eindeutig: die Identität Id lässt sich immer als τ 2 mit τ einer Permutation beschreiben. Seien σ = τ1 ◦ · · · ◦ τN = τ10 ◦ · · · ◦ τN0 0 zwei verschiedene Faktorisierungen einer Permutation s ∈ SN in Transpositionen. Wir werden weiter unten beweisen, dass die Differenz der Anzahl Faktoren N − N 0 immer eine gerade Zahl ist. Dafür brauchen wir den Begriff des Vorzeichen einer Permutation. 66 3.1 Permutationen Definition 3.9. Sei n ∈ N und σ ∈ Sn . Man nennt ein Paar (i, j) mit i, j ∈ {1, . . . , n} einen Fehlstand der Permutation σ, falls i<j und σ(i) > σ(j). Sei m die Anzahl der Fehlstände von σ, dann definieren wir sign(σ) = (−1)m ∈ {−1, +1}. Man nennt sign(σ) das Vorzeichen von σ. Beispiel 3.10. gilt (i) Die Identitätsabbildung Id ∈ Sn besitzt keine Fehlstände. Deshalb sign(Id) = (−1)0 = 1. (ii) Sei n ∈ N mit n ≥ 2 und τ die Transposition, die 1 und 2 vertauscht. Das heisst, k τ (k) 1 2 3 ··· 2 1 3 ··· n n Dann ist (1, 2) der einzige Fehlstand von τ . Es gilt also sign(τ ) = (−1)1 = −1. (iii) Sei σ ∈ S3 durch k σ(k) 1 2 3 2 3 1 gegeben. Wir sehen dass (1, 3) und (2, 3) Fehlstände sind, aber (1, 2) kein Fehlstand ist. Also gilt sign(σ) = (−1)2 = 1. (iv) Ist σ wie in (iii) und τ ∈ S3 die Transposition, die 1 und 2 vertauscht. Dann gilt k τ ◦ σ(k) 1 2 3 1 3 2 Also ist τ ◦σ eine Transposition mit einzigem Fehlstand (2, 3). Wir finden sign(τ ◦ σ) = −1. Dass die Transpositionen in Beispiel (ii) und (iv) oben Vorzeichen −1 besitzt, ist kein Zufall. Lemma 3.11. Sei n ∈ N und τ ∈ Sn eine Transposition. Dann gilt sign(τ ) = −1. 67 3 Die Determinante einer Matrix Beweis. Da τ eine Transposition ist, vertauscht sie zwei Indizes i, j ∈ {1, . . . , n} mit i < j. Somit ist (i, j) (3.4) ein Fehlstand von τ ist. Es kann jedoch weitere Fehlstände geben. Sei i < k < j, dann gilt σ(i) = j > k = σ(k). Wir erhalten j − i − 1 zusätzliche Fehlstände (i, i + 1), (i, i + 2), . . . , (i, j − 1). (3.5) Andererseits ist auch (k, j) ein Fehlstand da σ(k) = k > i = σ(j). Diese Überlegung ergibt wiederum j − i − 1 Fehlstände (i + 1, j), (i + 2, j), . . . , (j − 1, j). (3.6) Wir haben also in (3.4), (3.5) und (3.6) insgesamt 1 + (j − i − 1) + (j − i − 1) = 1 + 2(j − i − 1) Fehlstände gefunden. Schliesslich deckt unsere Liste jeden Fehlstand von τ ab, denn ein Fehlstand (i0 , j 0 ) muss i0 = i oder j 0 = j erfüllen. Somit gilt σ(τ ) = (−1)1+2(j−i−1) = −1. Wir wissen, dass eine Transposition τ in Sn Vorzeichen −1 besitzt. Weiterhin gilt τ 2 = τ ◦ τ = Id, also sign(τ 2 ) = 1 = sign(τ )2 . Wir haben in Beispiel 3.10(iv) Permutationen gesehen, die sign(τ ◦ σ) = −1 = sign(τ )sign(σ) erfüllen. Teil (ii) des nächsten Lemma verallgemeinert diese Gleichung. Wir werden zeigen, dass sign(σ ◦ τ ) = sign(σ)sign(τ ) für alle σ, τ ∈ Sn gilt. In anderen Worten ist die Abbildung sign : Sn → {−1, +1} ein Gruppenhomomorphismus, wobei wir {−1, +1} als Untergruppe der multiplikativen Gruppe Q r {0} betrachten. Die erste Aussage ist eine Hilfsresultat, welches im Beweis von (ii) benötigt wird. Lemma 3.12. Sei n ∈ N. (i) Für jedes σ ∈ Sn gilt sign(σ) = σ(j) − σ(i) ; j−i 1≤i<j≤n Y die Indizes i und j laufen über {1, . . . , n} mit der Zusatzbedingung i < j. (ii) Für σ1 , σ2 ∈ Sn gilt sign(σ1 ◦ σ2 ) = sign(σ1 )sign(σ2 ). Insbesondere ist sign : Sn → {−1, +1} ein Gruppenhomomorphismus. 68 (3.7) 3.1 Permutationen Beweis. Wir beginnen mit Teil (i). Sei also σ ∈ Sn und m ≥ 0 die Anzahl Fehlstände von σ. Wir spalten den Zähler des Produkts (3.7) in zwei Faktoren auf Y Y Y (σ(j) − σ(i)) = (σ(j) − σ(i)) (σ(j) − σ(i)), i<j i<j σ(i)<σ(j) i<j σ(i)>σ(j) dabei läuft das Produkt über Paare i, j ∈ {1, . . . , n} mit der beschriebenen Zusatzbedingung. (Weshalb taucht kein Faktor σ(i) = σ(j) auf?) Jeder Faktor im Produkt ganz rechts ist negativ und entspricht genau einem Fehlstand von σ. Aus dieser Überlegung erhalten wir Y Y Y (σ(j) − σ(i)) = (−1)m (σ(j) − σ(i)) |σ(j) − σ(i)| i<j i<j σ(i)<σ(j) = (−1)m Y i<j σ(i)>σ(j) |σ(j) − σ(i)|. (3.8) i<j Da σ bijektiv ist, durchläuft σ(j) jede Zahl Q in {1, . . . , n} wenn j diese Menge durchläuft. Das letzte Produkt (3.8) ist also gleich i<j (j − i). Somit erhalten wir Y σ(j) − σ(i) i<j j−i = (−1)m . Die rechte Seite ist aber sign(σ) per Definition. Es folgt Teil (i). Nun beweisen wir (ii) und dafür dürfen wir die Formel für sign(σ) aus (i) benützen. Wir haben also Y σ1 (σ2 (j)) − σ1 (σ2 (i)) Y σ1 (σ2 (j)) − σ1 (σ2 (i)) σ2 (j) − σ2 (i) = sign(σ1 ◦ σ2 ) = j − i σ2 (j) − σ2 (i) j−i i<j i<j ! Y σ1 (σ2 (j)) − σ1 (σ2 (i)) = sign(σ2 ) (3.9) σ (j) − σ (i) 2 2 i<j | {z } (∗) Wir müssen noch zeigen, dass das Produkt (∗) gleich sign(σ1 ) ist. Dazu spalten wir das Produkt auf in zwei Faktoren: Y σ1 (σ2 (j)) − σ1 (σ2 (i)) Y σ1 (σ2 (j)) − σ1 (σ2 (i)) Y σ1 (σ2 (j)) − σ1 (σ2 (i)) = σ2 (j) − σ2 (i) σ2 (j) − σ2 (i) σ2 (j) − σ2 (i) i<j i<j i<j σ2 (i)<σ2 (j) σ2 (i)>σ2 (j) | {z (∗∗) } (3.10) Wir vertauschen die Rollen von i und j im Produkt (∗∗) und finden (∗∗) = Y i<j σ2 (i)>σ2 (j) σ1 (σ2 (i)) − σ1 (σ2 (j)) = σ2 (i) − σ2 (j) Y i>j σ2 (i)<σ2 (j) σ1 (σ2 (j)) − σ1 (σ2 (i)) σ2 (j) − σ2 (i) 69 3 Die Determinante einer Matrix Setzen wir diesen Ausdruck in (3.10) ein, so sehen wir Y σ1 (σ2 (j)) − σ1 (σ2 (i)) Y σ1 (σ2 (j)) − σ1 (σ2 (i)) = . σ (j) − σ (i) σ (j) − σ (i) 2 2 2 2 i<j σ2 (i)<σ2 (j) 1 (i) Dieser letzte Ausdruck ist dasselbe wie i<j σ1 (j)−σ , denn σ2 ist eine Bijektion. Also ist j−i (∗) gleich sign(σ1 ). Wir kombieren diese Erkenntnis mit (3.9) und erhalten sign(σ1 ◦ σ2 ) = sign(σ1 )sign(σ2 ), was zu zeigen war. Q Da sign : Sn → {−1, +1} ein Gruppenhomomorphism ist, ist sein Kern eine Untergruppe. Bemerkung 3.13. Sei σ eine Permutation in Sn . Dann existieren Transpositionen τ1 , . . . , τN ∈ Sn mit σ = τ1 ◦ · · · ◦ τN . Diese Transpositionen müssen nicht eindeutig sein. Aber Lemmas 3.11 und 3.12(ii) implizieren, dass sign(σ) = (−1)N gilt. Also ist die Parität von der Anzahl N Transpositionen eine wohldefinierte Invariante von σ. Definition 3.14. Sei n ∈ N. Die alternierende Gruppe An (auf {1, 2, . . . , n}) ist die Untergruppe {σ ∈ Sn : sign(σ) = +1} der symmetrischen Gruppe Sn . Bemerkung 3.15. Ist n ∈ N mit n ≥ 2 dann existiert eine Transposition τ ∈ Sn . Diese erfüllt sign(τ ) = −1 wegen Lemma 3.11. Damit gilt τ ∈ Sn r An also inbesondere An ( Sn . Lemma 3.16. Sei n ∈ N mit n ≥ 2 und η ∈ Sn mit sign(η) = −1. Dann gilt An ∪ An η = Sn und An ∩ An η = ∅ hier ist An η = {σ ◦ η : sign(σ) = +1}. Schliesslich sind An und An η gleich gross: #An = #An η = n!/2. Beweis. Sicher haben wir An ∪ An η ⊆ Sn . Ist andererseits σ ∈ Sn r An , so gilt sign(σ) = −1. Wegen Lemma 3.12(ii) haben wir sign(η)sign(η −1 ) = sign(η ◦ η −1 ) = +1, also sign(η −1 ) = −1. Aus dem selben Lemma folgt ebenfalls sign(σ ◦ η −1 ) = sign(σ)sign(η −1 ) = (−1)2 = +1 und somit σ ◦ η −1 ∈ An . Hieraus folgt σ ∈ An η und daher gilt auch An ∪ An η = Sn . Der Schnitt An ∩ An η ist leer, denn die Elemente von An und An η haben in Anbetracht von Lemma 3.12(ii) Vorzeichen +1 resp. −1. Um die Kardinalitätsfrage zu behandlen, reicht es #An = #An η zu zeigen, denn es gilt #Sn = n! wegen Lemma 3.4. Aber σ 7→ σ ◦ η definiert eine Bijektion An → An σ mit Umkehrabbildung σ 7→ σ◦η −1 . Also müssen Bild- und Urbildbereich gleiche Kardinalität besitzen. Wir werden später auf die Resultate über Permutationen in diesem Abschnitt verweisen. Schon bei der Definition der Determinante im nächsten Abschnitt werden diese ein wichtige Rolle spielen. 70 3.2 Die Definition der Determinante 3.2 Die Definition der Determinante Nach der Vorarbeit des letzten Abschnitts können wir sofort die Determinante definieren, um dann einige wichtige Eigenschaften zu beweisen. Definition 3.17. Sei K ein Körper, m ∈ N und a1,1 · · · a1,m .. ∈ Mat (K). A = ... m . am,1 · · · am,m Die Determinante von A ist det(A) = X sign(σ)a1,σ(1) a2,σ(2) · · · am,σ(m) . σ∈Sm Diese Darstellung der Determinante heisst Leibnizformel. Bemerkung 3.18. Nur quadratische Matrizen besitzen eine Determinante (den nur diese können invertierbar sein). Beispiel 3.19. (i) Für n = 2 gilt S2 = {Id, τ } mit τ die Transposition gegeben durch τ (1) = 2 und τ (2) = 1. Falls a1,1 a1,2 ∈ Mat2 (K) A= a2,1 a2,2 gilt det(A) = X sign(σ)a1,σ(1) a2,σ(2) σ = sign(Id)a1,1 a2,2 + sign(τ )a1,τ (1) a2,τ (2) = a1,1 a2,2 − a1,2 a2,1 . Somit stimmt det(A) mit dem Ausdruck in Lemma 2.25 und der Definition am Anfang dieses Kapitels überein. (ii) Sei a1,1 a1,2 a1,3 A = a2,1 a2,2 a2,3 a3,1 a3,2 a3,3 eine 3 × 3 Matrix mit Koeffizienten in einem Körper K. Ihre Determinante lässt sich mit der Regel von Sarrus berechnen: det(A) = a1,1 a2,2 a3,3 +a1,2 a2,3 a3,1 +a1,3 a2,1 a3,2 −a1,3 a2,2 a3,1 −a1,2 a2,1 a3,3 −a1,1 a2,3 a3,2 . Insgesagt treten 6 = 3! = #S3 Terme auf. 71 3 Die Determinante einer Matrix (iii) Die Determinante zweier wichtiger Matrizen werden wir nun berechnen. Die Nullmatrix in Matm (K) hat Determinante 0, denn jede Summand in der Definition ist 0. Die Einheitsmatrix erfüllt det Em = 1 und dies sieht man wie folgt. Wir schreiben Em = (ai,j )1≤i,j≤m , wobei ai,j = 1 genau dann, wenn i = j und ansonsten ist ai,j = 0. Gemäss Definition ist X det Em = sign(σ)a1,σ(1) · · · am,σ(m) . σ∈Sm Für σ = Id ist a1,σ(1) · · · am,σ(m) = a1,1 · · · am,m = 1. Sei nun σ ∈ Sm mit σ 6= Id, dann gilt a1,σ(1) · · · am,σ(m) = 0, da es ein i mit σ(i) 6= i gibt; für dieses haben wir ai,σ(i) = 0. Die Argumentation des letzten Beispiels impliziert λ1 0 · · · · · · 0 .. 0 λ2 0 . . . .. . . .. .. .. det A = λ1 · · · λm für A = . .. . .. 0 λm−1 0 0 ··· ··· 0 λm . Eine Matrix, deren Einträge ausserhalb der Diagonale Null sind, heisst Diagonalmatrix. Folgendes Lemma verallgemeinert die Aussage, dass die Nullmatrix Determinante Null besitzt. Lemma 3.20. Sei K ein Körper, m ∈ N und A ∈ Matm (K) mit einer Nullzeile. Dann gilt det(A) = 0. Beweis. Die Formel für die Determinante von A = (aij )1≤i,j≤m lautet X det(A) = sign(σ)a1,σ(1) · · · am,σ(m) . (3.11) σ∈Sm Ist beispielsweise die i-te Zeile von A eine Nullzeile, so gilt ai,1 = ai,2 = · · · = ai,m = 0. Wegen (3.11) tauch in jedem Summand von det(A) ein Faktor aus der i-ten Zeile auf. Deshalb ist jeder Summand 0 und daher gilt det(A) = 0. Die zwei wichtigsten Eigenschaften halten wir in folgendem Satz fest. Er verallgemeinert erstens die Tatsache, dass die Determinante einer 2 × 2 Matrix über ihre Invertierbarkeit entscheidet, siehe Lemma 2.25 und zweitens die Multiplikativität der Determinante für 2 × 2 Matrizen, cf. Lemma 3.1. Satz 3.21. Sei K ein Körper und m ∈ N. 72 3.2 Die Definition der Determinante (i) Eine Matrix A ∈ Matm (K) ist invertierbar genau dann, wenn det(A) 6= 0. In anderen Worten GLm (K) = {A ∈ Matm (K) : det(A) 6= 0}. (ii) Für A, B ∈ Matm (K) gilt det(AB) = det(A) det(B). Beweis. Später. Bevor wir den Satz beweisen, werden wir zunächst einige einfachere Rechenregeln der Determinante kennenlernen. Lemma 3.22. Sei K ein Körper, m ∈ N und a1 , . . . , am ∈ K m Zeilenvektoren der Länge m. (i) Die Determinante ist linear in den Zeilen, d.h. für jedes i ∈ {1, . . . , m} und jeden Zeilenvektor a0i ∈ K m und jedes Paar λ, µ ∈ K gilt a1 a1 a1 .. .. .. . . . det λai + µa0i = λ det ai + µ det a0i . (3.12) . . . .. .. .. am am am (ii) Die Determinante ist alternierend, d.h. falls es zwei verschiedene Indizes i, j ∈ {1, . . . , m} mit ai = aj gibt, dann gilt a1 det ... = 0. am Beweis. Wir schreiben ai = (ai,1 , . . . , ai,m ) für jedes i ∈ {1, . . . , m}. Der Beweis von Teil (i) ist eine formale Konsequenz der Definition der Determinante. Sei dazu a0i = (a0i,1 , . . . , a0i,m ). Per Definition ist die Determinante auf der rechten Seite von (3.12) gleich X sign(σ)a1,σ(1) · · · ai−1,σ(i−1) (λai,σ(i) + µa0i,σ(i) )ai+1,σ(i+1) · · · am,σ(m) σ∈Sm =λ X sign(σ)a1,σ(1) · · · ai,σ(i) · · · am,σ(m) + µ σ∈Sm X sign(σ)a1,σ(1) · · · a0i,σ(i) · · · am,σ(m) σ∈Sm a1 .. . = λ det ai + µ det . .. am a1 .. . a0i .. . am 73 3 Die Determinante einer Matrix was zu zeigen war. Für den Beweis von Teil (ii) benötigen wir nun die die Theorie der Permutationen aus dem letzten Abschnitt. Zunächst müssen wir uns im Klaren sein, dass m ≥ 2. Denn gilt m = 1 so können wir natürlich nicht zwei verschiedene Zeilen gleich sein! Sei a1 a1,1 · · · a1,m .. A = ... = ... . am am,1 · · · am,m Nach Voraussetzung sind die i-te un j-te Zeile von A gleich. Wir müssen det(A) = 0 zeigen. Wir dürfen i < j annehmen und das vereinfacht die Präsentation. Wir fixieren die Transposition τ ∈ Sm , welche i und j vertauscht. Wir erinnern uns nun an Lemma 3.16 welches besagte, dass die symmetrische Gruppe wie folgt zerlegt werden kann: Sm = Am ∪ Am τ und Am ∩ Am τ = ∅. Die Determinante von A lässt sich also in zwei Teilsummen zerlegen: X X det(A) = sign(σ) a1,σ(1) · · · am,σ(m) + sign(σ ◦ τ )a1,σ(τ (1)) · · · am,σ(τ (m)) | {z } σ∈Am σ∈Am +1 Wegen Multiplikativität des Vorzeichens gilt sign(σ ◦ τ ) = sign(σ)sign(τ ), cf. Lemma 3.12(ii). Eine Permutation hat Vorzeichen −1 wegen Lemma 3.11. Also folgt det(A) = X a1,σ(1) · · · am,σ(m) − σ∈Am X a1,σ(τ (1)) · · · am,σ(τ (m)) . (3.13) σ∈Am Die Strategie ist nun die Folgende. Wir werden zeigen, dass sich jeder Term der ersten Summe mit einem Term der zweiten Summe aufhebt. Die Details sind wie folgt. Sei σ ∈ Am beliebig. Es gilt a1,σ(τ (1)) · · · = a1,σ(1) · · · ai,σ(τ (i)) · · · ai,σ(j) · · · aj,σ(τ (j)) · · · aj,σ(i) · · · am,σ(τ (m)) am,σ(m) da τ (j) = i, τ (i) = j, alle anderen Werte von τ bleiben unberührt. Weiterhin sind die i-te und j-te Zeilen gleich, also = = a1,σ(τ (1)) · · · a1,σ(1) · · · a1,σ(1) ai,σ(τ (i)) · · · ai,σ(i) · · · ··· aj,σ(τ (j)) · · · aj,σ(j) · · · am,σ(τ (m)) am,σ(m) am,σ(m) . Es handelt sich um einen Summand in der Leibnizformel für die Determinante. Nun sieht man, dass sich die Terme in (3.13) gegenseitig aufheben. Es folgt det(A) = 0. 74 3.2 Die Definition der Determinante Wir wollen untersuchen, wie sich die Determinante einer Matrix unter Zeilenumformungen verändert. Zur Erinnerung: es gab drei verschiedene Zeilenumformungen und diese können durch linksmultiplikation mit Elementarmatrizen realisiert werden. Dies haben wir in Lemma 2.31 gesehen. Lemma 3.23. Sei K ein Körper, m ∈ N, und A ∈ Matm (K). (i) (Zeilenaddition) Seien i, j ∈ {1, . . . , m} mit i 6= j und λ ∈ K. Wir setzen A0 = E I (i, j, λ)A. Dann gilt det(A0 ) = det(A) und det E I (i, j, λ) = 1. (ii) (Zeilenvertauschen) Seien i, j ∈ {1, . . . , m} mit i 6= j und A0 = E II (i, j)A. Dann gilt det(A0 ) = − det(A) und det E II (i, j) = −1. (iii) (Skalarmultiplikation einer Zeile) Sei i ∈ {1, . . . , m} und λ ∈ K. Wir setzen A0 = E III (i, λ)A. Dann gilt det(A0 ) = λ det(A) und det E III (i, λ) = λ. Beweis. Seien a1 , . . . , am die Zeilen von A. Eine Zeilenumformung des Typs I wie in (i) ersetzt ai durch ai + λaj . Wir zeigen den Fall i < j, gilt j > i so ist das Argument ähnlich. Wegen Lemma 3.22(i) gilt die zweite Gleichung in 0 det(A ) = det a1 .. . ai ai + λaj .. . . +λ det = det . . a aj j .. .. . . am am {z } | a1 .. . a1 .. . aj .. . . aj .. . am det(A) Ganz rechts steht nun eine Matrix mit zwei gleichen Zeilen. Wegen Lemma 3.22(ii) muss die entsprechende Determinante gleich 0 sein. Es folgt also det(A0 ) = det(A). Wenden man nun die eben bewiesen Gleichung auf die Einheitsmatrix A = Em an, so folgt det(E I (i, j, λ)) = det(Em ) = 1. Hieraus folgt die zweite Behauptung in (i). 75 3 Die Determinante einer Matrix Um (ii) zu zeigen, benötigen wir einen Trick. Wir nehmen wieder i < j an und definieren die Hilfsmatrix a1 .. . ai + aj .. . B= . a +a i j .. . am Sie stimmt in allen Zeilen, ausser der i-ten und j-ten, mit A überein. Da aber B zwei gleiche Zeilen besitzt, gilt det(B) = 0. Nun formen wir det(B) mit Hilfe von Lemma 3.22(i) zweimal um. Linearität in der i-ten Zeile ergibt a1 a1 .. .. . . aj ai .. .. + det . 0 = det(B) = det . . a +a a +a i i j j .. .. . . am am Nun nutzen wir Linearität in der j-ten Zeile aus, um a1 a1 .. .. . . ai ai . . 0 = det .. + det .. a a j i . . .. .. am am {z } | {z | =0 =det(A) a1 a1 .. .. . . aj aj . + det .. + det ... a a i j . . .. .. am am } | {z } | {z =det(A0 ) =0 } zu erhalten. Dass die äusseren beiden Matrizen Determinante Null haben, folgt da sie je zwei identische Zeilen besitzen. Wir erhalten det(A) + det(A0 ) = 0 und daher det(A0 ) = − det(A). Die eben bewiesen Gleichung auf die Einheitsmatrix A = Em angewandt, impliziert det(E II (i, j)) = − det(Em ) = −1. Die Behauptung (iii) ist die einfachste. Den Lemma 3.22(i) mit µ = 0 und a0i = 0 ergibt 76 3.2 Die Definition der Determinante sich a1 .. . det(A0 ) = det λaj = λ det . .. am a1 .. . aj = λ det(A). .. . am Die eben bewiesen Gleichung auf die Einheitsmatrix A = Em angewandt, impliziert det(E III (i, λ)) = λ det(Em ) = λ. 77 Index Abbildung von Mengen, 12 Additive Gruppe eines Körpers, 23 Allgemeine lineare Gruppe, 43 Alternierende Gruppe, 70 Bijektive Abbildung, 12 Bild eines Gruppenhomomorphismuses, 21 Charakteristik eines Körpers, 30 Definitionsbereich, 12 Determinante, 71 Diagonalmatrix, 72 Einheitsmatrix, 34 Einsmatrix, 34 Elementarmatrizen, 47 Kern eines Gruppenhomomorphismuses, 21 Kommutativer Ring, 23 Leibnizformel, 71 Linksinverses, 41 Matrix, 33 Matrixprodukt, 37 Multiplikative Gruppe eines Körpers, 26 Neutrales Element einer Gruppe, 15 Nullmatrix, 34 Permutation, 64 Pivoteintrag, 51 Primzahl, 29 Quadratische Matrix, 33 Fehlstand einer Permutation, 67 Grad eines Polynoms, 25 Gruppenisomorphismus, 20 Homogenes lineares Gleichungssystem, 44 Identitätsabbildung, 13 Identitätsmatrix, 34 Inhomogenes lineares Gleichungssystem, 44 Injektive Abbildung, 12 Inverses Element, 19 Inverses Element in einer Gruppe, 15 Invertierbare Matrix, 41 Körper, 26 Kardinalität einer Menge, 12 Kartesisiches Produkt zweier Mengen, 11 Rechtsinverses, 41 Ring, 23 Schnitt zweier Mengen, 11 Skalarmultiplikation, 35 Spaltenvektor, 39 Summe zweier Matrizen, 34 Surjektive Abbildung, 12 Symmetrische Gruppe, 16 Symmetrische Gruppe Sn , 64 Transposition, 65 Triviale Lösung eines homogenen Gleichungssystems, 55 Untergruppe, 21 Vereinigung zweier Mengen, 11 79 Index Verknüpfungsabbildung einer Gruppe, 15 Vorzeichen einer Permutation, 67 Wertebereich, 12 Zeilenstufenform, 51 Zeilenumformungen, 47 Zeilenvektor, 39 80
© Copyright 2024 ExpyDoc