Lineare Algebra PDF

Lineare Algebra Tim Netzer Inhaltsverzeichnis 1 Einleitung und Grundlagen 1 1.1 Was ist lineare Algebra?..................... 1 1.2 Notation............................ 2 1.3 Logische Grundlagen.........

Lineare Algebra Tim Netzer Inhaltsverzeichnis 1 Einleitung und Grundlagen 1 1.1 Was ist lineare Algebra?..................... 1 1.2 Notation............................ 2 1.3 Logische Grundlagen...................... 3 1.3.1 Aussagenlogik..................... 3 1.3.2 Prädikatenlogik..................... 3 1.3.3 Einige Beweismethoden................. 4 1.4 Mengen, Relationen und Abbildungen.............. 7 2 Gauß-Algorithmus und Matrixrechnung 25 2.1 Der Gauß-Algorithmus..................... 25 2.2 Gruppen, Ringe und Körper................... 33 2.2.1 Grundbegriffe...................... 33 2.2.2 Die komplexen Zahlen F................ 37 2.2.3 Endliche Körper..................... 52 2.3 Matrixrechnung........................ 56 3 Vektorräume und lineare Abbildungen 67 3.1 Vektorräume.......................... 68 3.1.1 Grundbegriffe...................... 68 3.1.2 Lineare Unabhängigkeit, Basen und Dimension..... 74 3.2 Lineare Abbildungen...................... 84 3.2.1 Grundbegriffe...................... 85 3.2.2 Die Dimensionsformel................. 92 3.2.3 Der Rang einer Matrix................. 96 3.2.4 Darstellungsmatrizen F................ 98 3.2.5 Der Dualraum F.................... 104 iii iv INHALTSVERZEICHNIS 4 Die Determinante 107 4.1 Permutationen......................... 107 4.2 Die Determinante und ihre Eigenschaften............ 113 4.3 Entwicklungsformeln und Cramersche Regel F......... 120 5 Eigenwerte und Eigenvektoren 125 5.1 Eigenwerte und Eigenvektoren................. 125 5.2 Polynome und Nullstellen.................... 130 5.3 Diagonalisierung........................ 133 5.4 Trigonalisierung........................ 139 5.5 Die Jordan’sche Normalform.................. 142 5.6 Der Satz von Cayley-Hamilton und das Minimalpolynom.... 149 6 Skalarprodukte und Spektralsätze 155 6.1 Skalarprodukte und Normen.................. 155 6.2 Orthonormalbasen....................... 160 6.3 Spektralsätze.......................... 166 6.4 Positiv semidefinite Matrizen.................. 175 7 Bilinearformen 181 7.1 Grundbegriffe.......................... 181 7.2 Symmetrische Bilinearformen................. 185 7.3 Quadratische Formen...................... 192 8 Konvexität 197 8.1 Grundbegriffe.......................... 197 8.2 Trennungssätze......................... 203 8.3 Polyeder und Polytope...................... 207 9 Verschiedenes 217 9.1 Konstruktionen mit Vektorräumen............... 217 9.1.1 Summen und Produkte................. 217 9.1.2 Faktorräume...................... 221 9.1.3 Tensorprodukte..................... 224 9.2 Räume von unendlicher Dimension............... 228 9.2.1 Algebraische Sichtweise................. 228 9.2.2 Algebraisch-analytische Sichtweise........... 231 9.3 Kategorientheorie........................ 233 INHALTSVERZEICHNIS v Literaturverzeichnis 239 Übungsaufgaben 241 vi INHALTSVERZEICHNIS Kapitel 1 Einleitung und Grundlagen 1.1 Was ist lineare Algebra? In vielen Bereichen der Mathematik beschäftigt man sich mit dem Lösen von Gleichungssystemen. Man will entweder Lösungen explizit finden (am besten so- gar alle existierenden Lösungen), oder zumindest die Menge aller Lösungen geo- metrisch gut verstehen. Die lineare Algebra befasst sich mit den denkbar einfachsten Gleichungssyste- men, nämlich mit linearen Gleichungssystemen (über geeigneten Zahlbereichen). Hier hat man im Lauf der Zeit auf fast alle Fragen befriedigende Antworten ge- funden. Da lineare Gleichungssysteme sowohl in der Mathematik als auch in an- deren Wissenschaften sehr häufig auftreten, zählt die lineare Algebra zu den wich- tigsten theoretischen Grundlagen in vielen Gebieten von Wissenschaft und Tech- nik. Die Lösungsmenge eines linearen Gleichungssystems hat eine einfache geome- trische Struktur, die eines (affinen) Vektorraums. Darum können solche Lösungs- mengen durch endlich viele Daten komplett angegeben werden, selbst im Fall un- endlich vieler Lösungen. Zusätzlich existiert mit dem (vielleicht schon aus der Schule bekannten) Algorithmus von Gauß eine effiziente algorithmische Metho- de, um lineare Gleichungssysteme zu lösen. Alle diese Tatsachen lernen Sie im Verlauf dieser Vorlesung kennen. Damit sind dann viele praktische Fragen zu li- nearen Gleichungssystemen eigentlich bereits beantwortet. Die Mathematik fragt aber immer auch nach einem tieferen Verständnis und nach Verallgemeine- rungen und Erweiterungen der bekannten Ergebnisse. Um lineare Gleichungssy- steme in allen Aspekten gründlich zu verstehen, entwickeln wir die Theorie von 1 2 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Vektorräumen und linearen Abbildungen. Das ist aber nicht nur Selbstzweck, denn aus dem tieferen Verständnis ergeben sich neue Sichtweisen und Erkennt- nisse auch über die ursprünglichen konkreten Fragen. Auch aus Sicht der Geo- metrie sind Vektorraumtheorie und ihre Erweiterungen unerlässlich. Die Vorlesung Lineare Algebra richtet sich an Studierende unterschiedlicher Fach- richtungen. Sie geht deshalb nicht an jeder Stelle so weit in die Tiefe, wie ein rein mathematischer Ansatz vielleicht nahelegen würde. Insbesondere äußert sich das dadurch, dass mit F gekennzeichnete Abschnitte erst im Vertiefungsteil der Vor- lesung behandelt werden. Mit Vertiefung umfasst die lineare Algebra 1 den Stoff bis etwa zur Mitte von Kapitel 5. Der Rest des Skripts ist dann Stoff der Vorlesung Lineare Algebra 2. Zur linearen Algebra gibt es unzählige Bücher und Skripten. Grundsätzlich ste- hen alle wichtigen Resultate in fast jedem dieser Texte. Wer zusätzliche Literatur konsultieren möchte, kann sich also ganz nach den eigenen Vorlieben richten. Als erste Anregungen empfehlen wir die Bücher von Bosch , Fischer und Lang. 1.2 Notation Im Skript und der Vorlesung werden durchgehend die folgende Symbole und No- tationen verwendet: ∧ und ∨ oder ⇒ wenn, dann ¬ nicht ∀ für alle ∃ es existiert ∃! es existiert genau ein N natürliche Zahlen (mit Null) Z ganze Zahlen Q rationale Zahlen R reelle Zahlen ∈ ist Element von ∈ / ist kein Element von. 1.3. LOGISCHE GRUNDLAGEN 3 1.3 Logische Grundlagen 1.3.1 Aussagenlogik In der Aussagenlogik weisen wir jeder Aussage einen sogenannten Wahrheits- wert zu, der entweder W für wahr oder F für falsch lautet. Wenn wir dann Aus- sagen mit sogenannten Junktoren verknüpfen erhalten wir neue Aussage, deren Wahrheitswert sich aus den Wahrheitswerten der einzelnen Teilaussagen ergibt. Junktoren sind Verknüpfungen wie und, oder, nicht.... Sehr übersichtlich stellt man so etwas in einer Wahrheitstafel dar. Dabei ste- hen in der ersten Zeile zunächst die einzelnen Aussagen (oft A, B...) und danach die daraus konstruierten Aussagen. In den darunterliegenden Zeilen stehen alle möglichen Wahrheitswerte der ursprünglichen Aussagen und die sich ergeben- den Werte für die konstruierten Aussagen: A B ¬A (nicht) A ∧ B (und) A ∨ B (oder) A ⇒ B (Implikation) (¬A) ∨ B W W F W W W W W F F F W F F F W W F W W W F F W F F W W In einer solchen Tafel kann man auch ablesen, ob zwei Aussagen logisch äqui- valent sind. Sie sind es genau dann, wenn für alle Wahrheitsbelegungen der ur- sprünglichen Aussagen jeweils beide dieselben Wahrheitswerte haben. So sieht man an der oberen Tabelle zum Beispiel, dass die Aussage “A ⇒ B” (A impliziert B) äquivalent ist zur Aussage “(¬A) ∨ B” ((nicht A) oder B). 1.3.2 Prädikatenlogik Häufig hat man es mit logischen Aussagen zu tun, die nicht einfach wahr oder falsch sind, sondern die gewissen Leerstellen/Variablen enthalten. Eine solche Aussage kann nur dann als wahr oder falsch beurteilt werden, wenn etwas für die Leerstelle eingesetzt wird. Ein Beispiel ist die Aussage x ist größer gleich Null (in Formeln: x > 0). Die Wahrheit dieser Aussage kann nur entscheiden werden, wenn für x etwas eingesetzt wird. Die obere Aussage ist in den ganzen Zahlen etwa wahr wenn man für x die Zahl 1 einsetzt, und falsch wenn man die Zahl −1 einsetzt. 4 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Durch Hinzufügen von Quantoren kann eine solche Aussage jedoch in eine Aus- sage umformuliert werden, die dann für sich selbst wahr oder falsch ist (natür- lich abhängig davon, in welchem mathematischen Modell sie betrachtet wird). Quantoren sind für uns der All-Quantor ∀ (mit der Bedeutung für alle) und der Existenz-Quantor ∃ (mit der Bedeutung es existiert). So ergibt sich beispielsweise die Aussage ∀x : x > 0 welche in den ganzen Zahlen falsch ist, und die Aussage ∃x : x > 0 welche in den ganzen Zahlen wahr ist. Solche Aussagen können dann natürlich wie im ersten Abschnitt durch Junktoren weiter zu komplizierteren Aussagen zu- sammengesetzt werden. 1.3.3 Einige Beweismethoden Um eine mathematische Aussage zu beweisen gibt es verschiedene Methoden (die jedoch für sich allein meistens nicht ausreichen, sondern zusätzliche mathema- tische Kreativität benötigen). Eine Auswahl stellen wir hier kurz vor. (Gegen-)Beweis durch (Gegen-)Beispiel Eine Existenzaussage kann man manchmal sehr leicht durch die Angabe eines Beispiels beweisen. So wird die Aussage ∃x : x > 0 für die ganzen Zahlen dadurch bewiesen, dass man die Zahl 1 als Beispiel an- gibt. Genauso kann eine All-Aussage manchmal durch Angabe eines Gegenbei- spiels widerlegt werden. Soll zum Beispiel die Aussage ∀x : x > 0 für die ganzen Zahlen widerlegt werden, kann man einfach die Zahl −1 angeben. Aber Vorsicht: eine universelle Aussage wie ∀x : x > 0 ist jedoch durch die Angabe eines positiven Beispiels noch nicht bewiesen. Die Aussage besagt ja gerade etwas über alle Zahlen, nicht nur über eine. In einem endlichen Zahlbereich könnte man sie eventuell durch gezielte Betrachtung aller in Frage kommenden Belegungen 1.3. LOGISCHE GRUNDLAGEN 5 für x beweisen. Kommen unendlich viele Belegungen in Fragen, muss man sich etwas anderes einfallen lassen. Ebenso lässt sich eine Existenzaussage im Allgemeinen nicht dadurch widerle- gen, dass man ein Gegenbeispiel angibt. Man müsste dazu zeigen, dass alle in Frage kommenden Belegungen für x die Aussage nicht erfüllen. Beweis durch Widerspruch Wenn man eine Aussage beweisen möchte, kann man ihre Falschheit annehmen und daraus einen Widerspruch abzuleiten versuchen. Das nennt man Beweis durch Widerspruch. Angenommen man möchte beweisen, dass es unendlich viele Primzahlen gibt. Man könnte das direkt dadurch tun, dass man eine Vorschrift angibt, anhand derer wirklich unendliche viele Primzahlen produziert werden. Für einen Wider- spruchsbeweis würde man hingegen annehmen dass die Aussage falsch ist, dass also nur endlich viele Primzahlen existieren. Aus dieser Aussage leitet man dann mit logischen Schlüssen einen offensichtlichen Widerspruch her. Dadurch ist die ursprüngliche Aussage ebenso bewiesen. Je nach Aussage ist ein Widerspruchsbeweis manchmal etwas leichter durchzu- führen. Sehr häufig (nicht immer!) lässt sich ein Widerspruchsbeweis aber auch in einen direkten Beweis umformen und umgekehrt. Die meisten Mathematiker bevorzugen aus ästhetischen Gründen einen direkten Beweis gegenüber einem Widerspruchsbeweis. Beweis durch Kontraposition Möchte man die Aussage A⇒B beweisen (also “A impliziert B”), kann man stattdessen auch die Aussage (¬B) ⇒ (¬A) (also “(nicht B) impliziert (nicht A)”) zeigen. Beide Aussagen sind nämlich logisch äquivalent, wie man durch die Angabe einer Wahrheitstafel leicht zeigen kann. Dieses Vorgehen nennt man Beweis durch Kontraposition. Will man beispielsweise zeigen, dass jede durch 4 teilbare Zahl auch durch 2 teil- bar ist, könnte man stattdessen zeigen, dass eine nicht durch 2 teilbare Zahl auch nicht durch 4 teilbar sein kann. 6 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Vollständige Fallunterscheidung Manchmal muss man eine allgemeine Aussage in mehrere Teile aufteilen, die je- weils verschiedene Beweise erfordern. Möchte man eine Aussage etwa für alle na- türlichen Zahlen beweisen, kann man sie zunächst für die geraden und dann für die ungeraden Zahlen zeigen. Das nennt man Fallunterscheidung. Wichtig ist dabei, dass jede der möglichen Situationen in mindestens einem der Fälle abge- deckt ist. Schubfachprinzip Wenn man mindestens n + 1 Objekte auf höchstens n Schubfächer aufteilt, müs- sen sich in mindestens einem der Fächer mindestens 2 Objekte befinden. Diese einfache Beobachtung nennt man Schubfachprinzip. Manchmal kann so ein sehr eleganter Beweis geführt werden, zum Beispiel dass unter 366 Personen minde- stens zwei am gleichen Tag Geburtstag haben müssen. Beweis durch vollständige Induktion Wenn man eine Aussage für alle natürlichen Zahlen 0, 1, 2, 3,... zeigen möchte, kann man das zum Beispiel durch vollständige Induktion tun. Der erste Schritt dabei ist der Induktionsanfang (IA). Dabei zeigt man die Gültig- keit der Aussage für die kleinstmögliche Zahl, etwa die 0 (manchmal soll die Aus- sage auch erst ab einer bestimmten Zahl gelten, dann startet man dort). Meistens ist das offensichtlich wahr, oder durch eine sehr einfache Rechnung einsichtig. Dann nimmt man an dass die Aussage bereits für eine allgemeine natürliche Zahl n gilt (oder für alle Zahlen bis n), das nennt man die Induktionsvoraussetzung (IV). Ausgehend davon beweist man die Aussage dann für die nächste Zahl n + 1. Das ist der sogenannte Induktionsschritt (IS). Hat man das getan, ist die Aussage bewiesen. Das Prinzip kann durch den Domi- noeffekt veranschaulicht werden. Wenn der erste Stein umgestoßen wird, und sichergestellt ist dass jeder Stein den nächsten umstößt, dann fällt irgendwann jeder Stein. Als Beispiel wollen wir die Gleichung n(n + 1) 0 + 1 + 2 + ··· + n = 2 für jede natürliche Zahl n beweisen. Im Induktionsanfang rechnen wir die Gül- tigkeit für n = 0 nach. Links steht dann 0 und rechts offensichtlich auch. Die 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 7 Induktionsvoraussetzung ist nun, dass die Aussage für ein festes (aber allgemei- nes) n bereits stimmt. Im Induktionssschritt müssen wir die Aussage jetzt für n + 1 zeigen, also die folgende Aussage beweisen: (n + 1)(n + 2) 0 + 1 + · · · + n + (n + 1) =. 2 Dazu gehen wir folgendermaßen vor: IV n(n + 1) 0 + 1 + · · · + n + (n + 1) = + (n + 1) 2 n(n + 1) 2(n + 1) = + 2 2 n(n + 1) + 2(n + 1) = 2 (n + 1)(n + 2) =. 2 Für die erste Gleichheit haben wir die Induktionsvoraussetzung benutzt, also dass die Summe aller Zahlen bis n gerade n(n+1) 2 ergibt. Damit ist die Aussage allge- mein bewiesen. 1.4 Mengen, Relationen und Abbildungen Der Begriff der Menge gehört zu den wichtigsten Begriffen der Mathematik über- haupt. Lange Zeit wurden Mengen einfach definiert als Zusammenfassung bestimmter wohlunterschiedener Objekte der Anschauung oder des Denkens zu einem Ganzen. Die einzelnen Objekte heißen Elemente der Menge. Bemerkung 1.4.1 (F). Diese Definition ist eher philosophischer Natur und ma- thematisch nicht exakt. So könnte man etwa die Menge betrachten, deren Ele- ment alle Mengen sind: A := {M | M Menge}. Es handelt sich hier offenbar um eine Zusammenfassung von wohlunterschiede- nen Objekten zu einem Ganzen. Somit müsste A also laut Definition eine Menge sein, und damit ein Element von sich selbst: A ∈ A. 8 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Wem es nicht seltsam genug vorkommt, dass Mengen Elemente ihrer selbst sein können, der betrachte nun folgende Menge: B := {M | M Menge, M ∈ / M}. Auch hier handelt es sich um eine Zusammenfassung wohlunterschiedener Ob- jekte, also um eine Menge. Es gibt nun zwei Möglichkeiten. Entweder gilt B ∈ B. Aufgrund der Definition von B muss dann aber B ∈ / B gelten, ein Widerspruch. Also muss die zweite Möglichkeiten eintreten, nämlich B ∈ / B. Damit erfüllt B aber die Bedingung in der Definition von B und es folgt B ∈ B, wieder ein Wi- derspruch. Der einzige Weg aus diesem Dilemma besteht darin, B nicht als Menge zuzulas- sen. Damit entpuppt sich die angegebene Mengendefinition als nicht zufrieden- stellend. Es gibt nun in der Tat mathematisch saubere Möglichkeiten, mit diesem Problem umzugehen und solche Widersprüche zu vermeiden. Allerdings ist die lineare Algebra nicht der richtige Ort, das zu besprechen. Wir bleiben deshalb im folgenden bei der nicht-exakten Mengendefinition und behalten nur im Hinter- kopf, dass es theoretisch hier etwas zu bedenken gibt. 4 Mengen können auf verschiedene Weise angegeben werden. Eine endliche Men- ge kann man beispielsweise einfach dadurch angeben, dass man alle ihre Elemen- te aufzählt (gewöhnlich verwendet man geschwungenen Klammern für Mengen- definitionen): {a, b, c, d}, {Klaus, Bello, Patscherkofel}, {1, π}. Bei unendlichen Mengen geht das nicht. Man kann diese Mengen beispielswei- se angeben, indem man ihre Elemente andeutet und auf den Verstand der Leser hofft: N := {0, 1, 2, 3,...}, Z := {... , −2, −1, 0, 1, 2,...}. Oft werden Mengen auch dadurch angegeben, dass man in der Mengenklammer nach einem senkrechten Strich Bedingungen auflistet, die die Zugehörigkeit von Elementen definiert. Dabei kann auch auf bereits bekannte Mengen zurückge- griffen werden. Beispiele dafür sind na o Q := | a, b ∈ Z, b 6= 0 , P := {a | a ∈ N, a Primzahl}. b Man beachte, dass in einer Menge keine Reihenfolge der Elemente vorgegeben oder relevant ist. So gilt etwa {a, b, c} = {c, b, a}. 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 9 Außerdem kann jedes Element in einer Menge nur einmal enthalten sein, selbst wenn man es (überflüssigerweise) mehrfach aufzählt. Es gilt also {a, a, b, c} = {a, b, c}. Vom Mengenbegriff ausgehend definiert man nun weitere wichtige Konzepte. Definition 1.4.2. (i) Eine Menge N heißt Teilmenge einer Menge M , wenn jedes Element von N auch ein Element von M ist. Wir verwenden dafür die Notation N ⊆ M. Als Formel geschrieben liest sich das so: N ⊆M :⇔ ∀a : a ∈ N ⇒ a ∈ M. N M (ii) Für zwei Mengen M, N bezeichnet M ∪ N die Vereinigungs-, M ∩ N die Schnittmenge sowie M \ N die Mengendifferenz: M ∪ N := {a | a ∈ M ∨ a ∈ N } M ∩ N := {a | a ∈ M ∧ a ∈ N } M \ N := {a | a ∈ M ∧ a ∈ / N }. M ∪N M ∩N M \N (iii) Für zwei Mengen M, N ist das kartesische Produkt von M und N die Menge aller geordneten Paare von Elementen aus M und N : M × N := {(a, b) | a ∈ M, b ∈ N }. 10 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN (a, b) a M M ×N b N 4 Bemerkung/Beispiel 1.4.3. (i) Es gibt genau eine Menge ohne Elemente, die leere Menge. Wir verwenden dafür die Notation ∅: ∅ := {}. (ii) Es gilt {a, b, c} ∪ {a, 7, π} = {a, b, c, 7, π} {a, b, c} ∩ {a, 7, π} = {a} {a, b, c} \ {a, 7, π} = {b, c}. (iii) Für M = {a, b, c} und N = {1, 7, π} ergibt sich M × N = {(a, 1), (a, 7), (a, π), (b, 1), (b, 7), (b, π), (c, 1), (c, 7), (c, π)}. (iv) Die Elemente von M × N sind geordnete Paare, es ist also beispielsweise (π, a) kein Element von M × N in (iii). Insbesondere sind M × N und N × M unter- schiedliche Mengen. (v) Hat M genau m und N genau n Elemente, so hat M ×N genau m·n Elemente. (vi) Das kartesische Produkt kann analog auch für mehr als zwei Mengen gebildet werden. Für Mengen M1 ,... , Mn setzt man dabei M1 × M2 × · · · × Mn := {(a1 ,... , an ) | a1 ∈ M1 ,... , an ∈ Mn }. Für eine Menge M schreibt man auch M n := M | × ·{z · · × M}. n Ein Beispiel dafür ist der aus der Schule bekannte R3. 4 Definition 1.4.4. Seien M, N Mengen. Eine Relation zwischen M und N ist eine Teilmenge R ⊆ M × N. Statt (a, b) ∈ R schreibt man manchmal auch aRb und sagt a steht zu b in der Relation R. Für M = N sagt man auch, dass R eine Relation auf M ist. 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 11 R⊆M ×N a (a, b) aRb ¬cRd (c, d) c d b 4 Bemerkung/Beispiel 1.4.5. (i) Eine Relation gibt eine Beziehung zwischen Ele- menten an. Für jedes a ∈ M und b ∈ N kann diese Beziehung entweder gelten, oder auch nicht. Die Relation R als Menge enthält genau die Paare (a, b), für die a zu b in Relation steht. (ii) Für M = {Gabi, Monika, Erika} und N = {Klaus, Martin, Horst} ist etwa eine Relation gegeben durch R1 := {(Gabi, Martin), (Monika, Horst), (Erika, Klaus)}. Eine andere Möglichkeit wäre aber zum Beispiel R2 = {(Gabi, Martin), (Monika, Martin), (Erika, Klaus), (Erika, Horst)}. Ohne das als gesellschaftspolitisches Statement zu verstehen, könnte in diesem Setup Monika beispielsweise nicht zu Erika in Relation stehen, denn Erika ist kein Element von N. (iii) Mathematisch etwas relevanter ist die folgende Relation auf R: ≤:= (a, b) ∈ R × R | ∃c ∈ R : a + c2 = b.  Hier steht also a in Relation zu b genau dann wenn a kleiner gleich b ist. Hier kennen wir die alternative Notation a ≤ b statt (a, b) ∈ ≤ schon lange. 4 Relationen können gewisse zusätzliche Eigenschaften haben, die von Bedeutung sind. Definition 1.4.6. (i) Sei M eine Menge. Eine Relation R ⊆ M × M auf M heißt reflexiv, falls ∀a ∈ M : (a, a) ∈ R, symmetrisch, falls ∀a, b ∈ M : (a, b) ∈ R ⇒ (b, a) ∈ R, antisymmetrisch, falls ∀a, b ∈ M : (a, b) ∈ R ∧ (b, a) ∈ R ⇒ a = b, transitiv, falls ∀a, b, c ∈ M : (a, b) ∈ R ∧ (b, c) ∈ R ⇒ (a, c) ∈ R vollständig, falls ∀a, b ∈ M : (a, b) ∈ R ∨ (b, a) ∈ R. 12 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN (ii) Eine Äquivalenzrelation auf M ist eine reflexive, symmetrische und transitive Relation auf M. (iii) Eine partielle Ordnung auf M ist eine reflexive, antisymmetrische und tran- sitive Relation auf M. Die partielle Ordnung heißt vollständige/totale Ordnung, falls sie vollständig ist. 4 Bemerkung/Beispiel 1.4.7. (i) Die in Beispiel 1.4.5 (iii) angegebene Relation ≤ ist eine vollständige Ordnung auf R. (ii) Auf N definieren wir folgende Relation (Teilbarkeit): T = {(a, b) ∈ N × N | ∃c ∈ N : a · c = b}. Für (a, b) ∈ T schreibt man oft auch a | b und sagt a teilt b. Dann sieht man leicht, dass T eine partielle, aber keine total Ordnung auf N ist. (iii) Auf jeder Menge M ist {(a, a) | a ∈ M } eine Äquivalenzrelation. Jedes Element steht nur zu sich selbst in Relation. Die Relation gibt also gerade die Gleichheit wieder. (iv) Auf der Menge aller Personen im Raum definiert man folgende Relation: H = {(a, b) | a und b haben dieselbe Haarfarbe}. Dann ist H eine Äquivalenzrelation. (v) Äquivalenzrelationen erlauben es also, einen verallgemeinerten Gleichheits- begriff zu definieren. Es ist dabei nicht nur jedes Element zu sich selbst gleich, sondern kann im verallgemeinerten Sinne auch zu anderen Elementen gleich (äqui- valent) sein. Die Eigenschaften reflexiv/symmetrisch/transitiv sind natürlich Ei- genschaften, die man von einer verallgemeinerten Gleichheit erwarten würde. (vi) Für Äquivalenzrelationen verwendet man häufig auch die Bezeichnung ∼. Statt (a, b) ∈ R oder aRb schreibt man also a ∼ b (oder etwas genauer a ∼R b). 4 Definition 1.4.8. Sei R eine Äquivalenzrelation auf der Menge M. Für a ∈ M definieren wir [a] := {b ∈ M | (a, b) ∈ R} , und nennen es die Äquivalenzklasse von a bezüglich R. Es gilt also stets a ∈ [a] ⊆ M. 4 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 13 Lemma 1.4.9 (F). (i) Sei R eine Äquivalenzrelation auf M. Für a, b ∈ M gilt dann stets [a] = [b] oder [a] ∩ [b] = ∅. Die Äquivalenzklassen liefern also eine Zerlegung von M in paarweise disjunkte Teilmen- gen. (ii) Sei I eine beliebige Indexmenge und für jedes i ∈ I sei Mi ⊆ M eine Teilmenge. Es gelte [ Mi ∩ Mj = ∅ für i 6= j sowie M = Mi. i∈I Dann liefert folgende Setzung eine Äquivalenzrelation auf M , deren Äquivalenzklassen ge- rade die Mengen Mi sind: R := {(a, b) ∈ M × M | ∃i ∈ I : a, b ∈ Mi }. Beweis. (i) Angenommen es gilt [a] ∩ [b] 6= ∅. Wir zeigen, dass dann [a] = [b] gelten muss. Es gibt nun also c ∈ M mit c ∈ [a] und c ∈ [b]. Aus der Definition von Äqui- valenzklassen folgt (a, c) ∈ R und (b, c) ∈ R. Die Symmetrie von R impliziert (c, b) ∈ R und aus der Transitivität folgt damit (a, b) ∈ R. Sei nun d ∈ [a] beliebig. Aus (a, d) ∈ R folgt (d, a) ∈ R und mit (a, b) ∈ R dann wieder aus der Transitivität (d, b) ∈ R. Die Symmetrie impliziert (b, d) ∈ R, also d ∈ [b]. Wir haben gezeigt dass jedes Element aus [a] auch zu [b] gehört, also [a] ⊆ [b]. Die Inklusion [b] ⊆ [a] zeigt man genauso (da die Voraussetzung [a] ∩ [b] = ∅ aber völlig symmetrisch bezüglich a und b ist, muss eigentlich nichts mehr gezeigt werden). Damit gilt [a] = [b]. Wegen a ∈ [a] für jedes a ∈ M liefern die Äquivalenzklassen also eine disjunkte Zerlegung von ganz M. (ii) Die Relation R ist nach Konstruktion offensichtlich reflexiv und symmetrisch. Für die Transitivität gelte (a, b) ∈ R und (b, c) ∈ R. Es gibt also i, j ∈ I mit a, b ∈ Mi und b, c ∈ Mj. Aus i 6= j würde Mi ∩ Mj = ∅ folgen, was wegen b ∈ Mi ∩Mj nicht sein kann. Also gilt i = j, und somit a, c ∈ Mi , also (a, c) ∈ R. Damit ist gezeigt, dass R eine Äquivalenzrelation ist. Wegen b ∈ [a] ⇔ (a, b) ∈ R ⇔ ∃i ∈ I : a, b ∈ Mi folgt für a ∈ Mi schon [a] = Mi. Die Mengen Mi sind also gerade die Äquiva- lenzklassen von R. 14 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Definition 1.4.10. Für eine Äquivalenzrelation R auf M nennen wir die Menge der Äquivalenzklassen auch Faktormenge: M/R := {[a] | a ∈ M }. 4 Bemerkung/Beispiel 1.4.11. (i) Die Äquivalenzklasse [a] enthält alle zu a äquiva- lenten Elemente. Es ist also die Zusammenfassung aller Elemente, die im verall- gemeinerten Sinn als gleich wie a anzusehen sind. Für jedes b ∈ [a] gilt [a] = [b]. Sowohl a als auch b sind also Vertreter der gleichen Äquivalenzklasse. (ii) In Beispiel 1.4.7 (iv) enthält eine Äquivalenzklasse gerade alle Personen mit gleicher Haarfarbe. (iii) Die Menge M/R hat Teilmengen von M als Elemente, nämlich die Äquiva- lenzklassen. Da verschiedene Elemente von M in der selben Äquivalenzklasse lie- gen können, enthält M/R potenziell weniger Elemente als M. Wenn in Beispiel 1.4.7 der Raum 100 Personen enthält, die insgesamt 5 verschiedene Haarfarben haben, ist M eine Menge mit 100 und M/R eine Menge mit 5 Elementen. Heidi blond Erika braun rot Menge M mit Äquivalenzrelation Horst Harry schwarz Tim kahl {[Heidi], [Erika], [Horst], [Harry], [Tim]} Faktormenge M/R 4 Konstruktion 1.4.12 (F). Wenn wir Z mit den Rechenregeln als bekannt voraus- setzen, können wir nun eine exakte Definition von Q geben. Dazu definieren wir zunächst eine Äquivalenzrelation auf der Menge Z × (Z \ {0}): (a, b) ∼ (c, d) :⇔ ad = bc. Man muss nun zunächst nachrechnen, dass es sich hier wirklich um eine Äquiva- lenzrelation handelt. Ist dies erledigt, definieren wir Q einfach als Faktormenge dieser Äquivalenzrelation: Q := (Z × (Z \ {0})) / ∼. 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 15 Für die Äquivalenzklasse von (a, b) schreibt man statt [(a, b)] hier gewöhnlich ab , was zur bekannte Notation na o Q= | a, b ∈ Z, b 6= 0 b führt. Es gilt beispielsweise (1, 2) ∼ (2, 4), denn 1 · 4 = 2 · 2. Daraus folgt [(1, 2)] = [(2, 4)], oder in anderer Schreibweise gerade 1 2 =. 2 4 Nun versieht man Q gewöhnlich mit Addition und Multiplikation, die folgender- maßen definiert wird: a c ad + bc + := b d bd a c ac · :=. b d bd Hier taucht ein wichtiges Phänomen auf, nämlich das der Wohldefiniertheit. Wir definieren hier Addition und Multiplikation von Äquivalenzklassen, also streng genommen von Teilmengen von Z × (Z \ {0}). Auf der rechten Seite der Defini- tion wird aber Bezug auf einen Vertreter der Äquivalenzklasse Bezug genommen, also auf ein Element der jeweiligen Menge. Dieser Vertreter ist aber keineswegs eindeutig. Theoretisch könnte das zu Problem führen. Zum Beispiel erhalten wir mit der oberen Formel 1 3 3 · =. 2 5 10 Wir hätten aber statt 2 auch 4 schreiben können, und erhielten dann 1 2 2 3 6 · =. 4 5 20 Formal betrachtet haben wir im ersten Fall für die Äquivalenzklasse 21 den Ver- treter (1, 2) in der Formel verwendet und im zweiten Fall den Vertreter (2, 4). Er- freulicherweise gilt nun aber 3 6 = , 10 20 wie man direkt sieht, d.h. die Elemente (3, 10) und (6, 20) liegen in der selben Äquivalenzklasse. Das kann (und muss) man nun noch ganz Allgemein für + und · auf Q beweisen. 4 16 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Definition 1.4.13. Seien M, N Mengen. Eine Funktion/Abbildung f von M nach N ist eine linkstotale und rechtseindeutige Relation zwischen M und N , d.h. eine Teilmenge f ⊆ M × N mit folgender zusätzlicher Eigenschaft: ∀a ∈ M ∃!b ∈ N : (a, b) ∈ f. Dabei heißt M Definitionsbereich und N Zielbereich der Funktion. 4 Bemerkung 1.4.14. (i) Die definierende Eigenschaft einer Funktion besagt gera- de, dass für jedes Element a aus dem Definitionsbereich M genau ein Element b aus dem Zielbereich N existiert, welches zu a in Relation steht (also immer min- destens eins, aber auch nie mehr als eins). Aufgrund der Eindeutigkeit von b kann man eine Funktion also auch als Zuordnungsvorschrift verstehen, die jedem a ∈ M ein b ∈ N zuordnet. (ii) Statt f ⊆ M × N schreibt man für Funktionen meistens f : M → N , und statt (a, b) ∈ f auch b = f (a). Man nennt dann b auch das Bild von a unter f. f: M →N f (a) a (iii) Wenn man die Notation f : M → N wählt, nennt man die Darstellung f ⊆ M × N manchmal auch Graph von f. In strengen Sinn der Definition ist eine Funktion aber nichts anderes als ihr Graph. (iv) Für T ⊆ M nennt man die Menge f (T ) := {f (a) | a ∈ T } das Bild von T unter f , und die Menge Bild(f ) := f (M ) das Bild von f. 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 17 (v) Für S ⊆ N nennt man f −1 (S) := {a ∈ M | f (a) ∈ S} das Urbild von S unter f und für b ∈ N f −1 (b) := f −1 ({b}) = {a ∈ M | f (a) = b} das Urbild von b. Man beachte aber, dass dabei f −1 im Allgemeinen nicht als Funktion von N nach M aufgefasst werden kann, denn das Urbild eines Punktes kann mehrere Punkte enthalten. Das widerspräche der Rechtseindeutigkeit. 4 Beispiel 1.4.15. (i) Wir betrachten die Funktion f : {a, b, c, d} → {1, 2, 3} defi- niert durch f (a) = 1, f (b) = 1, f (c) = 2, f (d) = 3. In der formalen Darstellung als Graph erhalten wir f = {(a, 1), (b, 1), (c, 2), (d, 3)} und schematisch können wir f so darstellen: a 1 b 2 c 3 d Es gilt beispielsweise f ({a, c}) = {1, 2}, f −1 ({1, 3}) = {a, b, d}, f −1 (3) = {d}, f −1 (1) = {a, b}. (ii) Auf jeder Menge M gibt es die Identitätsfunktion: idM : M → M a 7→ a. (iii) Die Funktion f = {(a, a2 ) ∈ R × R | a ∈ R} würde man gewöhnlich so an- geben: f: R→R a 7→ a2. Ihr Graph hat dann folgende Gestalt: 18 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN R f R Es gilt Bild(f ) = R≥0 = f (R≥0 ) und f −1 (4) = {−2, 2}. 4 Definition 1.4.16. Sei f : M → N eine Abbildung. Dann heißt f (i) injektiv, falls jedes Element im Zielbereich höchstens ein Urbild hat: ∀b ∈ N : #f −1 (b) ≤ 1. (ii) surjektiv, falls jedes Element im Zielbereich mindestens ein Urbild hat: ∀b ∈ N : #f −1 (b) ≥ 1. (iii) bijektiv, falls f injektiv und surjektiv ist: ∀b ∈ N : #f −1 (b) = 1. 4 Bemerkung/Beispiel 1.4.17. (i) Die Injektivität von f kann man auch folgender- maßen ausdrücken: ∀a, b ∈ M : a 6= b ⇒ f (a) 6= f (b). Zwei verschiedene Elemente des Definitionsbereichs werden also stets auf ver- schiedene Elemente im Zielbereich abgebildet. In der schematischen Darstellung von oben bedeutet das, dass niemals zwei verschiedene Pfeile am selben Punkt enden. Man beachte, dass sich diese Eigenschaft von der Rechtseindeutigkeit (in der Funktionsdefinition) unterscheidet; diese besagt gerade, dass von jedem Ele- ment im Definitionsbereich genau ein Pfeil ausgeht. injektiv 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 19 nicht injektiv Wenn man die Injektivität einer Abbildung andeuten möchte, verwendet man manchmal folgende Notation: f : M ,→ N. (ii) Die Surjektivität besagt, dass jedes Element im Zielbereich von einem Pfeil getroffen wird, oder auch Bild(f ) = N : surjektiv nicht surjektiv Um die Surjektivität anzudeuten, schreibt man manchmal f : M  N. Die Surjektivität einer Abbildung kann man notfalls dadurch erzwingen, dass man den Zielbereich N durch das Bild Bild(f ) der Abbildung ersetzt: f : M  Bild(f ). 20 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN (iii) Injektivität und Surjektivität sind voneinander unabhängig Bedingungen. Keine der beiden impliziert die andere oder schließt sie aus. (iv) Die Bijektivität besagt, dass jedes Element im Zielbereich genau ein Urbild besitzt. Damit stellt f eine eins-zu-eins Zuordnung zwischen den Elementen von M und N her: bijektiv In dieser Situation kann man offensichtlich f −1 als Abbildung von N nach M auf- fassen: f −1 := {(b, a) ∈ N × M | f (a) = b} und man nennt f −1 dann Umkehrabbildung von f. (v) Eine injektive Abbildung f : M → N wird bijektiv, wenn N durch Bild(f ) ersetzt wird. In diesem Sinne existiert also für jede injektive Abbildung die Um- kehrabbildung f −1 : Bild(f ) → M. (vi) Die Identitätsfunktion idM : M → M ist stets bijektiv. Es gibt aber im All- gemeinen noch weitere bijektive Funktionen von M nach M. Beispiele sind Dre- hungen und Spiegelungen des R2. 4 Beispiel 1.4.18. Wir betrachten die Funktion f: R→R a 7→ a2. R f R 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 21 Es gilt f (−1) = 1 = f (1), also ist f nicht injektiv. Es gilt −1 ∈ / R≥0 = Bild(f ), also ist f auch nicht surjektiv. Wir ersetzen nun den Zielbereich durch R≥0 : g : R → R≥0 a 7→ a2. R≥0 g R Die Abbildung g ist nun surjektiv, aber wegen g(−1) = 1 = g(1) immer noch nicht injektiv. Wenn wir nun auch noch den Definitionsbereich zu R≥0 verklei- nern, erhalten wir eine injektive und surjektive Abbildung, also eine Bijektion: h : R≥0 → R≥0 a 7→ a2. R≥0 h R≥0 Die Umkehrfunktion von h nennt man Wurzelfunktion: h−1 : R≥0 → R≥0 √ a 7→ a. R≥0 h−1 R≥0 4 22 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Definition 1.4.19. Seien f : M → N und g : N → O Funktionen. Dann ist die Hintereinanderausführung von f und g definiert als g◦f: M →O a 7→ g (f (a)). Dabei liest man das Symbol ◦ als nach, was auch die Reihenfolge g ◦ f erklärt. f g M / N /8 O g◦f f g g◦f 4 Bemerkung/Beispiel 1.4.20. (i) Sei f : {a, b, c} → {1, 2} definiert durch f (a) = 1, f (b) = 2, f (c) = 1 und g : {1, 2} → {Klaus, Bello, Patscherkofel} definiert durch g(1) = Patscherkofel, g(2) = Bello, so erhalten wir für g ◦ f : {a, b, c} → {Klaus, Bello, Patscherkofel} (g ◦ f )(a) = Patscherkofel, (g ◦ f )(b) = Bello, (g ◦ f )(c) = Patscherkofel. (ii) Für f : M → N gilt stets f ◦ idM = f, idN ◦f = f. (iii) Ist f : M → N bijektiv und f −1 : N → M die Umkehrabbildung, so gilt f −1 ◦ f = idM , f ◦ f −1 = idN. 1.4. MENGEN, RELATIONEN UND ABBILDUNGEN 23 (iv) Die Hintereinanderausführung von Abbildungen erfüllt das Assoziativgesetz, d.h. es gilt h ◦ (g ◦ f ) = (h ◦ g) ◦ f für Abbildungen f : M → N, g : N → O, h : O → P. (v) Die Hintereinanderausführung von Abbildungen ist im Allgemeinen nicht kom- mutativ! Es gibt also Abbildungen f : M → M, g : M → M mit g ◦ f 6= f ◦ g. Beispielsweise kann man das mit einer Drehung und einer Achsenspiegelung des R2 anschaulich leicht sehen. 4 24 KAPITEL 1. EINLEITUNG UND GRUNDLAGEN Kapitel 2 Gauß-Algorithmus und Matrixrechnung In diesem Abschnitt lernen wir zunächst den Gauß-Algorithmus über R kennen. Mit ihm kann man lineare Gleichungssysteme algorithmisch vollständig lösen. Wir sehen dann, dass man statt R beispielsweise auch Q verwenden kann und das führt uns zur allgemeinen Definition eines Körpers. Das sind gerade die Zahl- bereiche, über denen der Gauß-Algorithmus wie über R funktioniert. Wir lernen einige Beispiele dazu kennen, allen voran die komplexen Zahlen. Danach beschäf- tigen wir uns mit Matrixrechnung, die viel notationelle Vereinfachung und ein tieferes Verständnis des Gauß-Algorithmus liefert. 2.1 Der Gauß-Algorithmus In diesem Abschnitt arbeiten wir ausschließlich mit R, alle auftretenden Zahlen sollen also reell sein. In den meisten Anwendungen in Physik, Technik etc. wird auch mit den reellen Zahlen gearbeitet. Man sollte dabei nicht vergessen, dass die reellen Zahlen bei weitem kein einfaches oder offensichtliches Konstrukt sind. Mathematisch exakt wurden sie sogar erst gegen Ende des 19. Jahrhunderts ge- fasst. Für eine saubere Einführung in die reellen Zahlen verweisen wir auf die Analysis-Vorlesungen. Beispiel 2.1.1. Aus der Schule bekannt sind meistens Systeme von linearen Glei- 25 26 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG chungen in zwei oder drei Variablen. Ein solches System ist beispielsweise 2x + y = 10 x+y = 6 Um das System zu lösen, möchte man alle (reellen) Werte für x und y bestim- men, die bei gemeinsamer Einsetzung in beide Gleichungen wahre Aussagen er- geben. Dies erreicht man gewöhnlich durch Äquivalenzumformungen, also Umfor- mungen des Gleichungssystems, welche die Lösungsmenge nicht verändern. Am Ende sollte dabei die Lösungsmenge einfach abzulesen sein. Bei einfachen Sy- stem kann man beispielsweise die Strategie des Auflösens und Einsetzens ver- wenden. Die zweite Gleichung ist offensichtlich äquivalent zu y = 6 − x. Setzt man das ins erste System ein, erhält man 2x + (6 − x) = 10, also x + 6 = 10. Hier liest man die einzige Lösung x = 4 direkt ab, und erhält y = 6 − 4 = 2. Das System hat also die einelementige Lösungsmenge L = {(4, 2)}. 4 Die Strategie des Auflösens und Einsetzens wird schnell unpraktikabel, wenn die Anzahl der Variablen und Gleichungen wächst. Bei 10 Gleichungen in 15 Varia- blen möchte eigentlich niemand mehr diese Rechnung durchführen. Wir gehen nun also etwas systematischer vor. Definition 2.1.2. (i) Ein lineares Gleichungssystem ist ein Ausdruck der folgen- den Form: a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 (2.1)...... am1 x1 + am2 x2 + · · · + amn xn = bm Dabei sind aij und bi vorgegebene Koeffizienten (hier aus R) des Gleichungssy- stems. Die x1 ,... , xn sind Variablen. 2.1. DER GAUSS-ALGORITHMUS 27 (ii) Das lineare Gleichungssystem (2.1) heißt homogen, falls b1 = b 2 = · · · = bm = 0 gilt. Ansonsten heißt es inhomogen. (iii) Die Koeffizientenmatrix des Gleichungssystems (2.1) ist folgendes rechtecki- ges Schema:   a11 · · · a1n A = .....  ,.   am1 · · · amn die erweiterte Koeffizientenmatrix ist   a11 · · · a1n b1 ...... . (A, b) = ...  am1 · · · amn bm (iv) Die Lösungsmenge des Systems (2.1) ist L(A, b) := {(c1 ,... , cn ) ∈ Rn | rechts und links in (2.1) steht in jeder Gleichung dieselbe Zahl, wenn jedes xi durch ci ersetzt wird}. 4 Die Strategie des Algorithmus von Gauß ist nun, das Gleichungssystem (bzw. ei- gentlich nur seine erweiterte Koeffizientenmatrix) so umzuformen, dass sich ei- nerseits die Lösungsmenge nicht ändert und andererseits die Lösungsmenge des neuen Systems leicht abzulesen ist. Leicht abzulesen ist die Lösungsmenge bei Koeffizientenmatrizen in Zeilenstufenform: Definition 2.1.3. Eine m × n-Matrix A ist in Zeilenstufenform, falls sie folgende Gestalt hat:   ~   ~    ~  A=.. .   .     0 ~  Dabei müssen alle Einträge ~ ungleich Null sein und unterhalb der Stufenlinien darf überall nur Null stehen. Die Einträge ~ nennt man Pivots. In exakterer (aber unverständlicherer) Ausdrucksweise besagt das: 28 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG (i) Es gibt ein 0 ≤ r ≤ m, so dass alle Zeilen mit Index r + 1 bis m nur Nullen enthalten. (ii) In jeder Zeile mit Index 1 ≤ i ≤ r gibt es einen Eintrag 6= 0. Wenn ji der kleinste Spaltenindex ist, für den der Eintrag in der i-ten Zeile 6= 0 ist, so gilt j1 < j2 < · · · < jr. 4 Bemerkung 2.1.4. Hat die Koeffizientenmatrix A eines linearen Gleichungssy- stems Zeilenstufenform, kann man die Lösungsmenge des Systems direkt able- sen. Die erweiterte Koeffizientenmatrix sieht dann so aus: ~ b1    ~ b2     ~ b 3  ..... .    .  ~ br    0 br+1     ..  .  bm Indem man das in Gedanken wieder in ein klassisches Gleichungssystem über- setzt, sieht man direkt: (i) Das System hat genau dann eine Lösung, wenn br+1 = · · · = bm = 0 gilt. (ii) Ist das System lösbar, erhält man alle Lösungen auf folgende Weise: Falls in der i-ten Spalte von A kein Pivot steht, kann für xi eine beliebige Zahl eingesetzt werden. Solche Variablen nennt man freie Variablen. Die Werte für alle anderen Variablen sind dann eindeutig bestimmt (diese Variablen nennt man gebunden). Man erhält sie, indem man von unten, beginnend mit der r-ten Zeile, die entsprechenden Gleichungen nach der Variable am Pivot auflöst. Durch diese Prozedur erhält man eine Parametrisierung der gesamten Lösungs- menge durch Rn−r , d.h. eine bijektive Abbildung ϕ : Rn−r → L(A, b). 2.1. DER GAUSS-ALGORITHMUS 29 Dabei entspricht ein Tupel d ∈ Rn−r einer Wahl von Werten für die freien Varia- blen (davon gibt es n − r viele). Das Tupel ϕ(d) ist dann die eindeutig bestimmte Fortsetzung zu einer Lösung des Systems. 4 Beispiel 2.1.5. Wir betrachten folgende erweiterte Koeffizientenmatrix, in der A Zeilenstufenform hat:  1 3  2 2 − 4 0 9  0 0 2 1 −4/3  (A, b) =   . 0 0 0 −1 2  0 0 0 0 0 Hier ist m = n = 4 und r = 3. Wegen b4 = 0 ist das System lösbar. Die einzige freie Variable ist x2. Wenn wir für x2 also den Wert d ∈ R wählen, ergibt sich aus der dritten Zeile der einzig mögliche Wert −2 für x4 , damit aus der zweiten Zeile 1 3 für x3 und schließlich aus der erste Zeile 37 2 − 4d für x1. Dadurch ergibt sich folgende Parametrisierung der Lösungsmenge: ϕ : R → L(A, b) 37 − 4d, d, 13 , −2.
d 7→ 2 Die Lösungsmenge kann auch einfach als L(A, b) = 37 1 
2 − 4d, d, 3 , −2 |d∈R angegeben werden. 4 Im Gauß-Algorithmus formen wir ein Gleichungssystem so lange um, bis es Zei- lenstufenform hat. Wir geben die nötigen Definitionen nun in der Sprache der (erweiterte) Koeffizientenmatrix an. Definition 2.1.6. Eine elementare Zeilenumformung einer Matrix ist eine der drei folgenden Operationen: (I) Vertauschung von zwei Zeilen. (II) Multiplikation (jedes Eintrags) einer Zeile mit einer Zahl 6= 0. (III) Addition eines Vielfachen (6= 0) einer Zeile zu einer (echt) anderen (ein- tragsweise). 4 30 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Der folgende Satz beinhaltet die wichtigsten Aussagen zum Gauß-Algorithmus. Der eigentliche Algorithmus wird im Beweis von Teil (ii) beschrieben. Satz 2.1.7 (Algorithmus von Gauß). Sei (A, b) die erweiterte Koeffizientenmatrix eines linearen Gleichungssystems. (i) Entsteht (A0 , b0 ) durch eine endliche Abfolge von elementaren Zeilenumformungen aus (A, b), so gilt L(A0 , b0 ) = L(A, b). (ii) (A, b) lässt sich durch eine endliche Abfolge von elementaren Zeilenumformungen auf eine Gestalt (A0 , b0 ) bringen, in der A0 Zeilenstufenform hat. Beweis. (i): Das Vertauschen zweier Zeilen entspricht dem Vertauschen zweier Gleichungen, was die Lösungsmenge offensichtlich nicht ändert. Das Multiplizieren der i-ten Zeile mit λ 6= 0 entspricht dem Multiplizieren aller Koeffizienten der i-ten Gleichung (einschließlich dem bi ) mit λ. Ist c = (c1 ,... , cn ) eine Lösung der ursprünglichen Gleichung, so gilt ai1 c1 + · · · + ain cn = bi. Daraus folgt (λai1 )c1 + · · · + (λain )cn = λ(ai1 c1 + · · · + ain cn ) = λbi , als ist c auch eine Lösung des neuen Systems, die Lösungsmenge wird also höch- stens größer. Da diese Umformung durch eine Umformung desselben Typs (Mul- tiplikation mit λ−1 ) wieder rückgängig gemacht werden kann und das System da- bei abermals höchstens größer wird, ist es stets gleich geblieben. Wir addieren nun das λ-fache der i-ten Zeile zur j-ten. Sei c = (c1 ,... , cn ) eine Lösung des ursprünglichen Systems, insbesondere gelte also ai1 c1 + · · · + ain cn = bi aj1 c1 + · · · + ajn cn = bj. Daraus folgt λbi + bj = λ (ai1 c1 + · · · + ain cn ) + (aj1 c1 + · · · + ajn cn ) = (λai1 + aj1 )c1 + · · · + (λain + ajn )cn. 2.1. DER GAUSS-ALGORITHMUS 31 Also löst c auch die neu entstandene Gleichung im neuen System. Also ist die Lö- sungsmenge auch in diesem Schritt höchstens größer geworden. Auch diese Um- formung lässt sich durch eine vom selben Typ invertieren, nämlich durch Addi- tion des (−λ)-fachen der i-ten Zeile zur j-ten. Also bleiben die Lösungsmengen stets gleich und wir haben (i) bewiesen. (ii): Die Nullmatrix hat bereits Zeilenstufenform, also können wir annehmen, dass A mindestens einen Eintrag 6= 0 hat. Wir wählen nun eine Zeile, in der ein Eintrag 6= 0 in A mit kleinstem Spaltenindex j1 auftritt. Wir vertauschen die erste Zeile von (A, b) dann mit dieser Zeile (Umformung vom Typ (I)). In allen Spalten von kleinerem Index als j1 steht nun also nur Null und an der Stelle (1, j1 ) steht ein Eintrag 6= 0. Damit können wir mit Umformungen vom Typ (III) alle Einträge unterhalb des (1, j1 )-Eintrags ebenfalls eliminieren. Nun ignorieren wir die erste Zeile und die ersten j1 Spalten der Matrix und iterie- ren den Prozess mit der übrigen (kleineren) Matrix. Man beachte, dass die erste Zeile und die ersten j1 Spalten der Matrix durch die folgenden Umformungen nicht mehr verändert werden. Nach endlich vielen Schritten erreichen wir also Zeilenstufenform. Bemerkung 2.1.8. (i) Der Gauß-Algorithmus und Bemerkung 2.1.4 ermöglichen es nun, für lineare Gleichungssysteme sämliche Lösungen zu bestimmen. Wir bringen die erweiterte Koeffizientenmatrix mit elementaren Zeilenumformun- gen auf Zeilenstufenform und lesen die Lösungen danach ab. (ii) Am Beweis von (ii) in Satz 2.1.7 sehen wir, dass Umformungen von Typ (I) und (III) schon ausreichen, um Zeilenstufenform zu bekommen. Typ (II) benötigt man nur, wenn man alle Pivots auf 1 setzen möchte. (iii) Man kann offensichtlich auch noch erreichen, dass alle Einträge oberhalb der Pivots 0 sind. Sie können einfach mit Umformungen vom Typ (III), von links mit den Pivots beginnend, eliminiert werden. Diese Form macht das Ablesen der Lösungen (wie im Bemerkung 2.1.4 beschrieben) nochmal einfacher. Man kann in jeder Gleichung direkt den Wert für (die einzige) gebundene Variable aus den Werten für die freien Variablen bestimmen, ohne iterativ von unten diese Werte auszurechnen. Sind zusätzlich die Pivots alle 1, muss dabei nicht einmal eine Di- vision durchgeführt werden. Eine Zeilenstufenform mit Pivots = 1 und Nullen oberhalb der Pivots heißt reduzierte Zeilenstufenform. (iv) Wichtig beim Gauß-Algorithmus ist es, immer die erweiterte Koeffizienten- matrix umzuformen. Ansonsten ändert sich die Lösungsmenge natürlich offen- sichtlich. Nur bei homogenen Systemen ist das nicht nötig, da sich die Nullspalte ganz hinten sowieso niemals ändert, wenn Zeilenumformungen vorgenommen 32 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG werden. (v) Spaltenumformungen sind im Gauß-Algorithmus nicht ohne Probleme er- laubt. Vertauscht man etwa zwei Spalten, so ändert sich die Lösungsmenge, wenn auch nicht besonders dramatisch. Es müssen in der Lösung des neuen Systems zwei entsprechende Koordinaten vertauscht werden, um die Lösungsmenge des alten Systems zu erhalten. Um solche Komplikationen zu vermeiden, beschränkt man sich am besten ausschließlich auf Zeilentransformationen. 4 Beispiel 2.1.9. Wir berechnen eine Zeilenstufenform:     1 2 3 4 −1 1 2 3 4 −1 Z2 −5Z1 (A, b) =  5 6 7 8 −2   0 −4 −8 −12 3  9 10 11 12 −3 9 10 11 12 −3   1 2 3 4 −1 Z3 −9Z1  0 −4 −8 −12 3  0 −8 −16 −24 6   1 2 3 4 −1 Z3 −2Z2  0 −4 −8 −12 3 . 0 0 0 0 0 Hier sehen wir, dass das zugehörige Gleichungssystem eine Lösung besitzt. Die freien Variablen sind x3 und x4. Setzt man a ∈ R für x3 und b ∈ R für x4 ein, erhalten wir aus der zweiten Gleichung den einzig möglichen Wert − 34 − 2a − 3b für x2. Damit ergibt sich mit der ersten Gleichung für x1 der Wert 12 + a + 2b. Insgesamt erhalten wir L(A, b) = 12 + a + 2b, − 34 − 2a − 3b, a, b | a, b ∈ R. 
Wir berechnen auch noch die reduzierte Zeilenstufenform:     1 2 3 4 −1 1 − ·Z2 1 2 3 4 −1  0 −4 −8 −12 3  4  0 1 2 3 − 3  4 0 0 0 0 0 0 0 0 0 0 1 0 −1 −2 12   Z1 −2Z2  0 1 2 3 − 43  0 0 0 0 0 Hier findet man die oben angegebene Beschreibung der Lösungsmenge noch ein- facher. 4 2.2. GRUPPEN, RINGE UND KÖRPER 33 2.2 Gruppen, Ringe und Körper Wir schauen uns nun genau an, welche Eigenschaften von R wir im letzten Ab- schnitt eigentlich verwendet haben. Zunächst rechnen wir in R stets mit den beiden Rechenoperationen + und ·. Dabei haben wir, vermutlich ohne es zu bemerken, immer wieder Assoziativ-, Kommutativ- und Distributivgesetz für Addition und Multiplikation verwendet. Im Beweis von Satz 2.1.7 (i) sieht man das beispielsweise sehr schön. Auch bereits in der Defini- tion der elementaren Umformungsschritte war das Kommutativgesetz implizit vorausgesetzt. Ansonsten hätten wir ja z.B. die Reihenfolge bei der Addition an- geben müssen. Aber wir haben noch mehr verwendet. Um die Einträge unterhalb der Pivots zu eliminieren mussten wir verwenden, dass man zu jeder Zahl eine geeignete Zahl addieren kann, um Null zu erhalten. Das folgt aus der Existenz der Subtraktion von Zahlen. Um wirklich mit jedem Pivot jede andere Zahl elimieren zu können, muss man aber auch noch dividieren können. Das sieht man in Beispiel 2.1.9 gut. Weitere Eigenschaften wurden für die Existenz der Zeilenstufenform aber nicht verwendet. Auch die Extraktion der Lösungen (siehe Bemerkung 2.1.4) benötigt diese, aber keine weiteren Eigenschaften. Die rationalen Zahlen Q haben aber diese Eigenschaften ebenfalls. Wir können den Gauß-Algorithmus also genau- so über Q durchführen, vorausgesetzt alle Koeffizienten des Gleichungssystems sind rationale Zahlen. Dann findet man die rationale Lösungsmenge des Systems. Als Mathematiker nimmt man das zum Anlass, gleich alles axiomatisch zu formu- lieren. Das führt zum Begriff des Körpers. 2.2.1 Grundbegriffe Definition 2.2.1. (i) Eine Gruppe ist eine Menge G zusammen mit einer zweistel- ligen Verknüpfung ∗: G × G → G die folgende Bedingungen erfüllt: (Assoziativgesetz) ∀a, b, c (a ∗ b) ∗ c = a ∗ (b ∗ c) (neutrales Element) ∃e ∀a e∗a=a∗e=a (inverse Elemente) ∀a ∃b a ∗ b = b ∗ a = e. (ii) Gilt zusätzlich 34 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG (Kommutativgesetz) ∀a, b a∗b=b∗a so nennt man G eine kommutative oder abelsche Gruppe. 4 Beispiel 2.2.2. (i) Beispiele für abelsche Gruppen sind Z, Q, R mit der bekannten Addition + und e = 0. N ist keine Gruppe bezüglich +, da nicht jedes Element ein inverses Element besitzt. (ii) Q \ {0} und R \ {0} sind abelsche Gruppen bezüglich der bekannten Multipli- kation · mit e = 1. Für Z \ {0} gilt das nicht, da nicht jedes Element ein inverses Element besitzt. (iii) Für n ∈ N sei Z/nZ := {0, 1,... , n − 1} versehen mit der Addition wie auf einer Uhr. Wir addieren also wie gewöhnlich, identifizieren aber n mit 0, n + 1 mit 1 usw... Auf diese Weise erhalten wir eine abelsche Gruppe mit n Elementen. (iv) Für jede nichtleere Menge M bilden die bijektiven Abbildungen von M nach M eine Gruppe S(M ) bezüglich der Hintereinanderausführung ◦ von Funktio- nen. Das neutrale Element ist dabei die identische Abbildung idM. Falls M min- destens 3 Elemente hat, ist S(M ) nicht abelsch. S(M ) wird als Permutations- gruppe oder Symmetriegruppe von M bezeichnet. 4 Bemerkung 2.2.3. (i) Das Assoziativgesetz erlaubt uns, Klammern bei kompli- zierteren Ausdrücken meistens ganz wegzulassen. (ii) Die Definition der inversen Elemente nimmt Bezug auf das neutrale Element e. Das muss also zunächst bekannt sein, es ist eindeutig bestimmt. Falls nämlich e, e0 ∈ G beides neutrale Elemente sind, so gilt e = e ∗ e0 = e0 wobei wir für die erste Gleichung die Neutralität von e0 und für die zweite die Neutralität von e verwendet haben. Auch das inverse Element zu einem festen Element ist eindeutig bestimmt. Seien etwa b, b0 beide invers zu a. Multiplizieren wir nun die Gleichung a ∗ b = e von links mit b0 erhalten wir ∗ a} ∗b = b0 ∗ e = b0 , b|0{z e also b = b0. (iv) In abelschen Gruppen wird die Verknüpfung oft mit + bezeichnet und das neutrale Element mit 0. Das zu a inverse Element wird dann mit −a bezeichnet. 2.2. GRUPPEN, RINGE UND KÖRPER 35 In nicht-abelschen Gruppen verwenden wir oft · und 1 oder ◦ und id für die Ver- knüpfung und das neutrale Element. Das zu a inverse Element wird dann mit a−1 bezeichnet. Oft lassen wir · auch einfach weg, schreiben also ab statt a · b. 4 Definition 2.2.4. (i) Ein Ring ist eine Menge R zusammen mit zwei Verknüpfun- gen +: R × R → R · : R × R → R, genannt Addition und Multiplikation, sodass gilt: R ist bezüglich Addition eine abelsche Gruppe (das neutrale Element be- zeichnen wir mit 0). Die Multiplikation ist assoziativ und besitzt ein neutrales Element (genannt 1). Es gelte stets 1 6= 0. Addition und Multiplikation erfüllen das Distributivgesetz, d.h. für alle a, b, c ∈ R gilt a · (b + c) = (a · b) + (a · c) und (b + c) · a = (b · a) + (c · a). (ii) Der Ring R heißt kommutativ, falls die Multiplikation kommutativ ist. (iii) Die Menge R× := {a ∈ R | ∃b ∈ R : ab = ba = 1} heißt Menge der Einheiten von R. 4 Beispiel 2.2.5. (i) Die einfachsten Beispiele von kommutativen Ringen sind Z, Q, R, jeweils mit der bekannten Addition und Multiplikation. Es gilt Z× = {−1, 1}, Q× = Q \ {0}, R× = R \ {0}. (ii) Sei M eine nichtleere Menge. Dann bildet die Menge F(M, R) aller reellwer- tigen Abbildungen auf M einen kommutativen Ring bezüglich punktweise defi- nierter Addition und Multiplikation: (f + g)(m) := f (m) + g(m) (f · g)(m) := f (m) · g(m). Hier kann statt R auch ein beliebiger anderer Ring R gewählt werden (wobei F(M, R) dann nicht mehr unbedingt kommutativ ist). 4 36 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Bemerkung 2.2.6. (i) Wie in Gruppen sind auch in Ringen die beiden neutralen Elemente 0, 1 eindeutig bestimmt. Die inversen Elemente bezüglich + sind eben- falls eindeutig bestimmt. Für a ∈ R× ist auch das multiplikativ inverse Element eindeutig bestimmt, wir bezeichnen es mit a−1. (ii) In Ringen gelten einige einfache Rechenregeln, wie zum Beispiel 0·a=0 oder −(a · b) = (−a) · b = a · (−b) für alle a, b ∈ R. Obwohl sie nicht zu den Axiomen gehören, kann man sie relativ leicht beweisen. (iii) Um die Anzahl von Klammern zu verringern, vereinbaren wir, dass Multipli- kation stärker bindet als Addition. So schreiben wir etwa a·b+c·d anstelle von (a · b) + (c · d). Wiederum lassen wir · oft einfach weg, schreiben also ab anstelle von a · b. 4 Lemma 2.2.7. Sei R ein Ring. Dann ist R× eine Gruppe bezüglich ·. Beweis. Wir zeigen zunächst, dass R× überhaupt abgeschlossen unter · ist. Seien dazu also a, b ∈ R×. Es existieren also a−1 , b−1 ∈ R und es gilt (ab)(b−1 a−1 ) = a(bb−1 )a−1 = a1a−1 = aa−1 = 1. Genauso zeigt man (b−1 a−1 )(ab) = 1. Also ist ab ebenfalls invertierbar in R, d.h. ab ∈ R×. Die Multiplikation ist nun bereits aufgrund der Ringaxiome assoziativ. Offen- sichtlich gilt außerdem 1 ∈ R× , also besitzt R× ein neutrales Element bezüglich der Multiplikation. Wegen aa−1 = a−1 a = 1 besitzt mit a auch a−1 ein inverses Element, nämlich a. Damit gilt a−1 ∈ R× und a hat also in R× ein inverses Element bezüglich ·. 2.2. GRUPPEN, RINGE UND KÖRPER 37 Bemerkung 2.2.8. Der letzte Beweis zeigt, dass für a, b ∈ R× stets gilt (a−1 )−1 = a sowie (ab)−1 = b−1 a−1. 4 Definition 2.2.9. Ein Körper ist ein kommutativer Ring K mit K × = K \ {0}. 4 Beispiel 2.2.10. Q und R sind Körper. 4 Bemerkung 2.2.11. Wie bereits erwähnt, kann man den Algorithmus von Gauß für lineare Gleichungssysteme mit Koeffizienten aus einem beliebigen Körper durch- führen, genau wie im letzten Abschnitt beschrieben, ohne die Lösungsmenge zu verändern. Man beachte, dass hier (per Definition) L(A, b) ⊆ K n gilt. Es gelten Assoziativ-, Kommutativ- und Distributivgesetz für + und ·. Die Bedingungung K × = K \ {0} und die Existenz von additiv inversen Elementen erlaubt es uns, jeden Pivot so zu skalieren, dass man damit Einträge unterhalb eliminieren kann. Ist der Pivot etwa a 6= 0 und ein Eintrag unterhalb lautet b, so muss man die Pivotzeile mit −ba−1 multiplizieren und nach unten addieren. An der Stelle von b steht dann (−ba−1 ) · a + b = −b · 1 + b = −b + b = 0. Auch das Ablesen der Lösungsmenge funktioniert genau wie in Bemerkung 2.1.4. Man erhält eine Parametrisierung ϕ : K n−r → L(A, b). Über einem Ring lässt sich der Algorithmus jedoch im Allgemeinen nicht durch- führen. Ist ein Pivot über Z beispielsweise 2, so kann man eine etwaige darunter- stehende 1 damit nicht eliminieren (ohne den Zahlbereich Z zu verlassen). 2.2.2 Die komplexen Zahlen F Die komplexen Zahlen C bilden einen Körper, der eine Erweiterung von R ist. Wem das seltsam vorkommt, der rufe sich nochmal in Erinnerung, dass bereits 38 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG die reellen Zahlen ein komplexes theoretisches Gebilde sind, das keineswegs na- türlich gegeben ist. Es entstand aus Q in dem Versuch, gewisse Defizite beim Lösen von Gleichungen zu beheben. Es gibt nun keinen Grund, bei R mit solchen Konstruktionen aufzuhören. Es hat ja auch R noch gewisse Defizite, zum Beispiel besitzt die Gleichung x2 + 1 = 0 dort keine Lösung. Konstruktion 2.2.12. Als Menge sind die komplexen Zahlen einfach die reelle Ebe- ne R2 : C = R × R = {(a, b) | a, b ∈ R}. Wir definieren nun Addition und Multiplikation folgendermaßen: (a, b) + (c, d) = (a + c, b + d) (a, b) · (c, d) = (ac − bd, ad + bc). Es ist also beispielsweise (3, −2) + (2, 1) = (5, −1), (3, −2) · (2, 1) = (8, −1). Die Addition entspricht einfach dem Aneinanderhängen von Pfeilen im R2 : (a, b) + (c, d) (c, d) (a, b) (0, 0) Wir werden später sehen, dass auch die Multiplikation eine geometrische Inter- pretation besitzt. 4 Satz 2.2.13. C bildet mit + und · einen Körper. Dabei ist (0, 0) das additiv neutrale und (1, 0) das multiplikativ neutrale Element. Das additiv inverse Element zu (a, b) ist (−a, −b). Das multiplikativ inverse Element zu z = (a, b) 6= (0, 0) ist   −1 a −b z = ,. a2 + b 2 a2 + b 2 2.2. GRUPPEN, RINGE UND KÖRPER 39 Beweis. Wir rechnen nur einige Aussagen nach, der Rest ist Übungsaufgabe. Zum Beispiel ist (a, b) + (0, 0) = (a + 0, b + 0) = (a, b) und (a, b) · (1, 0) = (a · 1 − b · 0, a · 0 + b · 1) = (a, b). Weiter gilt a2 −b2     a −b −ab ab (a, b) · , 2 = − 2 , 2 + 2 a + b a + b2 2 2 2 a +b 2 2 a +b a +b 2 a + b2  2 a + b2  = , 0 = (1, 0). a2 + b 2 Bemerkung 2.2.14. (i) Wir können R in C einbetten, indem wir a ∈ R mit (a, 0) ∈ C identifizieren. Wir identifizieren R also mit der x-Achse in R2. Die neuen Ver- knüpfungen stimmen dann gerade mit den alten überein: (a, 0) + (b, 0) = (a + b, 0), (a, 0) · (b, 0) = (ab − 0 · 0, a · 0 + b · 0) = (ab, 0). Das additiv neutrale Element ist also gerade die alte 0, das multiplikativ neutrale ist die alte 1. In diesem Sinne können wir ab sofort R⊆C schreiben. Besonders interessant ist nun das Element (0, 1), das nicht zu den re- ellen Zahlen gehört. Wir rechnen (0, 1) · (0, 1) = (0 · 0 − 1 · 1, 0 · 1 + 1 · 0) = (−1, 0)= b − 1 ∈ R. Wir haben also eine Quadratwurzel aus −1 gefunden, die selbst allerdings keine reelle Zahl ist. (ii) Gewöhnlich werden komplexe Zahlen z = (a, b) nicht als Tupel geschrieben, sondern in der Form z = a + bi. Dabei ist i = 0 + 1 · i = (0, 1) und es gilt i2 = −1. Die Zahl a heißt Realteil, und b Imaginärteil von z. Wir schreiben auch Re(z) = a, Im(z) = b. 40 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Im b z = a + bi Re a Die Schreibweise a + bi hat den Vorteil, dass wir Produkte leichter ausrechnen können. Wir müssen uns nicht die Formel merken, sondern dürfen das Distribu- tivgesetz verwenden, und müssen nur i2 = −1 im Kopf behalten: (a, b) · (c, d) = (a + bi) · (c + di) = ac + adi + bci + bdi2 = ac − bd + (ad + bc)i = (ac − bd, ad + bc). In dieser Schreibweise haben wir also a b (a + bi)−1 = − 2 i. 4 a2 +b 2 a + b2 Beispiel 2.2.15. (i) Wir führen einige Beispielrechnungen mit komplexen Zahlen durch: (3 + 2i) + (−5 + i) = −2 + 3i −(5 − 2i) = −5 + 2i (5 − 2i) + (−5 + 2i) = 5 − 5 + (−2 + 2)i = 0 + 0i = 0 (1 + i) · (1 − i) = 1 − i + i − i2 = 1 + 1 = 2 1 1 (1 + i)−1 = − i 2 2   1 1 1 1 1 1 1 1 (1 + i) · − i = − i + i − i2 = + = 1. 2 2 2 2 2 2 2 2 (ii) Wir lösen nun die Gleichung (1 + i) · z = i 2.2. GRUPPEN, RINGE UND KÖRPER 41 in C. Dazu multiplizieren wir mit dem Inversen von 1 + i auf beiden Seiten. Das Inverse ist 21 − 12 i, wie wir im letzten Beispiel gesehen haben. Es ergibt sich   1 1 1 1 1 1 z= − i · i = i − i2 = + i 2 2 2 2 2 2 als Lösung. (iii) Wir wollen die Gleichung z 2 = −5 √ lösen. Wir wissen schon, dass i2 = −1 gilt. Damit folgt mit z = 5i √ 2 z 2 = 5 i2 = −5. 4 Auf den komplexen Zahlen gibt es weitere nützliche Operationen: Definition 2.2.16. (i) Für eine komplexe Zahl z = a + bi = (a, b) heißt z = a − bi = (a, −b) die komplex konjugierte Zahl. Sie entsteht gerade durch Multiplikation des Ima- ginärteils mit −1. Geometrisch handelt es sich dabei um Spiegelung an der x- Achse. (ii) Für z = a + bi ∈ C definieren wir den Betrag als √ |z| = a2 + b2. Man beachte, dass a2 + b2 eine positive reelle Zahl ist, aus der wir eine positive reelle Quadratwurzel ziehen können. Der Betrag |z| ist gerade die Länge von z als Vektor in R2 , wie man mit dem Satz des Pythagoras sieht. Auch stimmt der Betrag |a| für reelle Zahlen genau mit dem alten Betrag überein, d.h. |a| = a falls a ≥ 0 und |a| = −a falls a < 0. Im 2 √ a2 + b z = a + bi Re z = a − bi 4 42 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Satz 2.2.17. Für komplexe Zahlen z, z1 , z2 gilt: (i) z1 + z2 = z1 + z2 und z1 · z2 = z1 · z2 (ii) z −1 = (z)−1 (iii) Re(z) = 12 (z + z) und Im(z) = − 21 i (z − z). (iv) |Re(z)| ≤ |z| und |Im(z)| ≤ |z| (v) |z| = |z|. (vi) z · z = |z|2 , also 1 z −1 = z |z|2 für z 6= 0. (vii) |z1 · z2 | = |z1 | · |z2 | (viii) |z1 + z2 | ≤ |z1 | + |z2 | (Dreiecksungleichung) Beweis. Die erste Aussage in (i) ist offensichtlich. Für die zweite setze z1 = a + bi, z2 = c + di. Dann ist z1 · z2 = ac − bd + (ad + bc)i und z 1 · z 2 = (a − bi) · (c − di) = ac − bd + (−ad − bc)i = z1 · z2. (ii) rechnet man entweder von Hand mit der Formel für das Inverse nach, oder man verwendet die folgende elegantere Methode: Es gilt z · z −1 = 1. Wir konju- gieren alles und erhalten mit (i) zz −1 = z · z −1 = 1 = 1. Also ist z −1 das (eindeutige) multiplikativ Inverse zu z. Das ist gerade die Aussage. Für (iii) setzen wir z = a + bi und rechnen z + z = a + bi + a − bi = 2a = 2Re(z), und das ist gerade die erste Aussage. Weiter ist z − z = a + bi − (a − bi) = 2bi = 2Im(z)i. Wenn wir mit − 21 i multiplizieren, erhalten wir rechts genau Im(z), da i2 = −1. 2.2. GRUPPEN, RINGE UND KÖRPER 43 Für (iv) berechnen wir √ √ |Re(z)| = |a| = a2 ≤ a2 + b2 = |z|, und analog für Im(z) = b. (v) ist offensichtlich. Für (vi) rechnen wir z · z = (a + bi) · (a − bi) = a2 − b2 i2 = a2 + b2 = |z|2. Für (vii) verwenden wir (vi) und (i): |z1 z2 |2 = z1 z2 z1 z2 = z1 z1 z2 z2 = |z1 |2 |z2 |2. Wenn wir auf beiden Seiten die Quadratwurzel ziehen, erhalten wir das Ergebnis. Für (viii) schließlich rechnen wir: |z1 + z2 |2 = (z1 + z2 )(z1 + z2 ) = z1 z 1 + z1 z 2 + z2 z 1 + z2 z 2 = |z1 |2 + |z2 |2 + z1 z 2 + z1 z 2 = |z1 |2 + |z2 |2 + 2Re(z1 z 2 ). Dabei haben wir wieder (vi), (i) und (iii) verwendet. Weiter ist (|z1 | + |z2 |)2 = |z1 |2 + 2|z1 ||z2 | + |z2 |2 = |z1 |2 + 2|z1 z2 | + |z2 |2 , wobei wir (vii) verwenden. Als Differenz erhalten wir (|z1 | + |z2 |)2 − |z1 + z2 |2 = 2 (|z1 z2 | − Re(z1 z 2 )). (2.2) Da aber |Re(z1 z 2 )| ≤ |z1 z 2 | = |z1 ||z 2 | = |z1 ||z2 | = |z1 z2 | nach (iv), (vii) und (v) gilt, ist (2.2) offensichtlich nichtnegativ. Damit gilt |z1 + z2 |2 ≤ (|z1 | + |z2 |)2 und nach Ziehen der Quadratwurzel ist das die Dreiecksungleichung. Nun wollen wir die Darstellung komplexer Zahlen in sogenannten Polarkoordina- ten untersuchen. Wir erhalten damit eine geometrische Interpretation der Mul- tiplikation. Bisher haben wir komplexe Zahlen z in kartesischen Koordinaten an- gegeben, d.h. in der Form z = a + bi = (a, b). Man kann die Punkte der Ebene R2 aber auch in Polarkoordinaten angeben. 44 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Definition 2.2.18. Jeder Punkt z ∈ C ist eindeutig bestimmt durch seinen Winkel θ (gegen den Urzeigersinn von der positiven x-Achse aus gemessen), und seinen Abstand r zum Ursprung. b z = a + bi r θ a Dabei ist θ ∈ [0, 2π) und r ≥ 0. Die Darstellung z = (r, θ) nennt man Polarkoordinatendarstellung von z. 4 Bemerkung 2.2.19. (i) Um Missverständisse zu vermeiden werden wir ab jetzt die kartesischen Koordinaten immer in der Form z = a + bi angeben, und die Tupelschreibweise z = (r, θ) bleibt den Polarkoordinaten vorbehalten. (ii) Für z = a + bi = (r, θ) gilt r · sin(θ) = b, r · cos(θ) = a, r2 = a2 + b2 = |z|2. Damit kann man die beiden Darstellungstypen ineinander umrechnen. Sind zum Beispiel die kartesischen Koordinaten a und b gegeben, erhält man √   −1 b a 2 2 r = |z| = a + b , θ ∈ sin ∩ cos−1 ∩ [0, 2π). r r Sind hingegen die Polarkoordinaten r und θ gegeben, bekommt man direkt a = r · cos(θ), b = r · sin(θ). 4 Beispiel 2.2.20. (i)√ Sei z = 1 √ + i in kartesischen Koordinaten gegeben. Wir be- rechnen r = |z| = 1 + 1 = 2 sowie   1 θ = arcsin √ = π/4. 2 2.2. GRUPPEN, RINGE UND KÖRPER 45 Also ist √ z = ( 2, π/4) die Darstellung in Polarkoordinaten. (ii) Für z1 = 1, z2 = i, z3 = −1, z4 = −i erhält man analog die Polarkoordinaten z1 = (1, 0), z2 = (1, π/2), z3 = (1, π), z4 = (1, 3π/2). z2 = i z3 = −1 π π/2 z1 = 1 3π/2 z4 = −i (iii) Sei z = (1, 3π/4) in Polarkoordinaten gegeben. Wir berechnen die kartesi- schen Koordinaten: 1 1 a = 1 · cos(3π/4) = − √ , b = 1 · sin(3π/4) = √. 4 2 2 Wie schon erwähnt liegt einer der Hauptvorteile der Polarkoordinaten in der be- sonders schönen Formel für die Multiplikation. Sie erlaubt ein unmittelbares geo- metrisches Verständnis: Satz 2.2.21. Die Multiplikation zweier komplexer Zahlen erfüllt in Polarkoordinaten die folgende Gleichung: (r, θ) · (s, η) = (r · s, θ + η). Beweis. Sei z1 = (r, θ) und z2 = (s, η). Wir rechnen zunächst in kartesische Koordinaten um: z1 = r cos(θ) + r sin(θ)i, z2 = s cos(η) + s sin(η)i. 46 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Nun können wir die Multiplikation durchführen: z1 z2 = rs cos(θ) cos(η) − rs sin(θ) sin(η) + (rs cos(θ) sin(η) + rs sin(θ) cos(η)) i. Es gilt also Re(z1 z2 ) = rs(cos(θ) cos(η) − sin(θ) sin(η)) = rs cos(θ + η) und Im(z1 z2 ) = rs(cos(θ) sin(η) + sin(θ) cos(η)) = rs sin(θ + η). Dabei verwenden wir die aus der Analysis als bekannt vorausgesetzten Additions- theoreme für Sinus und Cosinus. Diese Koordinaten rechnen wir nun wieder in Polarkoordinaten um. Wir erhalten als Betrag von z1 z2 p p |z1 z2 | = (rs cos(θ + η))2 + (rs sin(θ + η)2 = (rs)2 = rs, wobei wir sin(ϕ)2 + cos(ϕ)2 = 1 für alle ϕ und r, s ≥ 0 verwenden. Für den Winkel von z1 z1 bekommen wir   rs sin(θ + η) arcsin = arcsin(sin(θ + η)) = θ + η. rs Genau das war zu zeigen. Bemerkung 2.2.22. Die geometrische Interpretation der Multiplikation ist also einfach: Man addiert die Winkel der Elemente, und multipliziert ihre Längen. z1 · z2 z2 z1 2.2. GRUPPEN, RINGE UND KÖRPER 47 Auf diese Weise sehen wir auch sofort, warum i2 = −1 gilt: i −1 4 In den reellen Zahlen kann man im Allgemeinen nicht beliebige Wurzeln aus Ele- menten ziehen. Wir wissen ja, dass −1 keine reelle Quadratwurzel besitzt und das war gerade die Motivation zur Konstruktion von C. Aber auch wenn es Wur- zeln gibt, gibt es eventuell nicht so viele, wie man vielleicht erwarten könnte. Wenn wir uns beispielsweise für die vierten Wurzeln von 1 interessieren, also für die Lösungen der Gleichung x4 − 1 = 0, so finden wir in R gerade 1 und −1. Die Gleichung ist aber gerade vom Grad 4, und wir könnten deshalb sogar bis zu 4 verschiedene Lösungen erwarten. In der Tat sind ja i und −i weitere Lösungen der Gleichung, die aber echt komplex sind. Satz 2.2.23 (Existenz von Einheitswurzeln). Sei n ≥ 1 eine positive ganze Zahl. Dann gibt es genau n verschiedene Zahlen 1 = ζ0 , ζ1 ,... , ζn−1 ∈ C mit ζjn = 1 für alle j = 0,... , n − 1. Beweis. Wir geben die ζj in Polarkoordinaten an: ζj := (1, 2πj/n). Die ζj sind offensichtlich paarweise verschieden, da sie die paarweise verschie- denen Winkel 0, 2π/n, 4π/n, 6π/n,... , 2π(n − 1)/n besitzen. Auch ζ0 = 1 ist klar. Mit Satz 2.2.21 gilt ζjn = (1n , n · 2πj/n) = (1, 2πj) = 1, 48 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG da Vielfache von 2π ja gerade dem Winkel 0 entsprechen. Es bleibt noch zu zeigen, dass es keine weiteren n-ten Wurzeln aus 1 gibt. Falls ζ = (r, ϕ) mit r ≥ 0 und ϕ ∈ [0, 2π) aber 1 = ζ n = (rn , nϕ) erfüllt, so muss rn = 1 und nϕ = 2πj für ein 0 ≤ j ≤ n − 1 gelten. Daraus folgt r = 1 und ϕ = 2πj/n, also ζ = ζj. Definition 2.2.24. Die ζj aus dem letzten Satz werden n-te Einheitswurzeln ge- nannt. 4 Bemerkung 2.2.25. Wir erhalten die n-ten Einheitswurzeln also gerade durch die Einteilung des Einheitskreises in C in n gleiche Stücke: ζ2 = (1, 4π/n) ζ1 = (1, 2π/n) ζ3 = (1, 6π/n) 1 = ζ0 ζ4 ζn−1 = (1, 2π(n − 1)/n) Wenn man ζ1 mit sich selbst mutlipliziert, wandert es einen Schritt weiter zu ζ2. Die dritte Potenz ist ζ3 , usw. In der n-ten Potenz ist man gerade einmal durch den Kreis gelaufen, und bei 1 gelandet. Wenn man ζ2 quadriert erhält man ζ4. Aus der Formel ζ2n = (1, 4π) sieht man, dass man nach der n-ten Potenz gerade zweimal durch den Kreis gelaufen ist, und bei der 1 landet. Allgemein wandert ζj beim potenzieren j-mal durch den Kreis und landet nach der n-ten Potenz bei 1. Allerdings kann ζj auch schon vorher einmal bei 1 gelandet sein. 4 Definition 2.2.26. Eine n-te Einheitswurzel, die das erste Mal in der n-ten Potenz 1 ergibt, heißt primitive n-te Einheitswurzel. 4 2.2. GRUPPEN, RINGE UND KÖRPER 49 Beispiel 2.2.27. (i) Sei n = 4. Wir finden die 4-ten Einheitswurzeln 1, i, −1 und −i: i −1 1 −i Es gilt 11 = 12 = 13 = 14 = 1 i1 = i, i2 = −1, i3 = −i, i4 = 1 (−1)1 = −1, (−1)2 = 1, (−1)3 = −1, (−1)4 = 1 (−i)1 = −i, (−i)2 = −1, (−i)3 = i, (−i)4 = 1. Die Zahlen 1 und −1 ergeben also schon in kleinerer Potenz als 4 einmal 1. Sie sind ja auch 2-te Einheitswurzeln. Die Zahlen i und −i werden erst nach dem vierten Potenzieren das erste Mal 1. (ii) Es sind i und −i primitive 4-te Einheitswurzeln. Die −1 ist keine primitive 4-te Einheitswurzel, aber eine primitive 2-te Einheitswurzel. Die 1 ist eine (die!) primitive erste Einheitswurzel. 4 Man kann nun sehr einfach auch Wurzeln aus anderen Elementen ziehen: Satz 2.2.28. Sei n ≥ 1 eine positive ganze Zahl und 0 6= z ∈ C. Dann gibt es genau n verschiedene Zahlen ω1 ,... , ωn ∈ C mit ωjn = z für j = 1,... , n. 50 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Beweis. Schreibe z = (r, ϕ) in Polarkoordinaten, mit r > 0 und ϕ ∈ [0, 2π). Die offensichtlichste n-te Wurzel aus z entsteht, indem man den Winkel durch n teilt und die n-te Wurzel aus dem (positiven) Radius zieht: √ ω1 = ( n r, ϕ/n). Seien nun 1 = ζ0 , ζ1 ,... , ζn−1 die n-ten Einheitswurzeln. Setze ωj = ζj−1 · ω1 für j = 2,... , n. Wir multiplizieren ω1 also gerade mit den n-ten Einheitswur- zeln. Es entstehen dabei weitere n-te Wurzeln aus z: ωjn = ζj−1 n ω1n = 1 · z = z. Die ωj sind außerdem paarweise verschieden, aufgrund der Kürzungsregel (die sich aus der Existenz von multiplikativ inversen Elementen ergibt). Sei nun ω = (s, ψ) eine weitere n-te Wurzel aus z, mit s ≥ 0 und ψ ∈ [0, 2π). Es gilt also (r, ϕ) = z = ω n = (sn , n · ψ), √ und damit s = n r, ψ = n1 (ϕ + 2πj) für ein 0 ≤ j ≤ n − 1. Damit ist √ √ ω = ( n r, ϕ/n + 2πj/n) = (1, 2πj/n) · ( n r, ϕ/n) = ζj · ω1 = ωj+1. Also gibt es keine weiteren n-ten Wurzeln außer den ωj. Bemerkung 2.2.29. Wir sehen, wie man die Wurzeln geometrisch zu verstehen hat. Die offensichtlichste n-te Wurzel ω1 aus z entsteht durch Teilung des Win- kels durch n und Ziehen der n-ten Wurzel aus dem Radius (hier zum Beispiel n = 4): z ω1 2.2. GRUPPEN, RINGE UND KÖRPER 51 Die weiteren n-ten Wurzeln aus z entstehen durch Multiplikation von ω1 mit den ζj , also durch Addition der Vielfachen von 2π/n zum Winkel: ω2 ω1 ω3 ω4 4 Wir haben gesehen, dass sich in C sehr viele polynomiale Gleichungen lösen las- sen, wie etwa xn − a = 0, mit a ∈ C. Der Fundamentalsatz der Algebra besagt, dass sich alle polynomialen Gleichungen lösen lassen. Satz 2.2.30 (Fundamentalsatz der Algebra). Seien c0 , c1 ,... , cn ∈ C, wobei n ≥ 1 und cn 6= 0. Dann gibt es ein z ∈ C mit c0 + c1 z + c2 z 2 + · · · + cn z n = 0. Jede polynomiale Gleichung vom Grad n ≥ 1 besitzt also eine Lösung. Beweis. Sei p = c0 + c1 t + c2 t2 + · · · + cn tn das gegebene Polynom, mit n ≥ 1 und cn 6= 0. Auf jeder abgeschlossenen Kreisschreibe Br = {z ∈ C | |z| ≤ r} nimmt die stetige Funktion |p| : z 7→ |p(z)| ein Minimum an. Wegen   n c0 cn−1 p(z) = cn z n + ··· + +1 cn z cn z für alle z 6= 0 sieht man aber auch |p(z)| → ∞ für |z| → ∞. 52 KAPITEL 2. GAUSS-ALGORITHMUS UND MATRIXRECHNUNG Deshalb gibt es ein globales Minimum z0 ∈ C von |p|, es gilt also |p(z0 )| ≤ |p(z)| für alle z ∈ C. Nach einer Translation können wir o.B.d.A. z0 = 0 annehmen, also p(z0 ) = c0. Angenommen es gilt 0 6= p(z0 ) = c0. Sei m die kleinste Zahl > 0 mit cm 6= 0, es gelte also p = c0 + cm tm + tm+1 q für ein Polynom q. Wir wählen mit Satz 2.2.28 ein z1 ∈ C mit c0 z1m = −. cm Für λ ∈ R gilt dann p(λz1 ) = c0 1 − λm + c−1 m+1 m+1
0 λ z1 q(λz1 ) und für λ ∈ [0, 1] also |p(λz1 )| ?