Mathe-II-Skript - Lehrkörper / Mitarbeiterhome.mathematik.uni-freiburg.de/junker/skripte/scriptMatheII.pdf · UnterMitarbeitvonDavidZschockeDiesesSkriptentstehtnachundnachundsollim

Mathe-II-Skript

Markus Junker

7. April 2014

Unter Mitarbeit von David Zschocke Dieses Skript entsteht nach und nach und soll imWesentlichen den Inhalt der im Sommersemester 2013 an der Albert-Ludwigs-Universitätin Freiburg gehaltenen Vorlesung „Mathematik II für Studierende der Informatik“ wieder-geben. An einzelnen Stellen wird das Skript über die Vorlesung hinausgehen; umgekehrtsind nicht alle Bemerkungen, Erläuterungen und Beispiele aus der Vorlesung enthalten.Das Skript verdankt viel einer von Lisa Schüttler angefertigten Mitschrift der gleichenVorlesung im Sommersemester 2012.

„Plagiats-Disclaimer“

Das Skript ist nach in der Mathematik gängiger Vorgehensweise angefertigt. Dies bedeu-tet, dass es keinen Anspruch auf eine eigene wissenschaftliche Leistung erhebt und keineeigenen Ergebnisse wiedergibt, sondern die Ergebnisse anderer darstellt. Diese Ergebnis-se sind über Jahrhunderte gewachsen; da Mathematik weitgehend ahistorisch betriebenwird, lässt sich in der Regel nicht mehr zurückverfolgen, von wem welche Fragestellungen,Begriffe, Sätze, Beweise oder Beweistechniken stammen. Vereinzelt gibt es überlieferteZuweisungen von Sätzen oder von Beweisen zu Mathematikern (die aber nicht immerhistorisch exakt sein müssen).Die Darstellung des Stoffes orientiert sich an den von mir selbst gehörten Vorlesungen,an Skripten von Kollegen und an Büchern. Diese verschiedenen Einflüsse sind nicht zutrennen und können daher nicht einzeln dargelegt werden. Fehler dagegen sind von mir zuverantworten. Insbesondere bei Formeln empfiehlt sich eine kritische Lektüre, da kleineTippfehler aufgrund mangelnder Redundanz gleich massive Fehler bewirken.

3

Inhaltsverzeichnis

I. Lineare Algebra 7

1. Grundlegende algebraische Strukturen 91.1. Strukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2. Monoide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3. Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4. Ringe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5. Körper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.6. Exkurs: Äquivalenzrelation (ÄR) . . . . . . . . . . . . . . . . . . . . . . . 16

2. Vektorräume 192.1. Vektorräume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2. Untervektorräume und Erzeugende . . . . . . . . . . . . . . . . . . . . . . 212.3. Lineare Unabhängigkeit, Basis, Dimension . . . . . . . . . . . . . . . . . . 232.4. Lineare Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.5. Matrixmultiplikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.6. Basiswechsel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.7. Lineare Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.7.1. Das Gauß-Verfahren zum Lösen linearer Gleichungssysteme . . . . 442.8. Determinanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482.9. Längen, Winkel, Skalarprodukt . . . . . . . . . . . . . . . . . . . . . . . . 50

3. Lineare Codes 573.1. Lineare Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.2. Gütekriterien und Schranken für Codes . . . . . . . . . . . . . . . . . . . . 613.3. Erzeuger und Prüfmatrizen . . . . . . . . . . . . . . . . . . . . . . . . . . 643.4. Liste der perfekten Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

II. Algebra 71

4. Gruppen 734.1. Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.2. Zyklische Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764.3. Nebenklassen und Faktorgruppen . . . . . . . . . . . . . . . . . . . . . . . 81

5

Inhaltsverzeichnis

5. Ringe 895.1. Ringe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895.2. Die endlichen Ringe Z/mZ . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

III. Analysis mehrerer Veränderlicher 97

6. Vorüberlegungen 996.1. Stetigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

7. Differentialrechnung 1017.1. Differenzierbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1017.2. Höhere Ableitungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

8. Integralrechnung 1098.1. Höherdimensionale Integration . . . . . . . . . . . . . . . . . . . . . . . . 109

8.1.1. Integration über Normalgebiete in R2 . . . . . . . . . . . . . . . . 1108.1.2. Wegintegrale/Kurvenintegrale . . . . . . . . . . . . . . . . . . . . . 111

6

Teil I.

Lineare Algebra

7

1. Grundlegende algebraische Strukturen

1.1. Strukturen

Erläuterungalgebraische Stukturen sind die Zusammenfassung einer Menge M mit einer oder mehre-ren inneren Operationen/Funktionen (d.h. Abbildungen Mn →M) und/oder einer odermehrere äußere Verknüpfungen (d.h. Abbildungen R ×M → M), die gewisse ”schöne”Eigenschaften haben.Beispiel

1. ganze Zahlen M = Z, + :M ×M →M

2. ganze Zahlen M = Z, · :M ×M →M

3. Die Menge der Funktionen von R nach R als M mit der Verknüpfung ◦ als Hinte-randerausführung.

4. Die Menge M = A∗ aller Wörter über einem Alphabet A. Wörter sind endlicheFolgen von Symbolen. Eine mögliche Verknüpfung wäre die Konkatenation als Hin-teranderschreiben der beiden Wörter.

Definition: Eigenschaften von der VerknüpfungenDie Eigenschaften können u.a. folgende Eigenschaften haben:• kommutativ m1 ∗m2 = m2 = m1 (im Beispiel sind 1,2 kommutativ)• Assoziativität m1 ∗ (m2 ∗m3) = (m1 ∗m2)∗m3 (im Beispiel sind 1,2,3,4 assoziativ)

ErläuterungWichtige Strukturen sind Vektorräume, Gruppen(groups), Ringe(rings), Körper(fields)

Definition: F2

F2 ist Körper mit den Elementen 0, 1 und den zwei inneren Verknüpfungen + als ∨ und· als ∧.

9


1.2. Monoide

Definition: MonoidEin Monoid 1 besteht aus einer nicht-leeren Menge M und einer zweistelligen Verknüp-fung ◦ auf M , also einer Abbildung ◦ :M ×M →M , die• assoziativ ist, d. h. (m1 ◦m2)◦m3 = m1 ◦(m2 ◦m3) für alle m1,m2,m3 ∈M erfüllt,• und ein neutrales Element e ∈ M besitzt, d. h. es gilt e ◦m = m ◦ e = m für allem ∈M .

Ein Monoid (M, ◦) heißt kommutatives Monoid, wenn die Verknüpfung ◦ zusätzlich• kommutativ ist, d. h. m1 ◦m2 = m2 ◦m2 für alle m1,m2 ∈M erfüllt.

ErläuterungDas neutrale Element ist eindeutig bestimmt, denn falls e, e′ neutrale Elemente sind, sogilt e = e ◦ e′ = e′.Wegen der Assoziativität kann man bei iterierten Verknüpfungen Klammern weglassen.Beispiel

• Die natürlichen Zahlen N bilden mit der Addition + ein kommutatives Monoid mitneutralem Element 0.• Die natürlichen Zahlen N bilden mit der Multiplikation · ein kommutatives Monoid

mit neutralem Element 1.• Die echt positiven natürlichen Zahlen N \ {0} bilden mit der Multiplikation · ein

kommutatives Monoid mit neutralem Element 1.• Die Abbildungen Abb(A,A) einer Menge A in sich selbst bilden unter der Kompo-

sition ◦, d. h. der Hintereinanderausführung von Funktionen, ein (i. a. nicht kom-mutatives) Monoid, dessen neutrales Element die identische Abbildung idA ist.• Wenn A eine Menge ist (in diesem Kontext auch „Alphabet“ genannt), bildet die

Menge A∗ der endlichen Folgen von Elementen aus A (auch „Wörter über A“ ge-nannt) mit der „Konkatenation“ (d. h. Hintereinandersetzen)� ein (i. a. nicht kom-mutatives) Monoid. Mit A = {a, b, c} ist also z. B. abaac� ccb = abaacccb. Dasneutrale Element ist das „leere Wort“, also die Folge der Länge 0, das oft mit λoder ε bezeichnet wird.

BeispielGegenbeispiele:• Die echt positiven natürlichen Zahlen N \ {0} bilden mit der Addition + kein Mo-

noid, da es kein neutrales Element gibt.• Die natürlichen Zahlen N bilden mit der Exponentiation kein Monoid, da die Expo-

nentiation nicht assoziativ ist, denn z. B. ist 232 = 29 = 512, aber (23)2 = 82 = 64.Zudem gibt es zwar ein „rechtneutrales Element“ (da n1 = n für alle n ∈ N), aberkein „linksneutrales“.

Notation: Weglassen von Teilen der Definition

10

1.3. Gruppen

Wenn die Menge M mit der Verknüpfung ◦ und neutralem Element e ein Monoid bildet,schreibt man dafür üblicherweise (M, ◦, e) oder (M, ◦), da e eindeutig festgelegt wird.Wenn man sauber arbeitet, unterscheidet man notationell zwischen der Struktur undder zugrundeliegenden Menge und schreibt dann gerne für die Struktur den entsprechen-den Buchstaben in einem anderen Schriftart, also z. B. M oder M für ein Monoid mitGrundmenge M . Oft erlaubt man sich aber die Unsauberkeit, für die Struktur und dieGrundmenge das gleiche Symbol (hier z. B. M) zu verwenden.Bei der Angabe eines Monoids entfällt bisweilen die Angabe der Verknüpfung, wenn ausdem Kontext heraus offensichtlich ist, welche gemeint ist, oder wenn es eine besondersnatürliche Verknüpfung gibt. Wenn man z. B. vom Monoid der Wörter über einem Al-phabet spricht oder dem Monoid der Abbildungen einer Menge in sich selbst, meint mandie oben angegebenen Standardbeispiele. Das doppelte Beispiel der natürlichen Zahlen– einmal mit Addition und einmal mit Multiplikation – zeigt aber, dass man i. a. aufdie Angabe der Verknüpfung nicht verzichten kann und selbst eine natürlich wirkendeOperation nicht unbedingt einen Alleinstellungsanspruch hat.Wenn mehrere Monoide betrachtet werden, werden oft die gleichen Notationen für dieVerknüpfungen und neutralen Elemente gebraucht. Es kann also vorkommen, dass manMonoid (M, ◦, e) und (N, ◦, e) betrachtet. Zur Verdeutlichung schreibt man dann manch-mal ◦M und eM für Verknüpfung und neutrales Element von M und analog ◦N und eNfür die von N .Analoge Bemerkungen zur Notation gelten für alle im weiteren eingeführten algebraischenStrukturen!

1.3. Gruppen

Definition: GruppeEin Gruppe besteht aus einer nicht-leeren Menge G und einer zweistelligen Verknüpfung◦ auf G, die• assoziativ ist,• ein neutrales Element e ∈M besitzt,• und bezüglich der es inverse Elemente gibt, d. h. zu jedem g ∈ G gibt es ein Elementh ∈ G mit h ◦ g = g ◦ h = e.

Eine Gruppe (G, ◦) heißt kommutative Gruppe 2, wenn die Verknüpfung ◦ zusätzlichkommutativ ist.

ErläuterungJede (kommutative) Gruppe ist also insbesondere ein (kommutatives) Monoid.Die inversen Elemente sind eindeutig bestimmt, denn sind h1, h2 invers zu g, so gilt

h1 = h1 ◦ e = h1 ◦ (g ◦ h2) = (h1 ◦ g) ◦ h2 = e ◦ h2 = h2.

Das bezüglich ◦ zu g ∈ G inverse Element wird mit g−1 bezeichnet.

11


Notation: gebräuchliche Notationen für GruppenEs gibt drei gebräuchliche Notationen für Gruppen:

Verknüpfung neutrales Element inverses Element

allgemein: ◦ e g−1

multiplikativ: · 1 g−1

additiv: + 0 −g

Die additive Schreibweise ist im allgemeinen kommutativen Gruppen vorbehalten. Beider multiplikativen Schreibweise lässt man den Multiplikationspunkt auch gerne weg.Beispiel

• (Z,+, 0) ist kommutative Gruppe.• (Q,+, 0), (Q \ {0}, ·, 1) und (Q>0, ·, 1)mitQ>0 = {q ∈ Q | q > 0} sind kommutative

Gruppen.• Ebenso mit R statt Q und – außer für das letzte Beispiel – mit C statt Q, .• (Sym(A), ◦, id) ist eine i. a. nicht kommutative Gruppe, wobei Sym(A) die Menge

der Bijektionen einer Menge A in sich bezeichnet.• Wichtiges Beispiel einer Gruppe wird die „verallgemeinerte Uhren-Arithmetik“ sein,

d. i. die kommutative Gruppe Zm =({0, . . . ,m− 1},+m, 0

), wobei

x+m y = „Rest von x+ y bei Division durch m“ =

{x+ y falls x+ y < m

x+ y −m falls x+ y ≥ m

Für n = 12 ist dies die Art, wie man mit Uhrzeiten rechnet („8 Uhr + 5 Stunden= 1 Uhr “).

Beispiel(Z \ {0}, ·, 1) oder (Q, ·, 1) sind keine Gruppen; im ersten Fall fehlen allen Elementenaußer 1 und −1 die Inversen; im zweiten Fall hat 0 kein Inverses.ErläuterungBemerkung: Man sieht bei genauerem Anschauen, dass manche dieser Gruppen von ein-fachen Beispielen für Monoide herstammen. Zum Beispiel ist (Z,+, 0) eine Gruppe, dieaus dem Monoid (N,+, 0) dadurch entsteht, dass man Inverse (also hier die negativenElemente) hinzunimmt. Das funktioniert nicht immer, wie man am Beispiel der Nullbezüglich der Multiplikation weiß oder am Beispiel der Abbildungen sehen kann: Wennh ◦ g1 = h ◦ g2 für g1 6= g2 gilt, kann kein (Links-)Inverses für h gefunden werden und dieAbbildung assoziativ bleiben. Bei dem Abbildungsmonoid (Abb(A), ◦) kommt man nurdadurch offensichtlich zu einer Gruppe, dass man die Elemente herausgreift, die schonein Inverses im Monoid haben (also die Bijektionen).

Definition: Symmetrische Gruppe

12

1.4. Ringe

Die Menge Sym(A) einer Menge A ist die Menge aller Bijektionen A → A (d.h. allePermutationen von A). (Sym(A), ◦, idA) ist die symmetrische Gruppe über A. (◦ ist dieHintereinanderausführung.)

Die symmetrische Gruppe ist für |A| ≥ 3 nicht kommutativ.

Beispiel|A| = 2, A = {a, b}: Sym(A) = {idA, τ} mit τ(a) = b, τ(b) = a

Definition: GruppentafelDie Gruppentafel ist eine Tabelle, die alle möglichen Hintereinanderausführungen zweierFunktionen einer Gruppe enthält. Eine Gruppe ist symmetrisch, wenn die Gruppentafelmit der Diagonale von links oben nach rechts unten eine Symmetrieachse besitzt.

BeispielZu A = {a, b}: Sym(A) = {idA, τ} mit τ(a) = b, τ(b) = a ist die Gruppentafel:

idA τ

idA idA ττ τ idA

Beispiel|A| = 3, A = {a, b, c}, Sym(A) = {idA, (ab), (ac), (bc), (abc), (acb)}, wobei die Elementedie zyklische Permutationen angeben: (ab) : a 7→ b, b 7→ a, c 7→ c.Aufgabe: Gruppentafel aufstellenStellen Sie zur symmetrischen Gruppe aus dem letzten Beispiel die Gruppentafel auf!(Fehlender Inhalt: Automorphismen der Struktur)

1.4. Ringe

Definition: RingEin Ring besteht aus einer nicht-leeren Menge R, zwei zweistelligen Verknüpfungen +und · auf R (Addition und Multiplikation) und Elemente 0 und 1 (Null und Eins), fürdie gilt:• (R,+, 0) ist eine kommutative Gruppe;• (R, ·, 1) ist ein Monoid;

13


• es gelten die Distributivgesetze, d. h. für alle r1, r2, s ∈ R gilt:

(r1 + r2) · s = (r1 · s) + (r2 · s)s · (r1 + r2) = (s · r1) + (s · r2)

Ein Ring (R,+, ·) heißt kommutativer Ring , wenn die Multiplikation zusätzlich kommu-tativ ist.

ErläuterungGenauer handelt es sich hier um „Ringe mit Eins“ oder „unitäre Ringe“. Es gibt auch einallgemeineres Konzept von Ring, bei dem es kein neutrales Element der Multiplikationzu geben braucht. Bei der Lektüre anderer Skripte oder Bücher muss man also vorsichtigsein, welche Definition jeweils benutzt wird.In einem kommutativen Ring folgt natürlich jedes der beiden Distributivgesetze aus demanderen.Notation: Weglassen von KlammernZur Ersparnis von Klammern führt man die üblichen „Vorfahrtsregeln“ ein, also „Punktvor Strich“; den Multiplikationspunkt lässt man auch gerne weg. Das erste Distributiv-gesetz kann man also kurz als (r1 + r2)s = r1s+ r2s schreiben.Man rechnet nach, dass r · 0 = 0 · r = 0 für alle r ∈ R ist (denn z. B. r · 0 = r · (0 + 0) =r · 0 + r · 0).ähnlich sieht man, dass (−r) · s = r · (−s) = −(r · s) für alle r, s ∈ R. Auch hier kannman daher Klammern einsparen.Beispiel

• Die Definition verbietet nicht, dass 0 = 1 ist. In diesem Fall folgt aber r = r · 1 =r · 0 = 0 für alle r ∈ R, und es liegt der sogenannte triviale Ring vor, der nur auseinem Element besteht.• Z, Q, R und C – jeweils mit der normalen Addition und Multiplikation – sind

kommutative Ringe.• Die Gruppe Zm kann durch eine analog definierte Multiplikation ·m zu einem kom-

mutativen Ring gemacht werden: x ·m y rechnet man dadurch aus, dass man vondem normalen Produkt in Z den Rest bei der Division durch m nimmt, also solangem abzieht, bis man im Bereich {=, . . . ,m− 1} landet.• Die Polynome mit Koeffizienten in einem Ring R und der Unbekannten X bilden

mit der bekannten Polynomaddition und -multiplikation den Polynomring R[X],also z. B. R[X] (Polynome mit einer Unbekannten X und Koeffizienten in R) oderZ[X] (Polynome mit einer Unbekannten X und Koeffizienten in Z).Nimmt man mit einer neuen Unbekannten Y z. B. den Polynomring R[X] als Koef-fizientenbereich, erhält man den Polynomring mit zwei Unbekannten X und Y mitKoeffizienten in R, also R[X][Y ] = R[X,Y ].

14

1.5. Körper

1.5. Körper

Definition: KörperEin Körper besteht aus einer nicht-leeren Menge K, zwei zweistelligen Verknüpfungen +und · auf R (Addition und Multiplikation) und Elemente 0 und 1 (Null und Eins), fürdie gilt:• 0 6= 1;• (K,+, 0) und K \ {0}, ·, 1 sind kommutative Gruppen;• es gelten die Distributivgesetze.

ErläuterungJeder Körper ist also insbesondere ein kommutativer, nicht-trivialer Ring.3

Beispiel

• Q, R und C sind Körper.• Für Primzahlen p ist Zp ein Körper und wird dann oft Fp geschrieben.

• R(x) ist der Körper der rationalen Funktionen über R,R(x) = {P (x)Q(x) |P,Q ∈ R[x], Q 6=

0}

Definition: F2

Besonders interessant für die Informatik ist der Körper F2, der aus den beiden Elementen0 und 1 besteht mit folgenden Verknüpfungen:

+ 0 1

0 0 11 1 0

· 0 1

0 0 01 0 1

ErläuterungGenauer handelt es sich hier um „Ringe mit Eins“ oder „unitäre Ringe“. Es gibt auch einallgemeineres Konzept von Ring, bei dem es kein neutrales Element der Multiplikationzu geben braucht. Bei der Lektüre anderer Skripte oder Bücher muss man also vorsichtigsein, welche Definition jeweils benutzt wird.In einem kommutativen Ring folgt natürlich jedes der beiden Distributivgesetze aus demanderen.Notation: VorfahrtsregelnZur Ersparnis von Klammern führt man die üblichen „Vorfahrtsregeln“ ein, also „Punktvor Strich“; den Multiplikationspunkt lässt man auch gerne weg. Das erste Distributiv-gesetz kann man also kurz als (r1 + r2)s = r1s+ r2s schreiben.

3Es gibt auch ein etwas allgemeineres Konzept eines „Schiefkörper“, bei dem die Multiplikation nichtkommutativ zu sein braucht.

15


Man rechnet nach, dass r · 0 = 0 · r = 0 für alle r ∈ R ist (denn z. B. r · 0 = r · (0 + 0) =r · 0 + r · 0).ähnlich sieht man, dass (−r) · s = r · (−s) = −(r · s) für alle r, s ∈ R. Auch hier kannman daher Klammern einsparen.

1.6. Exkurs: Äquivalenzrelation (ÄR)

Definition: binäre RelationenSei M eine Menge. Eine zweistellige (d.h. binäre) Relation auf M ist eine Eigenschaftvon Paaren von Elementen von M. Sie kann mit der Teilmenge der Paare von M ×Midentifiziert werden, auf die die Eigenschaft zutrifft.

BeispielM = N, <-Relation,≤-Relationen, >-Relationen sind Relationen.Notation: Teilbarkeitsrelation |Die Teilbarkeitsrelation | ist genau dann wahr, wenn die erste Zahl die zweite Zahl ganz-zahlig ohne Rest teilt.Beispiel15 ist durch 3 teilbar: 3|15, folglich 3 6 |14Notation: erfüllte binäre RelationR ist binäre Relation auf M,a, b ∈ M : ”aRb” bedeutet, dass R auf (a, b) zutrifft (alter-native Schreibweise: Rab).

Definition: Eigenschaften jeder ÄquivalenzrelationSei R eine binäre Relation.• R heißt ”reflexiv”, falls für alle m ∈M gilt Rmm• R heißt ”symmetrisch”, falls für alle m1,m2 ∈M gilt Rm1m2 ⇔ Rm2m1.• R heißt ”transitiv”, falls für alle m1,m2,m3 ∈ M gilt Rm1m2 und Rm2m3 ⇒Rm1m3.

Definition: ÄquivalenzrelationEine Äquivalenzrelation auf M ist eine reflexive, symmetrische, transitive binäre Rela-tionen auf M .

Definition: ÄquivalenzklasseSei ∼ eine ÄR auf M . Die Äquivalenzklasse von m ∈ M bzgl. ∼ ist [[m]]∼ = M |∼ :={n ∈M |m ∼ n}

16

1.6. Exkurs: Äquivalenzrelation (ÄR)

ErläuterungDie Äquivalenzklassen bilden eine Partition von M :•⋃m∈M m|∼ =M .

• zwei Äquivalenzklassen sind entweder gleich oder disjunktumgekehrt: jede Partition kommt von einer Äquivalenzrelation.

Definition: Repräsentant, RepräsentantensystemFalls K ⊆M eine Äquivalenzklasse ist und m ∈ K, dann heißt m Vertreter (oder Reprä-sentant) der Klasse. Ein Vertreter- oder Repräsentantensystem von ∼ ist eine Teilmengevon M , die aus jeder Äquivalenzklasse genau einen Vertreter enthält.

BeispielM = Z× (Z\0) Schreibe (m1,m2) als m1

m2. Definiere m1

m2+ m3

m4= m1·m4+m2·m3

m2·m4

Definiere nun die ÄR ∼ der Gleichheit von Brüchen auf M als (m1m2) ∼ (m3m4) :⇔∃k, l ∈ Z\{0} mit (km1, km2) = (lm3, lm4).+ ist verträglich mit ∼, d.h. falls p1 ∼ p′1, p1 + p2 ∼ p1 + p′2 ⇒ p2 = p′2

17

2. Vektorräume

2.1. Vektorräume

Sei K ein Körper, also z. B. K = R oder K = F2 (dies werden die hauptsächlichenBeispiele in dieser Vorlesung sein). Zur Verdeutlichung sind die Körperelemente und -operationen vorübergehend mit einem Index K gekennzeichnet, also +K ,−K , ·K , 0K , 1K .

Definition: Ein K-Vektorraum V besteht aus einer nicht-leeren Menge V zusammen mit einer zwei-stelligen „inneren“ Verknüpfung + : V × V → V (der „Addition“) und einer „äußeren“Verknüpfung · : K × V → V (der „Skalarmultiplikation“), für die gilt:• (V,+) ist eine kommutative Gruppe mit neutralem Element 0V ;• es gelten folgende Regeln für die Skalarmultiplikation:

1K · v = v

(k1 +K k2) · v = (k1 · v) + (k2 · v)(k1 ·K k2) · v = k1 · (k2 · v)k · (v1 + v2) = (k · v1) + (k · v2)

für alle k, k1, k2 ∈ K und v, v1, v2 ∈ V .

Bemerkungen und Notation: Falls aus dem Kontext klar ist, um welchen Körper Kes geht, spricht man auch kurz von „Vektorraum“ statt von „K-Vektorraum“. Elementevon V heißen Vektoren, Elemente von K Skalare.Im Unterschied zu einem Ring kann man Vektoren in einem allgemeinen Vektorraumnicht miteinander multiplizieren1 ; es gelten aber ähnliche Regeln, die man ganz analogbeweisen kann. So gilt k · 0V = 0V und 0K · v = 0V und k · (−v) = (−Kk) · v = −(k · v)für alle k ∈ K und v ∈ V .Für Vektorräume erlaubt man sich die gleichen notationellen Kurzformen wie bei Ringen(Klammersparregeln und Weglassen des Multiplikationspunktes). Auch werde ich vonnun an die Indizes K und V in der Regel weglassen; dadurch bekommen 0, + und · einedoppelte Bedeutung, es sollte aber aus der Situation immer klar werden, welche Null bzw.welche Addition und Multiplikation gemeint sind. Eine Skalarmultiplikation liegt immerdann vor, wenn links ein Körperelement und rechts ein Vektor steht; wenn auf beiden

1dessen ungeachtet gibt es in speziellen Fällen gewisse Vektorprodukte

19

2. Vektorräume

Seiten ein Körperelement steht, handelt es sich um die Multiplikation im Körper. DieAddition kann nur zwischen zwei Vektoren oder zwischen zwei Körperelementen stehen.Notation: StandardschreibweisenSei v ∈ Kn ein K−Vektorraum und v ein n−Tupel von Elementen aus K. Dann gibt eszwei Standardschreibweisen:• Zeilenvektor (k1, k2, . . . , kn)

• Spaltenvektor

k1k2. . ., kn

Beispiele:

• Vektoren bzw. „Pfeile in der Ebene“• Rn, also die Menge der n-Tupel reeller Zahlen, ist ein R-Vektorraum mit komponen-

tenweiser Addition und Skalarmultiplikation. Die Tupel können als z. B. als Zeilen-vektoren (r1, . . . , rn) geschrieben werden. Dann ist also (r1, . . . , rn)+(s1, . . . , sn) =(r1+ s1, . . . , rn+ sn) und r · (r1, . . . , rn) = (r · r1, . . . , r · rn). Die Tupel können aber

auch als Spaltenvektoren

r1...rn

geschrieben werden.

• R2 = R×R = {(r, s)|r, s ∈ R} ist R-Vektorraum mit (r, s)+(r′, s′) = (r+r′, s+s′)und q · (r, s) = (q · r, q · s) für q, r, r′, s, s′ ∈ R.• R3 koordinatisierte Punkte im Raum• Verallgemeinerung Rn = {(r1, . . . , rn)|ri ∈ R} mit (r1, . . . rn)+ (r′1, . . . , r

′n) = (r1+

r′1, . . . , rn + r′n) und q · (r1, . . . , rn) = (q · r1, . . . q · · · rn) für q, ri ∈ R.• Falls K Körper, ist Kn = {(k1, . . . , kn)|ki ∈ K} bilden analog eines K−VR.• unendliche Folgen reeller Zahlen (r1, r2, r3, ..) bilden einen R−VR unter den kom-

ponentenweisen Operationen• auch unendliche Folgen anderer Körper K bilden einen K-Vektorraum• {0, 1}−Folgen ”mit endlichen Träger” (a1, a2, a3, ...) mit ai ∈ {0, 1} mit nur endlich

vielen Einsen, d.h. es existiert ein n0 ∈ N mit ai = 0 für i ≥ n0.• Folgen mit endlichem Träger über R(können als Polynom aufgefasst werden. Beides

sind R−Vektorräume• C kann mit R2 identifiziert. R2 ist R− Vektorraum, C ist C−Vektorraum, R2 ist

auch ein C−Vektorraum• Pfeile in der Ebene

1. Pfeile = orientierte Geradenstücke in der Ebene. Definiere eine Äquivalenz-relation ∼ auf den Pfeilen: p1 ∼ p2, falls p1 durch Parallelverschiebung in p2übergeht (d.h. p1, p2 haben die gleiche Länge und gleiche Richtung).

2. Äquivalenzklasse eines Pfeiles p besteht aus allen parallelen Pfeilen.3. Definiere z.B. die Addition auf Äquivalenzklassen: p1|∼ + p2|∼ = p|∼ wobei

20

2.2. Untervektorräume und Erzeugende

p|∼ durch bekannte Verfahren mit dem Parallelogramm.4. Wähle festes Repräsentantensystem der Äquivalenzklasse als Pfeile , die von

einem festen Punkt ausgehen.• Die komplexen Zahlen C oder die n-Tupel komplexer Zahlen Cn sind sowohl ein C-

Vektorraum (dann ist die Skalarmultiplikation mit komplexen Zahlen erlaubt) alsauch ein R-Vektorraum (dann wird nur die Skalarmultiplikation mit reellen Zahlenbetrachtet).• R ist kein F2-Vektorraum: Zwar gibt es die Skalarmultiplikation mit 0 und mit 1,

aber es ist z. B. 3 = 1 · 1, 5 +R 1 · 1, 5 6= (1 +F2 1) · 1, 5 = 0 · 1, 5 = 0.

2.2. Untervektorräume und Erzeugende

In diesem Abschnitt sei stets V ein K-Vektorraum.

Definition: UntervektorraumU ⊆ V heißt K-Untervektorraum von V , falls U unter den eingeschränkten Operationenselbst ein K-Vektorraum ist, d. h. 0 ∈ U und für alle u, u1, u2 ∈ U und k ∈ K liegen dieElemente u1 + u2, −u und k · u in U . Man schreibt dafür U 6 V .

ErläuterungSämtliche Regeln wie Assoziativität, Kommutativität und Distributivität oder die Neu-tralität von 0 übertragen sich automatisch auf Teilmengen.Die Abgeschlossenheit bezüglich Negation folgt automatisch aus den anderen Regeln, da−u = (−1) ·u. Wenn U 6= ∅, etwa u ∈ U , folgt 0 = u+(−u) ∈ U . Untervektorräume sindalso genau die nicht-leeren, bezüglich Addition und Skalarmultiplikation abgeschlossenenTeilmengen.Wenn der Körper K durch den Kontext bekannt ist, sagt man auch kurz „Untervektor-raum“ statt „K-Untervektorraum“. Außerdem verkürzt man bisweilen „Untervektorraum“zu „Unterraum“.BeispielSei K = R und V = R. Die R-Untervektorräume von V sind dann:• der triviale Untervektorraum {0};• alle Teilmengen {(x, y) ∈ R2 | ax+by = 0} für feste a, b ∈ R – dies sind die Geraden

durch den Ursprung (0, 0);• der ganze Vektorraum R2.

BeispielGegenbeispiele (keine Untervektorräume sind):• Die Punkte eines Kreises als kein Untervektorraum des R2 (nicht abgeschlossen

unter der Addition)

21

2. Vektorräume

• Die Fläche zwischen zwei sich schneidenden Geraden als kein Untervektorraum desR2 (nicht abgeschlossen unter der Addition)• Die Menge der Punkte eines Gitters als kein Untervektorraum des R2 (nicht abge-

schlossen unter der Skalarmultiplikation)

Man überzeugt sich leicht davon, dass ein Schnitt von beliebig vielen K-Untervektorräumen von V wieder ein K-Untervektorraum von V ist.

Definition: erzeugter UntervektorraumSeien v1, . . . , vn ∈ V . Der von v1, . . . , vn erzeugte Untervektorraum von V , bezeichnetmit 〈v1, . . . , vn〉 ist äquivalenterweise definiert als• der kleinste Untervektorraum von V , der v1, . . . , vn enthält;• der Schnitt aller Untervektorräumen von V , die v1, . . . , vn enthalten;• {k1v1 + · · ·+ knvn | k1, . . . , kn ∈ K}

Beweis zu: Äquivalenz der DefinitionenZur Äquivalenz der Definitionen: Man sieht leicht, dass jeder K-(Unter-)Vektorraum mitv1, . . . , vn auch jede sogenannte Linearkombination von v1, . . . , vn, d. i. jeden Ausdruckder Form k1v1 + · · · + knvn enthalten muss. Umgekehrt sieht man auch leicht, dass dieSummen und skalare Vielfache von Linearkombinationen von v1, . . . , vn wieder Linear-kombinationen von v1, . . . , vn sind und sich jedes vi als Linearkombination von v1, . . . , vnschreiben lässt (z. B. v1 = 1 ·v1+0 ·v2+ · · ·+0 ·vn), also bilden die Linearkombinationenvon v1, . . . , vn einen v1, . . . , vn enthaltenden Untervektorraum.Spezialfall: Für n = 0 erhält man die leere Menge und es ist 〈∅〉 = {0}; damit dieDefinition auch in diesem Fall stimmt, definiert man 0 als den Wert der „leeren Summe“.

Definition: unendlicher erzeugter UntervektorraumVerallgemeinerung: Für eventuell unendlich viele Vektoren, also für eine TeilmengeA ⊆ V , kann man ebenfalls den von A erzeugten Untervektorraum von V als den kleinstenA enthaltenden Untervektorraum definieren. Es gilt dann

〈A〉 = {k1a1 + · · ·+ knan | n ∈ N, a1, . . . an ∈ A, k1, . . . , kn ∈ K}.

Mengenklammern lässt man in der Kombination mit den spitzen Klammern für dasErzeugnis meist weg, d. h. man schreibt kurz 〈v1, v2, . . . 〉 statt 〈{v1, v2, . . . }〉 oder 〈vi |i ∈ I〉 statt 〈{vi | i ∈ I}〉.

Notation: erzeugen, Erzeuger, Erzeugendensystem, endlich erzeugtFalls V = 〈vi | i ∈ I〉, so sagt man• die vi (i ∈ I) „erzeugen V “ oder

22

2.3. Lineare Unabhängigkeit, Basis, Dimension

• die vi (i ∈ I) „sind Erzeuger (oder Erzeugende) von V “ oder• {vi | i ∈ I} „ist ein Erzeugendensystem von V “

oder Varianten hiervon.V heißt endlich erzeugt , falls es ein endliches Erzeugendensystem gibt.Beispiel

• (1, 0, 0), (0, 0, 1), (0, 0, 1) erzeugt R3

• (2, 2, 1), (3, 4, 5), (0, 1,−2), (0, 2,−1) erzeugen R3

• (0, 1, 0), (0, 0, 2), (0, 3,−2) erzeugen einen echten Unterraum von R3 nämlich {(0, r, s)|r, s ∈R}

2.3. Lineare Unabhängigkeit, Basis, Dimension

Sei wieder stets V ein K-Vektorraum, und sei A ⊆ V eine Menge von Vektoren.

Definition: Lineare AbhängigkeitEin Vektor v ∈ V ist linear abhängig von A, falls v ∈ 〈A〉, d. h. falls es a1, . . . , an ∈ Aund k1, . . . , kn ∈ K gibt mit v = k1a1 + · · ·+ knan.A ist linear unabhängig , falls kein a ∈ A linear abhängig von A \ {a} ist.

Aus der Definition folgt unmittelbar, dass eine Menge von unendlich vielen Vektorengenau dann linear unabhängig ist, wenn jede endliche Teilmenge linear unabhängig ist.

ErläuterungVorsicht vor den Tücken der Mengenschreibweise bei Doppelnennungen:Angenommen v1 = v2 ist linear unabhängig von v3. Dann ist v1 linear abhängig von{v2, v3}, aber die Menge {v1, v2, v3} ist linear unabhängig, denn {v1, v2, v3} = {v1, v3}.Dieses Problem führt in der Folge zu etwas umständlich wirkenden Formulierungen: Untereine Menge {vi | i ∈ I} ohne Doppelnennungen ist gemeint, dass vi 6= vj für i 6= j, alsodass die Elemente vi für i ∈ I paarweise verschieden sind. Anders ausgedrückt: dieAbbildung I → V , i 7→ vi ist injektiv, oder, noch einmal anders ausgedrückt, vi0 /∈

{vi |

i ∈ I \ {i0}}für alle i0 ∈ I.

{v1, . . . , vn} ist genau dann linear unabhängig und ohne Doppelnennungen, wenn nurdie „triviale Linearkombination“ 0 ergibt, d. h. wenn k1v1 + · · ·+ knvn = 0 nur für k1 =0, . . . , kn = 0 gilt.

Beweis zu: Kriterium lineare UnabhängigkeitWenn die Menge linear abhängig ist oder Doppelnennungen vorliegen, wenn also z. B.v1 = k2v2 + · · ·+ knvn, dann folgt (−1) · v1 + k2v2 + · · ·+ knvn = 0. Wenn es umgekehrt

23

2. Vektorräume

eine Darstellung k1v1+· · ·+knvn = 0 gibt, bei der etwa k1 6= 0, so folgt v1 = −k2k1v2+· · ·+

(−knmk1

)vn, also ist die Menge {v1, . . . , vn} linear abhängig oder hat Doppelnennungen.

Daraus folgt sofort die Version für unendlich viele Vektoren: Eine Menge ohne Doppel-nennungen {vi | i ∈ I} ist genau dann linear unabhängig, wenn es keine nicht-trivialeLinearkombination von endlich vielen Vektoren aus der Menge 0 ergibt.

Definition: BasisEine Basis von V ist ein linear unabhängiges Erzeugendensystem.

{vi | i ∈ I} ist eine Basis von V⇐⇒ {vi | i ∈ I} ist eine maximale linear unabhängige Teilmenge von V⇐⇒ {vi | i ∈ I} ist ein minimales Erzeugendensystem von V(„maximal“ und „minimal“ sind bezüglich der Teilmengenbeziehung)

Beweis zu: Zusammenhang Basis lineare Unabhängigkeit und Erzeugenden-system(Fehlender Inhalt: Beweis)

Jeder endlich erzeugte Vektorraum besitzt Basen; jedes endliche Erzeugendensystem ent-hält eine Basis und jede linear unabhängige Teilmenge lässt sich zu einer Basis vergrößern.

Folgerung 2.3 gilt auch für unendlich dimensionale Vektorräume, ist aber langwieriger zubeweisen.

ErläuterungOhne Beweis benutzen wir:2

Jeder Vektorraum besitzt Basen, und je zwei Basen eines Vektorraums haben die gleicheMächtigkeit (d. h. stehe in Bijektion zueinander; im endlichen Fall: haben die gleicheAnzahl von Elementen. Diese Mächtigkeit bzw. Anzahl heißt Dimension von V (überK). Man schreibt dafür dimK V oder kurz dimV , wenn K im Kontext festgeschriebenist.

Beispiel2Ein Beweis für endliche-dimensionale Vektorräume folgt später aus dem Gauß-Verfahren; man musssich aber davon überzeugen, dass der Satz für das Gauß-Verfahren nicht gebraucht wird.

24

2.4. Lineare Abbildungen

• Rn hat die Dimension n (trivial an der Standardbasis)• Fn2 hat die Dimension n• R[x] als der Vektorraum der Polynome hat Dimension unendlich. Analog zur Stan-

dardbasis hier: (1, X,X2, X3, . . . )

• C hat als C−Vektorraum die Dimension 1, als R−Vektorraum die Dimension 2.• allgemeinen hat Cn die Dimension n als C−Vektorraum, 2n als R−Vektorraum• R ist ein Q−Vektorraum, aber niemand kennt eine Basis.

Seien v1, . . . , vn paarweise verschiedene Elemente. Dann ist {v1, . . . , vn} genau dann eineBasis von V , wenn es für jedes v ∈ V eine eindeutige Darstellung v = k1v1 + · · ·+ knvngibt.

Notation: KoordinatenDie Koeffizienten k1, . . . , kn werden dann häufig die Koordinaten von v bezüglich derBasis genannt.Beweis zu: Eindeutige Darstellbarkeit und BasisZunächst ist klar, dass genau dann für jedes v ∈ V solch eine Darstellung existiert,wenn {v1, . . . , vn} ein Erzeugendensystem ist. Angenommen nun v = k1v1+ · · ·+knvn =k′1v1+· · ·+k′nvn. Dann gilt 0 = (k1−k′1)v1+· · ·+(kn−k′n)vn, d. h. es gibt genau dann zweiverschiedene Darstellungen für einen Vektor, falls es eine nicht-triviale Linearkombinationder Null gibt, was nach Lemma 2.3 genau dann der Fall ist, wenn {v1, . . . , vn} nicht linearunabhängig ist.

Für unendlich viele Vektoren folgt, dass eine Teilmenge von V ohne Doppelnennungen{vi | i ∈ I} genau dann eine Basis von V ist, wenn es für jedes v ∈ V eine eindeutigeDarstellung v =

∑i∈I kivi mit ki ∈ K gibt. Hierbei gilt für die Summe die Konvention,

dass nur endlich viele Indizes ki 6= 0; die Summe steht also für eine endliche Linearkom-bination von Vektoren.


Seien V und W K-Vektorräume.

Definition: Lineare Abbildung/Vektorraum-HomomorphismusEine Abbildung φ : V → W ist eine K-lineare Abbildung oder ein K-Vektorraum-Homomorphismus, falls φ mit der Gruppenstruktur und der Skalarmultiplikation ver-träglich ist, d. h. falls für alle v, v1, v2 ∈ V und k ∈ K gilt 3:• φ(v1 +V v2) = φ(v1) +W φ(v2), φ(0V ) = 0W und φ(−V v) = −Wφ(v)

25

2. Vektorräume

• φ(k ·V v) = k ·W φ(v).Eine Abbildung φ : V → W ist ein K-Vektorraum-Isomorphismus, falls φ eine bijektiveAbbildung ist und sowohl φ als auch die Umkehrabbildung φ−1 K-linear sind.V undW heißen isomorph (als K-Vektorräume), falls ein K-Vektorraum-Isomorphismusφ : V →W existiert. Man schreibt dafür V ∼=W .

ErläuterungMan kann zeigen, dass die beiden Bedingungen φ(0) = 0 und φ(−v) = −φ(v) aus derAdditivität φ(v1 + v2) = φ(v1) + φ(v2) folgt, da (V,+) eine Gruppe ist.Ebenso kann man zeigen, dass die Umkehrabbildung einer bijektiven K-linearen Abbil-dung automatisch K-linear ist.Falls aus dem Kontext klar ist, um welchen Körper K es sich handelt, spricht man auchkurz von „linearen Abbildungen“ bzw. „Vektorraum-Homo- und -isomorphismen“.Notation: isomorphDer Begriff „isomorph“ und die Notation V ∼= W werden auch für andere Strukturenverwendet (z. B. Gruppen, Ringe). Wenn sie ohne nähere Spezifikation verwendet werden,setzen sie voraus, dass aus dem Kontext klar ist, welche Art von Strukturen betrachtetwerden, hier also K-Vektorräume. In diesem Fall spricht man auch noch kürzer von„Homomorphismen“ und „Isomorphismen“.

Sei {vi | i ∈ I} eine Basis von V ohne Doppelnennungen, und seien wi für i ∈ I beliebigeElemente von W . Dann gibt es genau eine lineare Abbildung φ : V →W mit φ(vi) = wifür alle i ∈ I. Außerdem ist φ ist dann ein Isomorphismus, wenn {wi | i ∈ I} eine Basisvon W ohne Doppelnennungen ist.

Beweis zu: Zusammenhang lineare Abbildung, Isomorphismus, BasisWenn es überhaupt solch eine lineare Abbildung gibt, muss φ(k1vi1 + · · · + knvin) =k1wi1 + · · · + knwin gelten. Da nach Satz 2.3 jedes v eine eindeutige Darstellung v =∑n

j1kjvij besitzt mit n ∈ N, kj ∈ K und paarweise verschiedenen ij ∈ I, kann man

durch φ(v) :=∑n

j1kjwij auch tatsächlich eine Abbildung V → W definieren. Man sieht

dann auch leicht ein, dass diese Abbildung tatsächlich linear ist.Das Bild von φ besteht dann aus den Vektoren φ(

∑nj1kjvij ) =

∑nj1kjφ(vij ) =

∑nj1kjwij ,

also ist φ genau dann surjektiv, wenn {wi | i ∈ I} ein Erzeugendensystem ist. Wenn{wi | i ∈ I} eine Basis ohne Doppelnennungen ist, folgt aus der Eindeutigkeit der Dar-stellung (Satz 2.3) auch die Injektivität von φ. Wenn umgekehrt φ bijektiv ist, muss zumeinen {wi | i ∈ I} eine Menge ohne Doppelnennungen sein (da φ injektiv), und zumandern gilt w =

∑nj1kjwij genau dann, wenn φ−1(w) =

∑nj1kjφ−1(wij ) =

∑nj1kjφ(vij ).

Aus der Eindeutigkeit der Darstellung bezüglich der Basis {vi | i ∈ I} folgt damit dieEindeutigkeit der Darstellung bezüglich {wi | i ∈ I}, d. h. wieder mit Satz 2.3, dass essich um eine Basis handelt.

26


ErläuterungEin Isomorphismus ist soviel wie eine Umbenennung der Elemente des Vektorraums undüberträgt alle aus der Vektorraumsstruktur definierbaren Eigenschaften. Insbesonderebildet er also eine Basis auf eine Basis ab und kann also nur zwischen Vektorräumengleicher Dimension bestehen!

Genau dann gibt es einen K-Vektorraum-Isomorphismus φ : V → W , wenn dimK V =dimKW .

Eine lineare Abbildung φ : V →W ist durch die Bilder einer Basis festgelegt.

Notation: angeordnete BasisEine angeordnete Basis (v1, . . . , vn) ist eine Basis {v1, . . . , vn} ohne Doppelnennungenzusammen mit einer festen Reihenfolge der Elemente (nämlich der Anordnung, in der dieElemente als Komponenten des n-Tupels auftreten).4

Definition: Vektorraum-IsomorphismusSei V ein n-dimensionaler K-Vektorraum. Dann wird durch jede angeordnete Basis B =(v1, . . . , vn) ein Vektorraum-Isomorphismus iB : V → Kn, vi 7→ ei festgelegt. Dabeiwird v = k1v1 + · · · + knvn auf seine Koordinaten (k1, . . . , kn) bezüglich der Basis Babgebildet. Umgekehrt bestimmt jeder Vektorraum-Isomorphismus i : V → Kn eineangeordnete Basis B von V , nämlich (i−1(e1), . . . , i

−1(en)), und es ist i = iB.

BeispielSei nun stets K = R (wobei abgesehen von der geometrischen Anschauung die überlegun-gen ebenso für jeden anderen Körper K gelten) und φ : V →W eine R-lineare Abbildungzwischen endlich-dimensionalen R-Vektorräumen V = Rn und W = Rm. Dann ist φ fest-gelegt durch die Bilder der Standardbasis {e1, . . . , en}. Es ist nun üblich und günstig, dieElemente von V und W als Spaltenvektoren zu schreiben. Wir betrachten zunächst dreiSpezialfälle:• Sei n = m = 1. Dann ist e1 = 1 und φ(1) = λ ∈ R. Es gilt also

φ(r) = φ(r · 1) = r · φ(1) = λ · r.

Die linearen Abbildungen R → R sind also genau die Multiplikationen mit reellenZahlen.

4Wenn man die Basiselemente durch die Variablen v1, . . . , vn bezeichnet, scheint eine Reihenfolge be-reits durch die Anordnung der Indizes gegeben zu sein; daher wirkt die Definition auf den erstenBlick vielleicht überflüssig. In einer konkreten Situation steht aber {v1, . . . , vn} z. B. für die Menge{(1, 1, 2), (−2, 3, 3), (2,−2, 0)}, auf der keine vorgegebene Reihenfolge erkennbar ist.

27

2. Vektorräume

• Sei n beliebig, m = 1 und φ(e1) = λ1, . . . , φ(en) = λn. Es gilt dann also:

φ(r1...

rn

) = φ( n∑i=1

riei)=

n∑i=1

riφ(ei) =

n∑i=1

riλi = λ1r1 + · · ·+ λnrn

Die Urbilder der Elemente der Bildraums R bilden parallele, zu (λ1, . . . , λn) senk-rechte Hyperebenen im Rn; man kann die Abbildung daher auffassen als die Projek-tion auf die Gerade durch den Ursprung in Richtung (λ1, . . . , λn), skaliert (d. h. ge-streckt oder gestaucht) um die Länge von (λ1, . . . , λn), also den Faktor

√λ21 + · · ·+ λ2n.

• Sei n = 1, m beliebig und φ(1) =

µ1...µm

. Dann gilt

φ(r) = φ(r · 1) = r · φ(1) = r ·

µ1...µm

=

rµ1...

rµm

Das Bild von φ ist also die Gerade durch den Punkt φ(1); die Abbildung φ bildetR unter Streckung bzw. Stauchung (Skalierung um die Länge von φ(1)) auf dieseGerade ab.• Seien schließlich n und m beliebig und

φ(e1) =

µ11µ21...

µm1

, φ(e2) =

µ12µ22...

µm2

, . . . , φ(en) =

µ1nµ2n...

µmn

Dann ist

φ(r1...

rn

) = φ( n∑i=1

riei)=

n∑i=1

riφ(ei) =

n∑i=1

ri

µ1i...

µmi

=

µ11r1 + · · ·+ µ1nrn...

µm1r1 + · · ·+ µmnrn

Um diese Abbildungen besser beschreiben zu können, führt man Matrizen ein.

Definition: MatrixEine (m × n)-Matrix über eine Körper K ist eine rechteckige Anordnung von mn Kör-perelementen aij für i = 1, . . . ,m („Zeilenindex“) und j = 1, . . . ,m („Spaltenindex“) inm Zeilen und n Spalten:

a11 a12 . . . a1na21 a22 . . . a2n...

......

am1 am2 . . . amn

28

2.5. Matrixmultiplikation

Die Menge aller (m×n)-Matrizen mit Einträgen ausK wird mitMatm×n(K) bezeichnet.

Notation:Wenn nicht explizit anders angegeben, werden die Einträge einer mit einem Großbuch-staben bezeichneten Matrix durch die entsprechenden Kleinbuchstaben beschrieben. Eshat also z. B. die Matrix C in der Regel Einträge cij , d. h.. C = (cij) i=1,...,n

j=1,...,m.

Definition: Operationen auf MatrizenMan definiert die Multiplikation einer (m × n)-Matrix mit einem Spaltenvektor aus Kn

durch die Formela11 a12 . . . a1na21 a22 . . . a2n...

......

am1 am2 . . . amn

·r1r2...rn

=

a11r1 + a12r2 + · · ·+ a1nrna21r1 + a22r2 + · · ·+ a2nrn

...am1r1 + am2r2 + · · ·+ amnrn

Durch diese Definition ergibt sich, dass die linearen Abbildungen Kn → Km genau dieMultiplikationen (von links) mit (m × n)-Matrizen sind, wobei die Spalten der Matrixdie Bilder der Standardbasisvektoren sind.Jeder linearen Abbildung φ : Kn → Km lässt sich also eindeutig die (m× n)-Matrix(

φ(e1)∣∣∣ . . . ∣∣∣φ(em))

zuordnen, wobei die φ(ei) hier Spaltenvektoren sind (was durch die senkrechten Stricheangedeutet sein soll). Man sagt dafür auch, dass die lineare Abbildung durch die Ma-trix dargestellt wird. Oft werde ich auch stillschweigend die (m × n)-Matrix A mit derAbbildung Kn → Km, v 7→ A · v identifizieren.


ErläuterungSeien φ : Kn → Km und ψ : Km → K l beides K-lineare Abbildungen, wobei φ durcheine (m × n)-Matrix A und ψ durch eine (l ×m)-Matrix B dargestellt wird. Man stelltnun zunächst leicht fest, dass ψ ◦ φ : Kn → K l ebenfalls K-linear ist.Beweis zu: Verknüpfung k-linearer AbbildungenMan rechnet nach, dass (ψ ◦φ)(v1+v2) = ψ(φ(v1+v2)) = ψ(φ(v1)+φ(v2)) = ψ(φ(v1))+ψ(φ(v2)) = (ψ ◦ φ)(v1) + (ψ ◦ φ)(v2) und (ψ ◦ φ)(k · v) = ψ(φ(k · v)) = ψ(k · φ(v)) =k · ψ(φ(v)) = k · (ψ ◦ φ)(v).

29

2. Vektorräume

ErläuterungAlso wird ψ ◦ φ durch eine (l× n)-Matrix C dargestellt. Wie hängt nun C mit A und Bzusammen? Wie kann man C aus A und B ausrechnen?

C ·

k1...kn

= ψ(φ(k1...

kn

)) = B ·(A ·

k1...kn

) =

= B ·

n∑i=1

a1iki

...n∑i=1

amiki

=

m∑j=1

b1in∑i=1

ajiki

...m∑j=1

blin∑i=1

ajiki

=

m∑j=1

n∑i=1

b1iajiki

...m∑j=1

n∑i=1

bliajiki

=

n∑i=1

(m∑j=1

b1jaji)ki

...n∑i=1

(m∑j=1

bljaji)ki

=

m∑j=1

b1jaj1 . . .m∑j=1

b1jajn

......

m∑j=1

bljaj1 . . .m∑j=1

bljajn

·k1...kn

Abbildung 2.1.: Matrizenmultiplikation

Dazu rechnet man C ·v = (B ·A) ·v aus (siehe Formelkasten in Abbildung 2.1) und stelltfest, dass der (i, k)-Eintrag der Matrix C sich berechnet als

cik =m∑j=1

bijajk =(bi1 . . . bim

)·

a1k...

amk

= i-te Zeile

. . . . . . . . .

bi1 . . . bim

. . . . . . . . .

·

j-te Spalte

... a1k [0em]...

......

...... amk

...

,wobei hierfür die i-te Zeile von B mit der k-ten Spalte von A so multipliziert wird, wieim letzten Abschnitt definiert (dies heißt auch Skalarprodukt des i-ten Zeilenvektors vonB mit dem k-ten Spaltenvektor von A, siehe Defintion 2.9).

Definition: MatrixproduktDas Matrixprodukt B · A einer (l × m)-Matrix B mit einer (m × n)-Matrix A ist die

(l × n)-Matrix C mit Einträgen cik =m∑j=1

bijajk.

Erläuterung

30


Das Matrixprodukt B · A ist also dann und nur dann definiert, wenn die Anzahl derSpalten von B gleich der Anzahl der Zeilen von A ist. Als Merkregel für die Dimensionender Matrizen kann man sich „(l × m) · (m × n) = (l × n)“ einprägen; der gemeinsamemittlere Term verschwindet also.Das Matrixprodukt B ·A ist genau so definiert, dass B ·A die Verknüpfung der durch Bund A beschriebenen linearen Abbildungen beschreibt, d. h. es gilt

(A ·B) · v = A · (B · v).

ErläuterungIn Definition 2.4 wurde das Produkt A·v einer (m×n)-Matrix A mit einem Spaltenvektorv ∈ Kn definiert. Nun ist solch ein Spaltenvektor v nichts anderes als eine (n×1)-Matrix.Somit ist also das Produkt A · v eigentlich doppelt definiert, aber man kann sich leichtanhand der Formeln davon überzeugen, dass beide Definitionen übereinstimmen.Dass dies kein Zufall ist, sieht man folgendermaßen ein: Man kann einen Vektor v ∈ Kn

mit der linearen Abbildung K1 → Kn, 1 7→ v identifizieren, deren Matrix gerade derSpaltenvektor v ist (die Abbildung ist also die Multiplikation mit v). Die Verküpfungdieser Abbildung mit der durch A beschriebenen linearen Abbildung ist dann die lineareAbbildungK1 → Km, welche 1 auf A(v) abbildet. Die Matrix dieser Abbildung berechnetsich als das Matrixprodukt von A und v, ist aber andererseits der Spaltenvektor A(v).Beispiel

•(1 2 34 5 6

)·

−1 00 21 3

=

(1 · (−1) + 2 · 0 + 3 · 1 1 · 0 + 2 · 2 + 3 · 34 · (−1) + 5 · 0 + 6 · 1 4 · 0 + 5 · 2 + 6 · 3

)=

(2 132 28

)• Die Verküpfung „Spiegelung an der y-Achse ◦ Spiegelung an der x-Achse“ wird

beschrieben durch (−1 00 1

)·(1 00 −1

)=

(−1 00 −1

),

ergibt also die Matrix der Punktpsiegelung am Urpsrung.• Eine Drehung um den Winkel α mit anschließender Drehung um den Winkel β

ergibt insgesamt eine Drehung um α+ β. Aus der Berchnung des Matrixproduktsergeben sich dadurch die Additionstheoreme für Sinus und Cosinus:(

cosβ − sinβsinβ cosβ

)·(cosα − sinαsinα cosα

) (cos(α+ β) − sin(α+ β)sin(α+ β) cos(α+ β)

)=

(cosα cosβ − sinα sinβ − sinα cosβ − cosα sinβcosα sinβ + sinα cosβ − sinα sinβ + cosα cosβ

)=

Definition: EinheitsmatrixDie zur Identitätsabbildung id : Kn → Kn gehörige Matrix ist die Einheitsmatriz ge-nannte (n×n)-Matrix In, deren Spalten (bzw. Zeilen) gerade die Standardbasisvektoren

31

2. Vektorräume

sind. Bei Nullmatrizen sind alle Einträge 0. Sie gehören zu den konstanten Nullabbil-dungen Kn → Km, v 7→ 0, und werden oft kurz, aber uneindeutig, ebenfalls mit 0geschrieben.

In =

1 0 . . . 00 1 . . . 0...

.... . .

...0 0 . . . 1

0 =

0 0 . . . 00 0 . . . 0...

......

0 0 . . . 0

ErläuterungKleiner Exkurs: Matrizenmultiplikationen spielen in vielen algorithmischen Anwendun-gen eine große Rolle; es ist daher interessant und nützlich, möglichst schnelle Verfahrenzu finden. Das Verfahren, das der Definition folgt, läuft für (n × n)-Matrizen in O(n3):pro Eintrag n Multiplikationen und n − 1 Additionen. Für große Matrizen gibt es aberschnellere Verfahren: Das erste solche stammt 1969 von Volker Strassen5 und läuft inO(n2,807). Er wurde nach und nach verbessert; den letzten großen Schritt lieferte 1990der Coppersmith-Winograd-Algorithmus6 mit O(n2,3737). Etwas überraschend kam 2010nochmals eine Verbesserung durch Andrew Stothers; der derzeit letzte Stand ist ein Al-gorithmus von Virginia Vassilevska Williams aus dem Jahre 2011 mit einer Laufzeit vonO(n2,3727). Als untere Schranke hat man sicher O(n2), da n2 Einträge auszurechnen sind;einige Forscher vermuten, dass diese untere Schranke optimal ist, also dass es Algorith-men in O(n2) gibt.(Zu bedenken ist dabei, dass kleinere Exponenten wegen der in der O-Notation versteck-ten Konstanten evtl. nur für sehr große Matrizen Verbesserungen bringen; außerdemsagt die Laufzeit nichst über die Güte des Algorithmus hinsichtlich Stabilität (Fehleran-fälligkeit) aus. Die Verbesserung des Exponenten in der dritten Nachkommastelle scheintzunächst vernachlässigbar, es ist aber bereits 10002,3737 − 10002,3727 ≈ 105; bei vielenMultiplikationen großer Matrizen kann sich also ein spürbarer Effekt ergeben.)

Die Matrizenmulitplikation ist assoziativ, aber i. a. nicht kommutativ (auch bei (n× n)-Matrizen untereinander. Die Einheitsmatrizen sind neutrale Elemente in dem Sinn, dassIm· = A und A·In = A für jede (m×n)-Matrix A gelten. Nullmatrizen sind absorbierendeElemente, d. h. es gilt 0 · A = A und A · 0 = A (für die Nullmatrix passender Größe, sodass also die Multiplikationen definiert sind).

Beweis zu: fehlende KommutativitätDie nicht vorhandene Kommutativität sieht man z. B. an(

0 10 1

)(1 10 1

)=

(0 10 1

)6=(1 10 1

)(0 10 1

)(0 20 1

).

5Volker Strassen (∗ 1936), ehemaligere Student der Universität Freiburg, zuletzt Professor in Konstanz.6nach Don Coppersmith (∗ ca. 1950) und Shmuel Winograd (∗ 1936), damals IBM.

32


Die anderen Eigenschaften folgen daraus, dass sie auf Seite der zugehörigen Abbildungengelten.

Eine (1 × 1)-Matriz (a11) kann man mit der Zahl a11 identifizieren. Die Multiplikationvon (1× 1)-Matrizen ist also kommutativ.

Notation: nilponente ElementeAbgesehen von der fehlenden Kommutativität gibt es noch andere Eigenschaften, welchedie Matrizenmultiplikation von der Multiplikation z. B. reeller Zahlen unterscheidet. Sogibt es sogenannte „nilpotente“ Elemente, das sind Matrizen A 6= 0 mit An = 0 für einn > 0. Zum Beispiel gilt:(

0 10 0

)2

=

(0 10 0

)·(0 10 0

)=

(0 00 0

)Insbesondere folgt für Matrizen aus A ·B = 0 nicht A = 0 oder B = 0!ErläuterungAbbildungen φ, ψ : Kn → Km kann man addieren durch (φ+ ψ)(v); = φ(v) + ψ(v) undskalar multiplizieren durch (k · φ)(v); = k · φ(v); sie bilden dadurch einen K-VektorraumAbb(Kn,Km), mit den linearen Abbildungen als Untervektorraum Lin(Kn,Km). Mankann nun die Addition und Skalarmultiplikation mittels der Identifikation von linea-ren Abbildungen und Matrizen in 2.4 (b) auf Matrizen ausdehnen, so dass die MengeMatm×n(K) zu einem zu Lin(Kn,Km) isomorphen K-Vektorraum wird. Man kann nunleicht nachrechnen, dass die folgende Definition die Matrizenaddition und die Skalarmul-tiplikation von Matrizen beschreibt:

Definition: SkalarmultiplikationSeien A und B (m× n)-Matrizen über K und k ∈ K. Dann ist

A+B =

a11 . . . a1n...

...am1 . . . amn

+

b11 . . . b1n...

...bm1 . . . bmn

:=

a11 + b11 . . . a1n + b1n...

...am1 + bm1 . . . amn + bmn

k ·A = k ·

a11 . . . a1n...

...am1 . . . amn

:=

k · a11 . . . k · a1n...

...k · am1 . . . k · amn

Es gelten nun die folgenden Eigenschaften:

33

2. Vektorräume

(a) Die Matm×n(K) bilden einen mn-dimensionalen, zu Lin(Kn,Km) isomorphen K-Vektorraum; insbesondere sind die (m × n)-Matrizen bezüglich der Addition eine kom-mutative Gruppe, deren neutrales Element die (m×n)-Nullmatrix ist. Die Standardbasisbesteht aus Matrizen Eij , deren (i, j)-Eintrag 1 ist und alle anderen Einträge 0. Jede Auf-zählung der Standardbasis liefert einen Vektorraum-IsomorphismusMatm×n(K)→ Kmn.(b) Es gelten die Distributivgesetze, d. h immer, wenn die Operationen definiert sind,gilt A · (B1 +B2) = (A ·B1) + (A ·B2) bzw. (B1 +B2) ·A = (B1 ·A) + (B2 ·A).(c) Die quadratischen (n × n)-Matrizen Matn×n(K) bilden mit Matrizenaddition und-multiplikation einen nicht-kommutativen Ring mit Eins In.(d) k · In ist die (n × n)-„Diagonalmatrix“ mit Einträgen k auf der Hauptdiagonalevon links oben nach rechts unten und Einträgen 0 an allen anderen Stellen. Es giltdann k · A = (k · In) · A = A · (k · In). Die Skalarmultiplikation vertauscht mit derMatrizenmultiplikation, d. h. es gilt k · (A · B) = (k · A) · B = A · (k · B) (sofern dasProdukt A×B definiert ist).

Beweis zu: Eigenschaften MatrizenManche Eigenschaften sind offensichtlich, weil sie auf der Seite der Abbildungen gelten;die anderen rechnet man anhand der Formeln nach.

2.6. Basiswechsel

Definition: invertierbare MatrizenEine (n×n)-Matrix A über K heißt invertierbar , wenn die zugehörige lineare Abbildungφ : Kn → Kn invertierbar ist, d. h. wenn eine (n× n)-Matrix A−1 existiert (nämlich dieMatrix zu φ−1) mit

A ·A−1 = A−1 ·A = In.

Aus Folgerung 2.4 ergibt sich, dass A genau dann invertierbar ist, wenn die Spaltenvek-toren von A, also φ(e1), . . . , φ(en), eine Basis von Kn bilden. Die Umkehrabbildung φ−1

ist dann durch φ(ei) 7→ ei festgelegt.Offensichtlich ist A−1 selbst wieder invertierbar und es gilt (A−1)−1 = A.

ErläuterungZiel dieses Abschnitts ist es nun, lineare Abbildungen zwischen beliebigen endlich di-mensionalen Vektorräumen durch Matrizen zu beschreiben. Da beliebige Vektorräumei. a. keine ausgezeicheten Standardbasen haben, wird es – abhängig von gewählten Ba-sen – verschiedene darstellenden Matrizen geben, und ein Hauptproblem wird sein zuverstehen, wie diese miteinander zusammenhängen.

34

2.6. Basiswechsel

Definition: BasiswechselSei V ein n-dimensionaler und W ein m-dimensionaler K-Vektorraum und φ : V →W eine K-lineare Abbildung. Sei außerdem v1, . . . , vn eine angeordnete Basis B von Vund w1, . . . , wm eine angeordnete Basis B′ von W . Nach Folgerung 2.4 legen B und B′

Isomorphismen iB : V → Kn und iB′ : W → Km fest, so dass sich folgendes Diagrammergibt:

Kn iB←− V φ−→WiB′−→ Km

Die Matrix von φ bezüglich der Basen B und B′ wird mit B′φB bezeichnet und ist dieMatrix der Abbildung iB′ ◦ φ ◦ i−1B : Kn → Km, d. h. die Spaltenvektoren sind dieKoordinaten von φ(v1), . . . , φ(vn) bezüglich der Basis B′.Falls V =W und B = B′, schreibt man kurz φB für BφB.

Seien V,W,X K-Vektorräume mit angeordneten Basen B,B′, B′′ und seien φ : V → Wund ψ :W → X lineare Abbildungen. Dann gilt

B′′(ψ ◦ φ)B = (B′′ψB′) · (B′φB)

Beweis zu: lineare Abbildungen und Basen

B′′(ψ ◦ φ)B ist die Matrix von iB′′ ◦ (ψ ◦ φ) ◦ i−1B = iB′′ ◦ ψ ◦ i−1B′ ◦ iB′ ◦ φ ◦ i−1B , was

gerade das Produkt der Matrix von iB′′ ◦ψ ◦ i−1B′ mit der Matrix von iB′ ◦φ ◦ i−1B ist, also(B′′ψB′) · (B′φB).

Sei wieder φ : V → W lineare, und seien B1, B2 angeordnete Basen von V , B′1, B′2angeordnete Basen von W . Dann gilt

B′2φB2 = (B′2 idWB′1

) · (B′1φB1) · (B1 idV B2)

Spezialfall V =W und B′i = Bi: Dann gilt

φB2 = (B2 idV B1) · φB1 · (B1 idV B2

) = (B1 idV B2)−1 · φB1 · (B1 idV B2

).

Beweis zu: Berechnung BasiswechselDer erste Teil folgt direkt aus dem Satz, da φ = idW ◦ φ ◦ idV . Wegen (B2 idV B1

) ·(B1 idV B2

) = B2(idV ◦idV )B2 = B2 idV B2= IdimV folgt auch die rechte Seite der Gleichung

im Spezialfall.Notation: BasiswechselmatrizenDie Matrizen B′2

idWB′1und B1 idV B2

heißen Basiswechselmatrizen. Sie sind also stetsinvertierbar mit (B1 idV B2

)−1 = B2 idV B1.

35

2. Vektorräume

Wie rechnet man die Basiswechselmatrizen aus? Ist die Basis B1 = (v1, . . . , vn) von Vgegeben und ist v′ der j-te Vektor in B2, so muss man also die Koeffizienten aij mitv′ = a1jv1 + · · · + anjvn berechnen; diese stehen als j-te Spalte in der Basiswechselma-trix B1 idV B2

. Wenn die Basiselemente als Vektoren in Kn gegeben sind (also mit ihrenKoordinaten bezüglich der Standardbasis), dann ergibt die Gleichung ein lineares Glei-chungssystem, das z. B. nach dem Gauß-Verfahren (siehe folgender Abschnitt ??) gelöstwerden kann. Auch das Invertieren von Matrizen geschieht am besten mit dem Gauß-Verfahren. Besonders einfach ist es, wenn V = Kn und B1 die Standardbasis ist: Dannbesteht die Basiswechselmatrix B1 idV B2

aus den Vektoren von B2 als Spaltenvektoren.

Beispiel

•

B1 : e1, e2, e3 (Standardbasis)B2 : v1 = (0, 0, 1), v2 = (0, 1, 1), v3 = (1, 1, 1)

W = K2

B′1 : w1 = (1, 1), w2 = (1,−1)B′2 : w

′1 = (1, 0), w′2 = (1, 1)

B1idB2 =

0 0 10 1 11 1 1

B2idB1 = (B1idB2)

−1 =

a11 a12 a13. . . . . . . . .. . . . . . a33

=

0 −1 1−1 1 01 0 0

Lösen von ei = a1iv1 + a2iv2 + a3iv3:

e1 = v3 − v2e2 = v2 − v1e3 = v1

B2′ idB′1 =

(0 21 −1

)B1′ idB′2 =

(1/2 11/2 0

)= (B2′ idB′1)

−1

36

2.6. Basiswechsel

w2 = 2w′1 − w′22w1 − w2 hat die Koordinaten

(2−1

)bezüglich B′1

2w1 − w2 hat die Koordinaten(

021− 1

)(21

)=

(−23

)bezüglich B′2

Probe bezüglich Standardbasis 2w1 − w2

2

(11

)(1−1

)=

(13

)−2w′1 + 3w′2 = −2

(10

)+ 3

(11

)=

(13

)ψ : V →W : B′1φB1 =

(3 1 20 5 4

)B2′ψB′1 = (B′2idB′1) · (B

′1ψB1) · (B1idB2)

=

(0 21 −1

)(3 1 20 5 4

)0 0 10 1 11 1 1

=

(0 10 83 −4 −2

)0 0 10 1 11 1 1

=

(8 18 18−2 −6 −3

)

v3 = e1 + e2 + e3 hat die Koordinaten

111

bezüglich der Standardbasis

001

bzgl.B2

(3 1 20 5 4

)111

=

(69

)bzgl. B′1, bzgl. Standardbasis

(15−3

)(

8 18 18−2 −6 −3

)001

=

(18−3

)bzgl. B′2, bzgl. Standardbasis

(15−3

)

(Fehlender Inhalt: Formatierung dieses Beispiels anpassen)• Ein weiteres Beispiel findet sich bei der Diagonalisierung einer Drehung über den

komplexen Zahlen auf Seite 39.

37

2. Vektorräume

• Was passiert, wenn der Basiswechsel in einer Umordnung der Basis besteht?Wenn B die Basis (v1, . . . , vn) ist, wird eine Umordnung beschrieben durch einePermutation der Indizes, also eine Bijektion σ : {1, . . . , n} → {1, . . . , n}, wobei dieneu angeordnete Basis Bσ dann (vσ(1), . . . , vσ(n)) ist.7

Die Basiswechselmatrix M(σ) := Bσ idB hat nun Einträge 1 an den Stellen (i, σ(i))und 0 an allen anderen Stellen. Solche Matrizen heißen auch Permutationsmatrix :Sie sind quadratische Matrizen, die in jeder Zeile und in jeder Spalte genau eine1 haben und sonst überall 0. Die Inverse zu M(σ) ist M(σ−1), also die Permu-tationsmatrix mit Einträge 1 an den Stellen (σ(i), i), also die an der Diagonalengespiegelte Matrix.

Beispiel: Sei n = 3 und σ(1) = 2, σ(2) = 3, σ(3) = 1. Dann ist

M(σ) = Bσ idB =

0 1 00 0 11 0 0

und M(σ−1) = B idBσ =

0 0 11 0 00 1 0

.

(Kleiner Vorgriff auf Abschnitt 4.1: Die Permutationen von {1, . . . , n} bilden eineGruppe Sym(n), die symmetrische Gruppen, und die Abbildunge σ 7→M(σ) ist einGruppenhomomorphismus von Sym(n) in die multiplikative Gruppe der invertier-baren (n× n)-Matrizen.)

Spezialfall: Transpositionen sind spezielle Permutatione, die nur zwei Elemente ver-tauschen (und damit selbst-invers sind). Die Transposition τ , welche die Elementei und j vertauscht, schreibt man auch (ij). Der Lesbarkeit halber schreibe ichM(ij)

für M((ij)). Es gilt dann (alle nicht aufgeführten Einträge sind gleich 0):

M(ij) =M−1(ij) =

1 . . .1

11 . . .

11

1 . . .1

i-te Zeile

j-te Zeile

Es ist also etwa (zweite und dritte Zeile und Spalte jeweils vertauschen!)

M(23) ·

1 2 3 45 6 7 89 0 1 23 4 5 6

·M(32) =

1 3 2 49 1 0 25 7 6 83 5 4 6

.

7Bei dieser Version gibt σ also an, welcher Vektor an die jeweilige Stelle gesetzt wird, d. h. σ(2) = 3bedeutet, dass v3 in der neu angeordneten Basis an zweiter Stelle steht. Alternativ könne man alsneu angeordnete Basis (vσ−1(1), . . . , vσ−1(n)) nehmen. Dann würde σ angeben, an welche Stelle derjeweilige Vektor geschoben wird, d. h. σ(2) = 3 würde bedeuten, dass v2 in der neu angeordnetenBasis an dritter Stelle käme.

38

2.6. Basiswechsel

ErläuterungEin Ziel der linearen Algebra besteht darin, zu einer gegebenen linearen Abbildung φ :V → V eine Basis B zu finden, so dass die Matrix φB möglichst „schön“ ist. Hierzugibt es eine ganze Reihe von Ergebnissen über sogenannte Normalformen von Matrizen.„Besonders schön“ ist eine Matrix in Diagonalgestalt, also von der Formλ1 0

. . .0 λn

.

Für die Basisvektoren v1, . . . , vn gilt dann φ(vi) = λvi und für beliebige Vektoren φ(a1v1+· · ·+ anvn) = λa1v1 + · · ·+ λanvn.

Definition: EigenvektorEin Vektor v 6= 0 heißt Eigenvektor der linearen Abbildung φ : V → V zum Eigenwertλ ∈ K, falls φ(v) = λv.

ErläuterungDer Idealfall besteht also darin, dass man zu einer linearen Abbildung eine Basis ausEigenvektoren findet. (Wenn man weiß, dass λ ein Eigenwert ist und φ durch die MatrixA beschrieben ist, kann man die Eigenvektoren durch Lösen des linearen Gleichungssys-temes A · x = λx mit Unbekannten Koeffizienten für x finden. Jedes skalare Vielfacheeines Eigenvektors (6= 0) ist wieder ein Eigenvektor. Die Eigenwerte wiederum kann manals Nullstellen des sogenannten charakteristischen polynoms bestimmen.)

Im Allgemeinen findet man aber keine Basis aus Eigenvektoren. Es gibt zwei Hinderungs-gründe.

Erläuterung(1) Drehungen im R2 haben i. a. keine Eigenvektoren, wie geometrisch sofort ersichtlichist. (Nur wenn der Drehwinkel ein ganzzahliges Vielfaches von 180◦ ist, gibt es Eigenvek-toren in R2.)Diese Problem lässt sich dadurch beheben, dass man den Körper erweitern, hier zu denkomplexen Zahlen C. So hat z. B. die Drehung um 90◦ bezüglich der Standardbasis dieMatrix

(0 −11 0

)– ohne Eigenvektoren in R2 – aber als Matrix über den komplexen Zahlen

sind ( 1i ),(

1−i)zwei linear unabhängige Eigenvektoren zu den Eigenwerten −i und i, d. h.

bezüglich der aus diesen beiden Vektoren gebildeten Basis ergibt sich die Diagonalform(−i 00 i

).

Man kann an diesem Beispiel noch einmal schön den Basiswechsel nachvollziehen: Daeine der basen die Standardbasis ist, besteht eine der beiden Basiswechselmatrizen ausden Vektoren der anderen Basis als Spalten und die andere Basiswechselmatrix ist deren

39

2. Vektorräume

Inverse: (1 1i −i

)und

(1 1i −i

)−1=

(12

12i

12 − 1

2i

);

man kann auch nachrechnen, dass diese Matrix tatsächlich die Koeffizienten der Stan-dardbasis bezüglich der neuen Basis enthält, da(

10

)=

1

2

(1i

)+

1

2

(1−i

)und

(01

)=

1

2i

(1i

)− 1

2i

(1−i

).

Auch den Basiswechsel lässt sich nachrechnen; es gilt:(1 1i −i

)(−i 00 i

)(12

12i

12 − 1

2i

)=

(0 −11 0

)und

(12

12i

12 − 1

2i

)(0 −11 0

)(1 1i −i

)=

(−i 00 i

)

(2) Scherungen im R2 haben i. a. (bis auf skalare Vielfache) nur einen Eigenvektor.Diese Problem kann nicht durch Vergrößerung des Körpers behoben werden; eine Sche-rung wie z. B. ( 1 1

0 1 ) bildet einen Vektor v = ae1 + be2 auf ae1 + b(e2 + e1) ab. Man kannleicht nachrechnen, dass nur die skalaren Vielfachen von e1 Eigenvektoren sind, also wennb = 0.Man kann zeigen, dass die über C der einzige Hinderungsgrund ist; man kann durchgeeignete Basiswahl die sogenannte Jordan’sche Normalform erreichen, bei der die Matrixaus Teilmatrizen der folgenden Form ausgebaut ist:

λ 1 0 . . . 0

0. . . . . . . . .

....... . . . . . . . . 0...

. . . . . . 10 . . . . . . 0 λ

2.7. Lineare Gleichungssysteme

ErläuterungEin lineares Gleichungssystem mit m Gleichungen und n Unbekannten hat die Form

a11x1 + a12x2 + · · ·+ a1nxn = b1

. . .

am1x1 + am2x2 + · · ·+ amnxn = bm

wobei aij ∈ K Körper (in der Regel R). Dies entspricht in Matrixschreibweise:a11 . . . a1n. . .am1 . . . amn

x1. . .xn

=

b1. . .bm

40


Dabei wird die erste Matrix als A bezeichnet, die zweite als x und die dritte als b. DasGleichungssystem ist folglich A · x = b. Falls ψ : Kn → Km die durch A beschriebenelineare Abbildung ist, dann sind die Lösungen des Gleichungssystems genau die v ∈ Kn

mit ψ(v) = b.

Definition: Kern und BildSei φ : V →W eine lineare Abbildung. Das Bild von φ ist definiert als Bild(φ) := {φ(v) |v ∈ V }; der Kern von φ als Kern(φ) := {v ∈ V | φ(v) = 0}.Das Bild wird ebenso für beliebige Abbildungen definiert. Bild und Kern werden auch(nach dem englischen image und kernel) als im(φ) und ker(φ) bezeichnet.

Notation: UrbilderIst f : A → B eine beliebige Abbildung und b ∈ B, so bezeichnet f−1[b] die Menge{a ∈ A | f(a) = b}. Meist wird dafür f−1(b) geschrieben. Falls f bijektiv ist und dieUmkehrfunktion f−1 : B → A existiert, so wird die Schreibweise mit runden Klammernaber zweideutig. Mit der exakteren Schreibweise gilt f−1[b] = {f−1(b)}.

(a) Kern und Bild einer linearen Abbildung φ : V → W sind Unterräume von V bzw.W .(b) Falls w0 = φ(v0) ∈ Bild(φ), so ist φ−1[w0] = v0+Kern(φ) := {v0+ v | v ∈ Kern(φ)}.Mit anderen Worten, es gilt g φ(v) = φ(v′) ⇐⇒ v − v′ ∈ Kern(φ).

Beweis zu: Eigenschaften von Kern und Bild(a) Da φ(0V ) = 0W ist 0V ∈ Kern(φ) und 0W ∈ Bild(φ).Seien w1 = φ(v1) und w2 = φ(v2) in Bild(φ). Dann sind w1 + w2 = φ(v1 + v2) undk · w1 = φ(k · v1) ebenfalls in Bild(φ), also ist Bild(φ) ein Untervektorraum.Seien v1, v2 ∈ Kern(φ). Dann ist φ(v1 + v2) = φ(v1) + φ(v2) = 0 + 0 = 0 und φ(k · v1) =k · φ(v1) = k· == 0. Also ist auch Kern(φ) ein Untervektorraum.(b) Es ist φ(v) = φ(v′) ⇐⇒ φ(v − v′) = φ(v)− φ(v′) = 0 ⇐⇒ v − v′ ∈ Kern(φ).ErläuterungFür ein w ∈ W gibt es also zwei mögliche Fälle: Entweder w /∈ Bild(φ) und φ−1[w] = ∅;oder w ∈ Bild(φ) und φ−1[w] ist eine sogenannte „Nebenklasse“ v+Kern(φ) von Kern(φ)mit φ(v) = w.Natürlich ist φ surjektiv, wenn Bild(φ) = W (gilt für beliebige Abbildungen φ : V →W ).

φ ist injektiv ⇐⇒ Kern(φ) = {0} ⇐⇒ dimKern(φ) = 0.Wenn W endlich-dimensional ist, so ist φ surjektiv ⇐⇒ dimBild(φ) = dimW .

41

2. Vektorräume

Beispiel(Fehlender Inhalt: Beispiel)

Sei φ : V →W linear. Dann gilt dimKern(φ) + dimBild(φ) = dimV .

Beweis zu: Dimensionssatz8 Sei l = dimKern(φ) und n = dimV und wähle eine Basis {v1, . . . , vl} von Kern(φ).Diese ist eine lineare unabhängige Teilmenge von V , kann also zu einer maximal linearunabhängigen Teilmenge {v1 . . . , vl, vl+1, . . . , vn} ergänzt werden, d. h. zu einer Basis vonV . Zu zeigen ist also n − l = dimBild(φ), indem gezeigt wird, dass φ(vl+1), . . . , φ(vn)eine Basis ohne Doppelnennungen von Bild(φ) ist.Sei w = φ(a1v1 + · · · + anvn) ∈ Bild(φ). Dann ist w = a1φ(v1) + · · · + anφ(vn) =al+1φ(v1+1) + · · · + anφ(vn), da φ(v1) = · · · = φ(vl) = 0. Also ist φ(vl+1), . . . , φ(vn) einErzeugendensystem von Bild(φ).Zu zeigen bleibt die lineare Unabhängigkeit, mit Lemma 2.3: Sei also 0 = bl+1φ(vl+1) +· · ·+ bnφ(vn) = φ(bl+1vl+1+ · · ·+ bnvn) ∈ Kern(φ). Da v1, . . . , vl eine Basis von Kern(φ)ist, gibt es b1, . . . , bl mit bl+1vl+1 + · · · + bnvn = b1v1 + · · · + blvl, oder (−b1)v1 + · · · +(−bl)vl+ bl+1vl+1+ · · ·+ bnvn = 0. Aus der linearen Unabhängigkeit der Basis v1, . . . , vnfolgt nun aber b1 = · · · = bn = 0.

Wenn φ : V → W bijektiv ist, dann gilt dimV = dimW . Wenn dimV = dimWendlich ist, dann ist φ genau dann injektiv, wenn surjektiv (und damit genau dann, wennbijektiv).

Beweis zu: Dimension und bijektive AbbildungenWenn φ : V → W bijektiv ist, so ist dimKern(φ) = 0, da φ injektiv, und dimBild(φ) =W , da φ surjektiv, also Bild(φ) = W . Es folgt dimV = dimKern(φ) + dimBild(φ) =0 + dimW .Wenn dimV = dimW endlich und φ injektiv, dann ist dimW = dimV = dimKern(φ)+dimBild(φ) = 0 + dimBild(φ), also φ surjektiv.Wenn dimV = dimW endlich und φ surjektiv, dann ist dimKern(φ) = dimV−dimBild(φ)= dimW − dimBild(φ) = 0, also φ injektiv.

Definition: Lineares GleichungssystemEin lineares Gleichungssystem (über einem Körper K, meist K = R) besteht aus linearenGleichungen

a11 · x1 + a12 · x2 + · · ·+ a1n · xn = b1...

...am1 · x1 + am2 · x2 + · · ·+ amn · xn = bm

8Für endlich-dimensionales V ; der Beweis funktioniert mit den entsprechenden Modifikationen aberauch für unendlich-dimensionale Vektorräume.

42


mit aij , bi ∈ K und Unbekannten x1, . . . , xn. Eine Lösung des Gleichungssystems bestehtaus Werten k1, . . . , kn ∈ K, welche gleichzeitig alle m Gleichungen erfüllen.Das zugehörige homogene (lineare) Gleichungssystem ist

a11 · x1 + a12 · x2 + · · ·+ a1n · xn = 0...

...am1 · x1 + am2 · x2 + · · ·+ amn · xn = 0

.

ErläuterungOffenbar kann man das lineare Gleichungssystem in einer Matrix zusammenfassen als

A · x =

a11 a12 . . . ain...

......

am1 am2 . . . amn

·x1...xn

=

b1...bm

= b

Eine Lösung des homogenen Gleichungssystems A · x = 0 ist dann ein Vektor aus demKern von A; die Lösungsmenge des homogenen Gleichungssystems (d. h. die Menge allerLösungen) ist genau Kern(A).ErläuterungFür das allgemeine Gleichungssystem A · x = b gibt es die beiden bereits besprochenenMöglichkeiten: Entweder b /∈ Bild(A) und es gibt keine Lösung, oder b ∈ Bild(A) und dieLösungsmenge besteht aus einer Nebenklasse c+Kern(A), wobei c irgendeine Lösung desGleichungssystems ist. Um die Lösungsmenge des Gleichungssytems zu bestimmen, mussman also eine sogenannte spezielle Lösung c finden – sofern sie existiert! – und den Kernvon A bestimmen. Ist v1, . . . , vl eine Basis des Kerns, so besteht die Lösungsmenge alsoaus allen Vektoren der Form c+ k1v1+ · · ·+ klvl mit ki ∈ K („die allgemeine Lösung“).

Definition: Rang einer MatrixDer Rang einer (m×n)-Matrix A, rg(A), ist die Dimension des Bildes von A als linearerAbbildung Kn → Km, d. h. die Dimension des von den Spalten A · e1, . . . , A · en von Aerzeugten Unterraums.

Nach Definition ist rg(A) 6 m und = m genau dann, wenn A surjektiv ist. Außerdemgilt n = dimKern(A) + rg(A) nach Satz 2.7.

Falls A die Matrix eines homogenen linearen Gleichunssystemes mit m Gleichungen undn Unbekannten ist, dann ist die Dimension des Lösungsraums n− rg(A).

43

2. Vektorräume

2.7.1. Das Gauß-Verfahren zum Lösen linearer Gleichungssysteme

ErläuterungDie Idee des Verfahrens besteht darin, das Gleichungssystem bzw. die Matrix durch eineReihe „elementarer Umformungen“, die die Lösungsmenge nicht oder in einer kontroli-ierten Weise ändern, in eine „schöne Form“ zu bringen, aus der man die Lösungsmengeleicht errechnen kann.

Definition: elementare UmformungenHier betrachten wir drei Arten von elementaren Umformungen. Jede der Umformungenentspricht der Multiplikation von links mit einer invertierbaren Matrix M . Dann gilt

A · v =M−1MA · v = b ⇐⇒ MA · v =M · b

und wegen M · 0 = 0 ist insbesondere Kern(MA) = Kern(A), d. h. die Lösungsmengeändert sich nicht, wenn A und c gleichermaßen umgeformt werden.

(1) Vertauschung der i-ten mit der j-ten Gleichung bzw.Vertauschung der i-ten mit der j-ten Zeile der Matrix A und des Vektors b.

Dies entspricht der Multiplikation von links mit der Matrix M(ij) = M−1(ij) (sieheSeite 38).

(2) Addition des k-fachen der j-ten Gleichung zur i-ten Gleichung bzw.Addition des k-fachen der j-ten Zeile der Matrix A und des Vektors b zur i-tenZeile.

Dies entspricht der Multiplikation von links mit der Matrix Eij(k) = Im+k·Eij . (Eijist die Standardbasenmatrix aus Satz 2.5). Man sieht leicht ein, dass Eij(k)−1 =Eij(−k).

(3) Multiplikation der i-ten Gleichung mit k 6= 0 bzw.Multiplikation der i-ten Zeile der Matrix A und des Vektors b mit k 6= 0.

Dies entspricht der Multiplikation von links mit der Matrix Ei(k) = Im+(k−1)·Eii.Man sieht wiederum leicht ein, dass Ei(k)−1 = Ei(k

−1).

ErläuterungErgänzend können auch Operationen auf den Spalten der Matrix vorgenommen wer-den (z. B. Vertauscheungen der Spalten, die dann den entsprechenden Vertauschungender Unbekannten entsprechen). Diese sind aber nur zur Verbesserung von Algorithmenhinsichtlich Stabilität notwendig.

Definition: Zeilenstufenform einer Matrix, Pivot-ElementeEine Matrix A ist in Zeilenstufenform, falls es j1 < · · · < jr gibt, so dass a1j1 6=

44


0, . . . , arjr 6= 0 undaij = 0, falls

i > ik und j 6 jkoder j < j1

oder i > ir

.

Die Elemente aiji heißen Pivot-Elemente, die Spalten j1, . . . , jr Pivot-Spalten.

ErläuterungSchematisch angedeutet sieht eine Zeilenstufenform (mit r = 3) wie folgt aus; ∗ steht fürbeliebige Elemente:

0 a1j1 ∗ ∗ ∗ ∗ ∗0 0 a2j2 ∗ ∗ ∗ ∗0 0 0 0 0 a3j3 ∗0 0 0 0 0 0 00 0 0 0 0 0 0

(a) Jede Matrix kann durch elementare Umformungen der Art (1) und (2) in Zeilenstu-fenform gebracht werden.(b) Jede invertierbare Matrix kann durch elementare Umformungen der Art (1) und (2)in eine Diagonalmatrix und durch elementare Umformungen der Art (1), (2) und (3) indie Identitätmatrix überführt werden.

Beweis zu: Mächtigkeit der elementaren Umformungen (Gauß-Verfahren, Gauß-Jordan-Verfahren)Für (a) gibt es den in Abbildung 2.2 dargestellten Algorithmus, das sogenannte Gauß-Verfahren. Die Matrix wird spaltenweise von links nach rechts und zeilenweise von obennach unten so abgearbeitet, dass die gewünschten Nullen auftreten. Betrachtet wird im-mer nur der Teil unterhalb der aktuellen Stelle: Ein eventuell vorhandener Eintrag 6= 0 inder Spalte wird ggf. durch Zeilenvertauschung an die betrachtete Stelle gebracht; durchdie Addition eines passenden Vielfachens der Zeile werden unterhalb der betrachtetenStelle Nullen erzeugt. (Ein formaler Korrektheitsbeweis unterbleibt hier).(b) Durch das Gauß-Verfahren bringt man zunächst die Matrix in Zeilenstufenform. Sieist genau dann invertierbar, wenn die Zeilenstufenform Dreiecksform hat, d. h. wenn diePivot-Elemente die Diagonalelemente a11, . . . , ann sind. Man kann auf diese Matrix nundas Gauß-Verfahren gewissermaßen „punktgespiegelt“, also spaltenweise von rechts nachlinks und zeilenweise von unten nach oben anwenden, und erhält eine Diagonalmatrix(d. h. aii 6= 0, aber aij = 0 für alle i 6= j.) Durch Umformungen der Art (3) kann manschließlich die Diagonaleinträge auf 1 bringen. diese Verfahren heißt manchmal auchGauß-Jordan-Verfahren.Beispiel(Fehlender Inhalt: Beispiel)

45

2. Vektorräume

Input: (m× n)-Matrix A. Setze i = 1, j = 1.

Ist aij 6= 0 ?

- Ja: ersetze Zeile k = i+ 1, . . . , n durch „Zeile k − akjaij· Zeile i“

ersetze i durch i+ 1 und j durch j + 1

- Nein: Gibt es ein l > i mit alj 6= 0 ?

- Ja: vertausche Zeile i mit Zeile l (für das kleinste l)

�

- Nein: ersetze j durch j + 1

Falls i > m oder j > n: Ende

�

Abbildung 2.2.: Gauß-Verfahren

Input: (n× n)-Matrix A. Führe zunächst das Gauß-Verfahren durch.

Sind alle aii 6= 0 ?

- Nein: die Matrix ist nicht invertierbar- Ja: Setze j = n

ersetze Zeile k = 1, . . . , j − 1 durch „Zeile k − akjajj· eile j“

ersetze Zeile j durch „Zeile 1ajj· Zeile j“

ersetze j durch j − 1

�

Falls j < 1: Ende

Abbildung 2.3.: Gauß–Jordan-Verfahren

Was kann mit dem Gauß-Verfahren berechnet werden?Sei stets E eine invertierbare Matrix, die A in Zeilenstufenform bringt, d. h. E ist eineMatrix Ek ·. . .·E1, wobei E1, . . . , Ek Matrizen zu elementaren Umformungen sind, welchenach dem Gauß-Verfahren A in eine Matrix Ek · . . . ·E1 ·A in Zeilenstufenform umformen.

• Den Rang einer Matrix berechnen:Der Rang der Matrix ist die Anzahl der Pivot-Elemente in der Zeilenstufenform.• Testen, ob eine Matrix invertierbar ist:

46


Eine Matrix ist genau dann invertierbar, wenn sie quadratisch ist und der Rangmit der Anzahl der Zeilen/Spalten übereinstimmt.• Eine spezielle Lösung eines linearen Gleichungssystems ausrechnen:

Man bringt das Gleichungssystem in Zeilenstufenform EA · x = E · b und löstdie Gleichungen von unten nach oben auf („Rückwärteinsetzen“). Sind Unbekanntedurch eine Gleichung und die vorherigen Festsetzungen nicht eindeutig bestimmt,setzt man einen beliebigen Wert (z. B. 0) ein.• Eine Basis des Kerns bestimmen:

Man bringt das homogene Gleichungssystem in Zeilenstufenform EA ·x = E ·0 = 0.Ist der Rang der Matrix gleich n (= Anzahl der Unbekannten), so ist Kern ={0}, die Basis also die leere Menge. Andernfalls löst man die Gleichungen vonunten nach oben durch Rückwärteinsetzen auf. Für jede Unbekannte, die nichteindeutig festgelegt ist, bekommt man einen Basisvektor des Kerns, indem mandiese Unbekannte auf 1 setzt und alle andern dann nicht festgelegten Unbekanntenauf 0.• Eine Basis des Bilds bestimmen:

Spalten Aei1 , . . . , Aeil von A sind genau dann linear unabhängig, wenn die entspre-chenden Spalten EAei1 , . . . , EAeil der Matrix in Zeilenstufenform linear unabhän-gig sind. Also bilden die Spalten von A, die Pivot-Spalten von EA sind, eine Basisdes Bildes.• Eine Menge linear unabhängiger Vektoren zu einer Basis ergänzen:

Man fügt die Vektoren als Spalten zu einer (m × n)-Matrix A zusammen und be-stimmt eine Basis des Bildes der (m×(n+m))-Matrix (A | Im) wie oben beschrieben.alternativ: Man fügt die Vektoren als Zeilen zu der (n×m)-Matrix AT zusammenund bringt sie in Zeilenstufenform. Diejenigen Standardbasisvektoren ei, für die ikeine Pivot-Spalte ist, ergänzen die gegebenen Vektoren zu einer Basis.• Das Inverse einer Matrix berechnen:

Die elementaren Umformungen, welche A nach dem Gauß-Jordan-Verfahren in dieIdentitätsmatrix umformen, formen gleichzeitig die Identitätsmatrix in die Inversevon A um: falls E ·A = In, so ist E · In = A−1.

Mathematische Folgerungen

Definition: Transponierte MatrixDie Transponierte AT einer (m× n)-Matrix A = (aij) i=1,...,n

j=1,...,mist die „an der Diagonalen

gespiegelte“ (n×m)-Matrix (aji) j=1,...,mi=1,...,n

.

Beispiel

47

2. Vektorräume

A =

(1 2 34 5 6

)AT =

1 42 53 6

Man sieht auch leicht aus der Multiplikationsformel, dass (A · B)T = BT · AT. Ins-besondere ist die Transponierte einer invertierbaren Matrix selbst invertierbar mit(AT)−1 = (A−1)T.

rg(A) = rg(AT).

Beweis zu: Rang der transponierten MatrixMan sieht, dass der Satz für Matrizen in Zeilenstufenform gilt. Da Isomorphismen dieDimension bewahren, ändert die Multiplikation von rechts oder links mit einer invertier-baren Matrix nicht den Rang einer Matrix. Sei also E · A in Zeilenstufenform für eininvertierbares E. Dann gilt: rg(A) = rg(E ·A) = rg((E ·A)T) = rg(AT ·ET) = rg(AT).Beweis zu: Beweis Dimensionssatz (alternativ)Aus dem Gauß-Verfahren gewinnt man auch einen Beweis für Satz 2.3 im endlich-dimen-sionalen Fall. Allerdings müsste man sich noch davon überzeugen, dass der Satz fürdas Gauß-Verfahren nicht gebraucht wurde (und man muss aufpassen, dass man keineBegriffe oder Argumente verwendet, welche bereits auf der Dimension beruhen, wie z. B.den Rang).

Wenn ein Vektorraum V eine Basis mit endlich vielen Elementen besitzt, dann habenalle Basen von V die gleiche Anzahl von Elementen.

Beweis zu: Größe der BasenAngenommen V hat Basen mit m und mit n Elementen, m < n. über die eine Basis ist Visomorph zu Km; man kann also annehmen, dass V = Km. Nun stellt man die (m× n)-Matrix A auf, deren Spalten die Vektoren der Basis mit n Elementen sind. Diese sindnach Annahme linear unabhängig, also müssen auch die Spalten der in Zeilenstufenformgebrachten Matrix linear unabhängig sein. In der Zeilenstufenform sieht man aber, dassmaximal m Spalten linear unabhängig sein können: Widerspruch.

2.8. Determinanten

ErläuterungIdee: Wie kann man die Volumenänderung auf einen Quader durch eine lineare AbbildungR3 → R3 messen?

48

2.8. Determinanten

mathematische Vorgehensweise in diesem Fall: Man möchte das Problem mit einem neu-en Konstrukt, den Determinanten lösen. Man stellt die Eigenschaften fest, die die De-terminante (= orientierte Volumenänderung) haben soll und stellt fest, dass es nur eineFunktion mit diesen Eigenschaften geben kann. Dann kann man Formeln angeben.Notation: DeterminanteDie Determinante det(A) einer Matrix A wird durch ersetzten der äußeren Klammerndurch senkrechte Striche angegeben.

Eigenschaften der Determinante (A sei eine n× n−Matrix):• det(A) = 0⇔ A nicht invertierbar• det(id) = 1

• det(A ·B) = det(A) · det(B)

• Vertauscht man in einer Matrix die Zeilen i und j oder die Spalten i und j, soist die zugehörige Determinante das negative der Determinante der ursprünglichenMatrix.• Addiert man auf eine Spalte oder Zeile der Matrix eine Zeile oder Spalte so kann

man das Ergebnis auf als die Addition der beiden Determinanten der Matrizen,die sich nur in der entsprechenden Spalte/Zeile unterscheiden berechnen: z.B..

det(

1 2 34 5 67 8 9

) = det(

1 1 34 1 67 1 9

) + det(

1 1 34 4 67 7 9

)

• Multipliziert man eine Zeile/Spalte einer Matrix mit einem Skalar kann die Deter-minante auch als Multiplikation der ursprünglichen Determinante mit dem Skalarberechnet werden.• det(A) = det(AT )

• det(A ·B) = det(A) · det(B)

Berechnung der Determinante• für kleine n lässt sich eine einfache Formel angeben:

– n = 1: det(a11) = a11

– n = 2: det((a11 a12a21 a22

)) = a11 · a22 − a21 · a12

– n = 3: det(

a11 a12 a13a21 a22 a23a31 a32 a33

)

= a12a22a33 + a12a23a31 + a13a21a31 − a31a22a13 − a32a23a11 − a33a21a12• Formel von Lagrange (A quadratisch) det(A) =

∑σ=Sym({1,...,n})

sgn(σ) · a1σ(1) ·

a1σ(2) . . . anσ(n)

• Entwicklungssatz det(A) =n∑j=1

(−1)i+jaijdet(Aij), wobei Aij die (n − 1) × (n −

49

2. Vektorräume

1)−Matrix ist, die aus A durch Streichen der i − ten Zeile und j − ten Spalteentsteht.• Mit Gaußverfahren auf Dreiecksmatrix bringen und Diagonale multiplizieren (Bei

Vertauschen von zwei Zeilen ändert sich das Vorzeichen), Addition des k-facheneiner Zeile auch eine andere ändert die Determinante nicht.• (Fehlender Inhalt: Formel für Inverse)

2.9. Längen, Winkel, Skalarprodukt

ErläuterungIn diesem Abschnitt soll stetsK = R sein; alle betrachteten Vektorräume seien über R. Essollen nun die geometrisch anschaulichen Begriffe der Länge eines Vektors, des Abstandeszweier Vektoren und des Winkels zwischen zwei Vektoren eingeführt werden. Dabei ist dasVorgehen – ähnlich wie schon bei der Determinante – wie folgt: Man findet eine Formelfür die Berechnung, die in den Fällen der Dimension 1, 2 und 3 das Richtige tut und dieEigenschaften besitzt, die man von den Begriffen erwartet. In den höherdimensionalenFällen, wo eine direkte geometrische Anschauung fehlt, definiert man die Begriffe danndurch diese Formel.

Länge und Abstand

Definition: Länge, AbstandDie Länge eines Vektors v = (v1, . . . , vn) ∈ Rn) ist

‖v‖ :=√v21 + · · ·+ v2n.

Der Abstand ( oder die Distanz) zweier Vektoren ist

d(v, w) := ‖v − w‖.

ErläuterungEs gilt also ‖v‖ = d(v, 0). Im R1 ist ‖v‖ = |v|; in R2 und R3 sieht man mit dem Satz vonPythagoras, dass die Definition den gewöhnlichen Längenbegriff wiedergibt.

50


Eigenschaften von Länge und Abstand Für alle u, v, w ∈ Rn und k ∈ R gilt:

Positivität: ‖v‖ ≥ 0 d(v, w) ≥ 0

‖v‖ = 0⇔ v = 0 d(v, w) = 0⇔ v = w

Symmetrie: ‖v‖ = ‖−v‖ d(v, w) = d(w, v)

Dreiecksungleichung: ‖v + w‖ ≤ ‖v‖+ ‖w‖ d(v, w) ≤ d(v, u) + d(u,w)

Skalierung: ‖r · v‖ = |r| · ‖v‖ d(r · v, r · w) = |r| · d(v, w)

ErläuterungNeben diesem gewöhnlichen Längenbegriff (der auch „euklidische Norm“ oder „2-Norm“‖v‖2 genannt wird), gibt es im Mehrdimensionalen auch weitere Längenbegriffe, etwa die„1-Norm“ ‖v‖1 = |v1|+· · ·+|vn| oder die „Maximumsnorm“ ‖v‖∞ := max

{|v1|, . . . , |vn|

},

die ebenfalls alle oben aufgeführten Eigenschaften aufweisen.

Skalarprodukt, Winkel, Orthogonalität

ErläuterungDer Winkel zwischen zwei Vektoren wird üblicherweise über das Skalarprodukt ausge-rechnet. Das Skalarprodukt selbst misst keine ganz elementare geometrische Größe wieLänge oder Winkel, sondern beides in Kombination. Im R2 wird das Skalarprodukt vonv = (v1, v2) und w = (w1, w2) durch die Formel 〈v, w〉 = v1w1 + v2w2 berechnet; diegeometrische Interpretation dieser Größe ist: „‖v‖ mal ‖w‖ mal Cosinus des Winkelszwischen v und w“.Da in diesem Fall die geometrische Interpretation der Formel viel weniger ersichtlichist als bei der Länge von Vektoren, soll sie auf zwei Arten erklärt werden (die zwar imwesentlichen übereinstimmen, aber Verschiedenes voraussetzen).Erläuterung

Erste Methode Da es bei dem Winkel nicht auf die Längen der Vektoren ankommt,kann man o.E. annehmen, dass v und w Länge 1 haben (indem man sie durch v

‖v‖ bzw.w‖w‖

ersetzt; den Fall v = 0 oder w = 0 kann man außer Acht lassen, da 〈0, w〉 = 〈v, 0〉 = 0).Falls v = e1 = (1, 0), so ist w1 gerade der Cosinus des eingeschlossenen Winkels zwischene1 und w (und w2 ist die (orientierte) Höhe der von e2 und w aufgespannten Raute,also im wesentlichen deren Flächeninhalt, da die Grundseite e1 Länge 1 hat). Winkelsollten unter Drehungen invariant sein; man kann daher den allgemeinen Fall auf diesenspeziellen Fall durch die Drehung von v auf e1 zurückführen. Also ist der Cosinus desWinkels zwischen v und w die erste Koordinate von(

v1 v2−v2 v1

)·(w1

w2

)=

(v1w1 + v2w2

v1w2 − v2w1

).

51

2. Vektorräume

Man sieht auch, dass die zweite Komponente die orientierte Höhe der Fläche der von v

und w aufgespannten Raute ist, also die Volumenveränderung der Abbildung(v1 w1

v2 w2

)angibt. Also stimmt neben der Formel für das Skalarprodukt auch die Determinanten-formel im R2.Erläuterung

Zweite Methode Geht man von der gewünschten geometrischen Interpretation des Ska-larprodukts aus, so ist klar, dass 〈v, k · v〉 = k · ‖v‖2 sein muss und dass 〈v, v〉 = 0 geltenmuss, wenn v und w senkrecht aufeinander stehen. Sicher steht v = (v1, v2) senkrecht auf(−v2, v1) und allen seinen Vielfachen. Nun schreibt man (nachrechnen durch Ausmulti-plizieren!)

(w1, w2) =v1w1 + v2w2

v21 + v22· (v1, v2) +

v1w2 − v2w1

v21 + v22· (−v2, v1).

Der linke Summand gibt dann gerade die orthogonale Projektion von w auf v an; dieLänge dieses Vektors mal die Länge von v ist dann gerade v1w1 + v2w2.ähnliche überlegungen kann man für den R3 anstellen (oder man führt, indem man diebeiden Vektoren zunächst in die {e1, e2}-Ebene dreht, den dreidimensionalen auf denzweidimensionalen Fall zurück).

Definition: StandardskalarproduktDas (Standard-)Skalarprodukt im Vektorraum Rn ist die folgende Abbildung 〈·, ·〉: Rn ×Rn → R:

〈v, w〉 := (v1, . . . , vn) ·

w1...w2

= v1w1 + v2w2 + · · ·+ vnwn =n∑i=1

viwi.

Eigenschaften des Skalarprodukts Für alle v, v′, w, w′ ∈ Rn und r ∈ R gilt:

Positivität: 〈v, v〉 = ‖v‖2 =≥ 0

〈v, v〉 = 0⇔ v = 0

Symmetrie: 〈v, w〉 = 〈w, v〉Bilinearität: 〈v + v′, w〉 = 〈v, w〉+ 〈v′, w〉〈v, w + w′〉 = 〈v, w〉+ 〈v, w′〉

〈r · v, w〉 = r · 〈v, w〉〈v, r · w〉 = r · 〈v, w〉

d. h. das Skalarprodukt ist sowohl im ersten als auch im zweiten Argument eine lineareAbbildung.

52


[Cauchy-Schwarz9] Seien v, w ∈ Rn, dann gilt

|〈v, w〉| ≤ ‖v‖ · ‖w‖

oder (quadriert) (∑i=1

viwi

)2

≤∑i=1

v21 ·∑i=1

w21.

Für v 6= 0 und w 6= 0 gilt

−1 ≤ 〈v, w〉‖v‖ · ‖w‖

=

⟨v

‖v‖,w

‖w‖

⟩≤ 1;

somit findet man einen eindeutigen Winkel α ∈ [0, 2π] mit

〈v, w〉 = ‖v‖ · ‖w‖ · cos(α).

Per Definition nennt man α den zwischen v und w eingeschlossenen Winkel ∠(v, w).10

Beweis zu: eingeschlossener WinkelDer Fall w = 0 ist klar (beide Seiten ergeben 0); sei also w 6= 0. Dann ist

0 ≤⟨v − 〈v, w〉

‖w‖2· w, v − 〈v, w〉

‖w‖2· w⟩

= 〈v, v〉 − 2 · 〈v, w〉‖w‖2

〈v, w〉+ 〈v, w〉2

‖w‖4〈w,w〉

=1

‖w‖2(〈v, v〉 · 〈w,w〉 − 2 · 〈v, w〉2 + 〈v, w〉2

)=

1

‖w‖2(〈v, v〉 · 〈w,w〉 − 〈v, w〉2

)Daraus folgt also 0 ≤ 〈v, v〉 · 〈w,w〉 − 〈v, w〉2 bzw. 〈v, w〉2 ≤ 〈v, v〉 · 〈w,w〉 = ‖v‖2 · ‖w‖2,also nach Wurzelziehen das gewünschte Ergebnis.

Insbesondere gilt also:

〈v, w〉 = 0 ⇐⇒ cos∠(v, w) istπ

2oder

3

2π (d. h. 90◦ oder 270◦)

⇐⇒ v und w stehen senkrecht aufeinander.

9Augustin Louis Cauchy (1789-1857), Hermann Amandus Schwarz (1843-1921)10Dieser Begriff ist nicht orientiert, d. h. der Winkel zwischen v und w ist gleich dem Winkel zwischen

w und v. Dem entspricht, dass der Cosinus eine gerade Funktion ist, also cos(α) = cos(−α) ist.

53

2. Vektorräume

ErläuterungIn den Dimensionen 1, 2 und 3 stimmt dies also mit dem anschaulichen geometrischenBegriff überein; in den höheren Dimensionen ist es eine sinnvolle Verallgemeinerung. Inabstrakten n-dimensionalen Räumen gibt es dagegen kein Standard-Skalarprodukt, alsoauch keinen natürlichen Winkelbegriff. Durch die Wahl einer Basis kann man aber dasSkalarprodukt des Rn übertragen. Das Standard-Skalarprodukt geht axiomatisch davonaus, dass die Standardbasis eine sogenannte Orthonormalbasis ist, also die BasisvektorenLänge 1 haben und paarweise aufeinander senkrecht stehen. Darauf beruhen alle weiterenLängen- und Winkelbestimmungen. Die übertragung des Standard-Skalarprodukts desRn auf einen abstrakten n-dimensionalen Vektorraum durch Wahl einer Basis bedeutet,dass man diese Basis zur Orthonormalbasis erklärt.

Sei v 6= 0, dann ist die orthogonale Projektion von w auf v gleich

wv =〈w, v〉‖v‖

· v

‖v‖=〈w, v〉〈v, v〉

· v.

Wenn v1, . . . , vn eine Orthonormalbasis ist, dann gilt

w =

n∑i=1

〈w, vi〉 · vi.

Beweis zu: OrthonormalbasisWenn man

⟨∑ni=1〈w, vi〉·vi, vj

⟩mit Hilfe der Bilinearität des Skalarprodukts ausrechnet,

ergibt sich sofort der zweite Teil. Der erste Teil folgt aus der geometrischen Interpretationdes Skalarprodukts (bzw. durch Skalieren und Ergänzen von v zu einer Orthonormalba-sis).

[Verallgemeinerter Satz des Pythagoras11; Cosinussatz]Für v, w ∈ Rn gilt:

‖v + w‖2 = ‖v‖2 + 2 · 〈v, w〉+ ‖w‖2.

Insbesondere gilt ‖v+w‖2 = ‖v‖2+ ‖w‖2 genau dann, wenn 〈v, w〉 = 0, also wenn v undw senkrecht aufeinander stehen.

Beweis zu: CosinussatzEinfach ausrechnen:

‖v +w‖ =n∑i=1

(vi +wi)(vi +wi) =

n∑i=1

v2i +

n∑i=1

w2i + 2 ·

n∑i=1

viwi = ‖v‖2 + 2〈v, w〉+ ‖w‖2

11Pythagoras (ca. 570 bis ca. 510 v.Chr.)

54


Orthogonale Abbildungen

Definition: orthogonale lineare AbbildungEine lineare Abbildung φ : Rn → Rn heißt orthogonal , wenn φ das Skalarprodukt erhält,wenn also 〈φ(v), φ(w)〉 = 〈v, w〉 für alle v, w ∈ Rn gilt.12

Eine (n × n)-Matrix A heißt orthogonal, wenn die zugehörige lineare Abbildung ortho-gonal ist.

Definition: OrthonormalbasisEine Basis v1, . . . , vn des R ist eine Orthonormalbasis, wenn

〈vi, vj〉 :=

{1 falls i = j

0 falls i 6= j.

ErläuterungMan rechnet leicht nach, dass

〈Av,w〉 =n∑j=1

(n∑i=1

ajivi

)· wj =

n∑i=1

vi ·

n∑j=1

ajiwj

= 〈v,ATw〉.

Die folgenden Aussagen sind äquivalent für eine (n× n)-Matrix über Rn:(a) A ist orthogonal;(b) A ist invertierbar und A−1 = AT;(c) Ae1, . . . , Aen ist eine Orthonormalbasis.

Beweis zu: Orthoganalität und MatrizenKlar ist, dass eine orthogonale Abbildung eine Orthonormalbasis auf eine Orthonormal-basis abbilden muss, also gilt (a)⇒(c). Der (i, j)-Eintrag von AT ·A ist genau 〈Aei, Aej〉,also ist Ae1, . . . , Aen genau dann eine Orthonormalbasis, wenn AT · A = Id, also wenn(b) gilt. Schließlich folgt aus (b), dass 〈Av,Aw〉 = 〈v,ATAw〉 = 〈v, w〉, also dass Aorthogonal ist.Beispiel

Drehungen im R2 sind orthogonal:(cosα − sinαsinα cosα

)−1=

(cosα sinα− sinα cosα

). Ebenso sind

Spiegelungen orthogonal. Drehungen und Spiegelungen sind die einzigen orthogonalen12Achtung: Die orthogonale Projektion aus Satz 2.9 ist keine orthogonale Abbildung.

55

2. Vektorräume

Abbildungen der Ebene (dabei sind die Drehungen orientierungserhaltend, die Spiege-lungen nicht).ErläuterungOrthogonale Abbildungen sind längentreu, d. h. ‖Av‖ = ‖v‖ für alle v, und winkeltreu,d. h. ∠(Av,Aw) = ∠(v, w) für alle v, w. Aus A−1 = AT folgt det(A)−1 = det(AT) =det(A) und somit detA = ±1. Orthogonale Abbildungen sind also zudem volumentreu,allerdings nur im unorientierten Sinn; die Orientierung kann sich ändern (wie man amBeispiel der Spiegelungen sieht).Scherungen sind Beispiele von volumenerhaltenden Abbildungen, die weder längen- nochwinkeltreu sind; Streckungen (aller Vektoren um den gleichen Faktor) sind Beispiele vonwinkeltreuen Abbildungen, die weder längen- noch volumentreu sind. Man kann aberzeigen, dass längentreue Abbildungen bereits orthogonal sind (dies folgt unmittelbar ausdem verallgemeinerten Satz von Pythagoras). Ebenso sind Abbildungen, die winkel- undvolumentreu sind, schon orthogonal.13

13Winkelerhaltend heißt, dass Ae1, . . . , Aen eine Orthogonalbasis ist, also AT ·A eine Diagonalbasis ist.Betrachtet man den Winkel zwischen ei und ei + ej , sieht man schnell, dass alle Diagonaleinträgegleich sein müssen. Da die Abbildung Determinante ±! hat, müssen die Diagonaleinträge = 1 sein.

56

3. Lineare Codes

3.1. Lineare Codes

ErläuterungIn der Codierungstheorie geht es um folgende Situation bzw. Problematik: Informationenwerden in Folgen von Symbolen aufgeschrieben bzw. festgehalten. Man sagt dazu auch,dass die Informationen „codiert“ werden, z. B. durch Morse-Zeichen oder durch Zahlen-folgen im ASCII-Code. Bei der übermittlung von Nachrichten (z. B. übertragung durchFunk oder Kabel oder Speicherung der Information über längere Zeiträume) könnenübertragungsfehler passieren oder Teile der Information verloren gehen.Kann man nun die Codierung so wählen, dass übertragungsfehler erkannt und teilweisekorrigiert werden können, und die Informationsübermittlung dennoch möglichst effizi-ent geschieht? Es geht also darum, in die Codierung eine Redundanz einzubauen. Dieeinfachste Art der Redundanz besteht darin, die Nachricht mehrfach zu wiederholen.Stimmen die empfangenen Informationen nicht überein, so weiß man, dass übertragungs-fehler eingetreten sein. Indem man gegebenenfalls die am häufigsten empfangene Versionals die richtige ansieht, kann man u.U.. auch übertragungsfehler ausgleichen. Die Codie-rung durch Wiederholung ist aber insofern ineffizient, als sich die Länge der übermitteltenNachricht (und damit Zeit und Kosten) vervielfacht. Die Anforderung der Effizienz be-zieht sich aber auch auf die Durchführung von Codierung, Decodierung und die eventuelleFehlerkorrektur: hierfür sollen schnelle Algorithmen vorliegen.Konkret betrachtet man folgende Situation: Man verfügt über ein endliches Alphabet(eine Symbolmenge) A mit q Elementen und nimmt Wörter der festen Länge n überA, d. h. Elemente (a1, . . . , an) von An, um Nachrichten zu codieren. Die Menge diesern-Tupel wird auch der Hamming-Raum1 H(n,A) genannt, bzw. H(n, q), wenn es nur aufdie Anzahl der Elemente von A ankommt.Oft nimmt man als Alphabet eine endliche Gruppe oder einen endlichen Körper, etwaFq, da die algebraische Struktur beim Ver- und Entschlüsseln helfen kann und geschickteCodierungen ermöglicht. H(n,Fq) = Fnq ist dann ein n-dimensionaler Vektorraum überFq. Besonders häufig ist der Fall q = 2 mit F2 = {0, 1}. Der Hamming-Raum H(8,F2) istzum Beispiel die Menge der möglichen Bytes. Den Hamming-Raum H(4,F2) kann manmit den hexadezimalen Ziffern identifizieren.BeispielCodes mit Redundanzen• Im ursprünglichen ASCII-Code wurden Zeichen durch ein Byte (a1, . . . , a8), also

1Richard Hamming (1915-1998)

57

3. Lineare Codes

ein 8-Tupel über F2, codiert. Dabei bildeten die ersten sieben Ziffern a1, . . . , a7die eigentliche Information: als Binärzahl gelesen geben sie die Stelle des codiertenZeichens (Buchstabe, Ziffer, Satz- oder Steuerungszeichen) in der Liste der ASCII-Zeichen an. Die letzte Ziffer a8 war eine Kontrollziffer, welche den sogenanntenparity check durchführte: a8 war so gewählt, dass a1 + · · ·+ a8 = 0 in F2 gilt. DerCode erkennt, wenn an einer Stelle ein übertragungsfehler passiert, da dann diePrüfrechnung nicht mehr stimmt. Geht bei der übertragung eine Stelle verloren,kann man sie errechnen.• Der alte ISBN-Code bestand aus einer neunstelligen Dezimalzahl, die man als 9-

Tupel (b1, . . . , b9) über F11 aufgefasst und um eine Prüfziffer b10 ∈ F11 so ergänzthat, dass∑10

i=0 i · bi = 0 in F11 gilt. (Das Element 10 in F11 wurde übrigens X geschrie-ben.)Dieser Code erkennt eine falsche Ziffer und auch Vertauschungen von zwei Ziffern.(„Erkennen“ heißt dabei, dass die Prüfrechnung nicht mehr stimmt.)• Der aktuelle ISBN-Code ist ein 13-Tupel über Z/10Z, wobei wieder die letzte Ziffer

eine Prüfziffer ist, die so gewählt wird, dass b1 + 3b2 + b3 + 3b4 + · · · + b13 = 0 inZ/10Z gilt. Dieser Code erkennt wieder eine falsche Ziffer, aber nur noch gewisseVertauschungen.

Fehler und die Hamming-Metrik

ErläuterungAnschaulich gesprochen ist ein Code gut, wenn er besonders viele Fehler erkennt odersogar deren Korrektur zulässt. Um dies zu präzisieren, muss man festlegen, was Fehlersind und wie man ihre Anzahl misst. Im üblichen Setting legt man dazu fest, dass esnur um die Anzahl der Stellen geht, die nicht übereinstimmen. Eine Vertauschung vonzwei (verschiedenen) Ziffern zählt also als zwei Fehler, da anschließend zwei Stellen nichtmehr stimmen. Insbesondere werden alle Stellen als gleichwertig gezählt (während manz. B. bei Dezimalzahlen Fehler in den höheren Stellen als gewichtiger ansehen würde alsin den niederen Stellen) und alle Elemente des Alphabets werden ebenfalls untereinanderals gleichwertig gezählt (d. h. es ist gleichermaßen ein einziger Fehler, ob z. B. 2 statt 1empfangen wird oder 9 statt 1).Mathematischer wird dies in der Hamming-Metrik präzisiert:

Definition: Hamming-Distanz/Hamming-MetrikFür v = (v1, . . . , vn) und w = (w1, . . . , wn) in H(n,A) definiert man den Hamming-Abstand (die Hamming-Metrik) als d(v, w) :=

∣∣ {i | vi 6= wi}∣∣.

Die Hamming-Metrik ist eine Metrik auf H(n,A), d. h. es gilt:

58

3.1. Lineare Codes

• Positivität: d(v, w) > 0 und d(v, w) = 0 ⇐⇒ v = w

• Symmetrie: d(v, w) = d(w, v)

• Dreiecksungleichung: d(u, v) 6 d(u, v) + d(v, w).Falls (A,+) eine (kommutative) Gruppe ist, dann gilt zusätzlich:• Translationsinvarianz: d(v, w) = d(v + u,w + u),

insbesondere d(v, w) = d(v − w, 0) = d(−w,−v)Falls A ein K-Vektorraum ist, dann gilt außerdem:• Invarianz unter Skalarmultiplikation: d(v, w) = d(kv, kw) für k ∈ K \ {0}

Beweis zu: Eingeschaften der Hamming-MetrikDie ersten beiden Eigenschaften folgen unmittelbar aus der Definition. Die Dreiecks-ungleichung sieht man aus der Transitivität der Gleichheit: Wenn ui 6= wi, dann giltui 6= vi oder vi 6= wi. Offensichtlich gilt d(v, w) > d(f(v), f(w)) für eine beliebige Abbil-dung f : H(n,A)→ H(n,A), also d(v, w) > d(f(v), f(w)) > d(f−1(f(v)), f−1(f(w))) =d(v, w) für bijektive f . Damit folgt die Invarianz unter Translationen und unter Skalar-multiplikation, da die Abbildungen v 7→ v + u und v 7→ k · v für k 6= 0 bijektiv sind(Umkehrabbildungen sind v 7→ v − u und v 7→ k−1 · v).ErläuterungWährend die übliche euklidische Metrik ‖v − w‖ im Rn ebenfalls translationsinvariantist, gilt dort ‖rv− rw‖ = |r| · ‖v−w‖. Die Invarianz der Hamming-Metrik unter Skalar-multiplikation ist also eine „ungeometrische“ Eigenschaft.

Falls (A,+) eine kommutative Gruppe ist und p eine Primzahl, dann ist A genau dannein Fp-Vektorraum, wenn a+ · · ·+ a︸︷︷︸

p mal

= 0 für alle a ∈ A gilt. Die Skalarmultiplikation ist

dann durch m · a = a+ · · ·+ a︸︷︷︸m mal

gegeben und es gilt −a = (p− 1) · a.

Insbesondere folgt daraus: Wenn C ⊆ Fnp unter Addition abgeschlossen ist, dann ist Cbereits ein Untervektorraum!

Definition: Eigenschaften von Codes(a) Ein Code ist eine Teilmenge von H(n,A) bzw. H(n, q). Man spricht von einem „Codeder Länge n über A“ bzw. einem „q-ären Code der Länge n“. Der Minimalabstand desCodes ist min

{d(v, w)

∣∣ v, w ∈ C, v 6= w}.

(b) Ein linearer Code ist ein Untervektorraum von Fnq . Das Gewicht von v ∈ C ist d(v, 0)und das Minimalgewicht des Codes ist min

{d(v, 0)

∣∣ v ∈ C, v 6= 0}.

(c) Ein Code C erkennt (mindestens) e Fehler , falls der Minimalabstand größer als e ist.(d) Ein Code C korrigiert (mindestens) e Fehler , falls es zu jedem v ∈ H(n,A) höchstensein c ∈ C gibt mit d(v, c) 6 e.

59

3. Lineare Codes

Notation: Beschreibung linearer CodesLineare Codes werden meist durch zwei oder drei Parameter beschrieben: als „(q-äre)[n, k]-Codes“ oder „(q-äre) [n, k, d]-Codes“. Dann ist stets n die Länge der Wörter, k =dimC und d das Minimalgewicht. Es gilt |C| = qk bzw. k = logq |C|.2

ErläuterungWegen d(v, w) = d(v − w, 0) ist das Minimalgewicht eines linearen Codes gleich seinemMinimalabstand. Unmittelbar aus der Definition sieht man auch:

(a) Ein Code mit Minimalabstand d erkennt d− 1 Fehler und korrigiert⌊d−12

⌋Fehler.

(b) Ein Code, der e Fehler korrigiert, erkennt 2e Fehler und hat Minimalabstand min-destens 2e+ 1.

Beispiel

• Der alte ISBN-Code ist ein 11-ärer Code der Länge 10, der einen Fehler erkenntund keinen korrigiert.• Der ursprüngliche ASCII-Code ist ein binärer linearer [8, 7, 2]-Code, der also einen

Fehler erkennt und keinen korrigiert.• Der Wiederholungscode {(x, x, x) | x ∈ Fq} ⊆ H(3, q) ist ein q-ärer linearer [3, 1, 3]-

Code, der zwei Fehler erkennt und einen korrigiert.

Definition: BallDer Ball vom Radius e um v ist3

Be(v) :={w ∈ H(n,A)

∣∣ d(v, w) 6 e}.

Die Anzahl der Elemente eines solchen Balles kann man ausrechnen durch

∣∣Be(v)∣∣ = e∑i=0

(n

i

)(q − 1)i;

hierbei durchläuft i die möglichen Abstände zu v; der Binomialkoeffizient gibt die Anzahlder Möglichkeiten für die i Stellen, an denen die Abweichungen auftreten; q − 1 ist fürjede Stelle die Anzahl der alternativen Elemente des Alphabets.

2Manche Autoren bevorzugen, statt der Dimension eines Codes C an zweiter Stelle die Anzahl derElemente von C anzugeben.

3In der Analysis sind Bälle üblicherweise als offene Bälle definiert, d. h. man fordert „< e“ statt „6 e“.Dies ist in der diskreten Situation hier nicht besonders sinnvoll.

60

3.2. Gütekriterien und Schranken für Codes

Für q = 2 gilt insbesondere

∣∣Be(c)∣∣ = (n0

)+

(n

1

)+ · · ·+

(n

e

).

Es gilt nun offensichtlich:

• C erkennt genau dann e Fehler, wenn c′ /∈ Be(c) für c, c′ ∈ C, c 6= c′.• C korrigiert genau dann e Fehler, wenn die Bälle Be(c) für c ∈ C paarweise disjunkt

sind.


Beispielmotivierendes Beispiel:Zwei Beispiele für einen 1-fehlerkorrigierenden CodeAusgangslage: Man hat als eigentliche Information Wörter der Länge 4 über F2 (alsoetwa die Binärdarstellung von hexadezimalen Zeichen). Man möchte den Code nun z. B.durch Anhängen von Prüfziffern so verändern, dass er einen Fehler korrigiert.

Code 1 Die „naive“ Methode besteht darin, das Ausgangswort dreifach zu senden. Wör-ter aus H(4,F2) werden also codiert als Wörter in H(12,F2), nämlich v = (v1, v2, v3, v4)als v� v� v := (v1, v2, v3, v4, v1, v2, v3, v4, v1, v2, v3, v4).C1 =

{v� v� v

∣∣ v ∈ H(4,F2)}ist dann ein binärer [12, 4, 3]-Code: Die Wortlänge ist 12,

die Dimension 4 (da dimH(4,F2) = 4) und das Minimalgewicht 3, d. h. der Code erkenntzwei Fehler und korrigiert einen.Dieser Code ist aber nicht besonders effizient: die Raumgröße ist |H(12,F2)| = 212 =4.096. Es gibt 16 Codewörter, die mit Ihren „Korrekturbereichen“ einen Platz von 16 ·|B1(c)| = 16 ·13 = 208 einnehmen. Es gibt also einen „verschwendeten Platz“ von 4.096−208 = 3.888 Wörtern.

Code 2 C2 besteht aus folgenden Wörtern in H(7,F2):

(0, 0, 0, 0, 0, 0, 0) (0, 1, 0, 0, 1, 0, 1) (1, 0, 0, 0, 0, 1, 1) (1, 1, 0, 0, 1, 1, 0)(0, 0, 0, 1, 1, 1, 1) (0, 1, 0, 1, 0, 1, 0) (1, 0, 0, 1, 1, 0, 0) (1, 1, 0, 1, 0, 0, 1)(0, 0, 1, 0, 1, 1, 0) (0, 1, 1, 0, 0, 1, 1) (1, 0, 1, 0, 1, 0, 1) (1, 1, 1, 0, 0, 0, 0)(0, 0, 1, 1, 0, 0, 1) (0, 1, 1, 1, 1, 0, 0) (1, 0, 1, 1, 0, 1, 0) (1, 1, 1, 1, 1, 1, 1)

Ein Wort v aus H(4,F2) wird codiert durch dasjenige Wort aus H(7,F2) in der Liste,dessen Anfangsstück gerade v ist. Man kann nun überprüfen, dass C2 ein binärer [7, 4, 3]-

61

3. Lineare Codes

Code ist. Der Code erkennt also ebenfalls zwei Fehler und korrigiert einen, bei gleicherAnzahl von Codewörtern (d. h. gleicher Dimension 4).Die Raumgröße ist hier aber |H(7,F2)| = 27 = 128. Die 16 Codewörter nehmen mit Ihren„Korrekturbereichen“ einen Platz von 16 · |B1(c)| = 16 · 8 = 128 ein, d. h. es gibt keinenverschwendeten Platz. Solche Codes heißen perfekte Codes.C2 ist übrigens ein Beispiel für einen Hamming-Code. Im folgenden wird erklärt wer-den, wie man C2 systematisch konstruieren kann und wie Codierung und Decodierungfunktionieren. Denn C1 hat gegenüber C2 zunächst den Vorteil, dass die Codierungs- undDecodierungsschritte offensichtlich sind, während man bei C2 in der Tabelle nachschauenmuss.

Definition: Anforderungen an einen guten CodeEin guter Code sollte also• möglichst viele Fehler erkennen und korrigieren, d. h. großen Minimalabstand ha-

ben;• möglichst viele Codewörter im Verhältnis zur Wortlänge n haben;• und dabei eine effiziente Codierung (Verschlüsselung), Decodierung (Entschlüsse-

lung) und ggf. Fehlerkorrektur gestatten.

ErläuterungFür Ver- und Entschlüsselung gibt es immer die Möglichkeit, eine Verschlüsselungsta-fel aufzustellen. Für die Entschlüsselung eines fehlerhaft übertragenen Worts muss dannnach dem bzgl. der Hamming-Metrik nächstgelegenen Wort in der Tafel suchen. Bei einemgroßen Hamming-Raum ist dies aber ein eher langwieriger Algorithmen. Schnelle Algo-rithmen setzen voraus, dass der Code eine interne Struktur besitzt. Daher sind lineareCodes interessant.Die ersten beiden Anforderungen laufen einander zuwider: Redundanzen (Prüfziffern)erhöhen die Wortlänge. Es gibt daher Schranken für das Verhältnis von Codegröße undMinimalabstand bei gegebenen Hamming-Raum.

[Die Hamming-Schranke] Die Anzahl der Codewörter eines q-ären Codes der Länge n mitMindestabstand > d ist höchstens

qn/ b d−1

2c∑

i=0

(n

i

)· (q − 1)i.

Beweis zu: Hamming-SchrankeDie Schranke folgt sofort aus der Formel für die Anzahl der Elemente von |Be(c)| undder Größe des Hamming-Raumes |H(n, q)| = qn.

62


Definition: perfekter CodeEin Code heißt perfekt , wenn er die Hamming-Schranke erreicht.

Beispiel

• q = 2, n = 7, d = 3: Hier ergibt die Hamming-Schranke 27/(1 + 7) = 16. DerHamming-Code C2 im Beispiel oben erreicht als perfekter Code diese Schranke.• q = 2, n = 6: Die Folge der Binomialkoeffizienten

(6i

)ist 1, 6, 15, 20, 15, 6, 1. Keine

der Summen(60

)+ . . .

(6e

)ist ein Teiler von 26 = 64 außer für e = 0 und e = 6. Diese

entsprechen den sogenannten trivialen Codes: es sind alle Wörter Codewörter (beiMinimalabstand 1) oder es gibt überhaupt nur ein Codewort (bei Minimalabstand∞). Beide Codes sind perfekt, aber aus Sicht der Codierungstheorie vollkommenuninteressant. Darüberhinaus gibt es also keinen perfekten binären Code der Länge6.

[Die Gilbert-Schranke4] Gegebenen q, n, d, so gibt es einen q-ären Code der Länge n undvom Minimalabstand mindestens d mit mindestens

qn/ d−1∑

i=0

(n

i

)· (q − 1)i

Codewörtern. Ist q eine Primzahlpotenz, so kann man den Code linear wählen.

Beweis zu: Sei C ein Code vom Minimalabstand > d, so dass |C| kleiner als die Gilbert-Schranke ist.Dann gibt es ein x ∈ H(n, q), welches zu allen c ∈ C mindestens Abstand d hat, dennnach Annahme gilt |C| · |Bd−1(c)| < qn = |H(n, q)|. (Die Größe der Bälle Bd−1(c) hängtnicht von c ab!) Dann ist C ∪ {x} ein größerer Code vom Minimalabstand > d. Durchsukzessives Vergrößern erhält man also einen Code, der die Gilbert-Schranke erfüllt.Für den linearen Fall nimmt man an, dass C ⊆ H(n,Fq) bereits ein linearer Code ist(z. B. der triviale Code {0}) und wählt x wie oben. Statt C ∪ {x} betrachtet man nunden erzeugten linearen Code 〈x,C〉, muss aber noch zeigen, dass dieser weiterhin Min-destgewicht > d hat.Ein typisches Element darin hat die Form αx+ βc mit α, β ∈ Fq und c ∈ C.– Falls α = 0, so ist d(αx+ βc, 0) = d(βc, 0) > d nach Annahme an C.– Falls α 6= 0, so ist d(αx+ βc, 0) = d(x,−β

αc) > d nach Wahl von x, da βαc ∈ C.

BeispielFür q = 2, n = 7, d = 3 ergibt die Gilbert-Schranke 27/(1 + 7 + 21) ≈ 4, 41. Die Gilbert-Schranke stellt also die Existenz einen Codes C vom Minimalabstand 3 mit mindestens

4Edgar Gilbert (*1923)

63

3. Lineare Codes

5 Codewörtern sicher. Im linearen Fall weiß man, dass die Anzahl der Element von Cals Untervektorraum von F7

2 eine Zweierpotenz sein muss, also erhält man |C| > 8. Ausdem obigen Beispiel wissen wir aber, dass es sogar den Hamming-Code mit 16 Wörterngibt.

3.3. Erzeuger und Prüfmatrizen

Sei C nun ein q-ärer [n, k]-Code, also ein k-dimensionaler Unterraum von H(n, q) = Fnq .

Definition: ErzeugermatrixEine Erzeugermatrix G für einen linearen [n, k]-Code C ist eine (k × n)-Matrix, derenZeilen eine Basis von C bilden.

ErläuterungEine Erzeugermatrix eines Codes ist nicht eindeutig bestimmt. Man kann sie aber durchelementare Umformungen auf die Form(

Idk A)

bringen, wobei A eine (k×(n−k))-Matrix ist. Im allgemeinen wird der Code durch solcheUmformungen verändert und durch einen äquivalenten Code ersetzt. äquivalente Codeshaben zwar u.U.. andere Codewörter, aber dieselben Parameter wie z. B. Anzahl derCodewörter, Minimalabstand, und werden in der Regel identifiziert. Wir werden auchsehen, dass diese spezielle Form der Erzeugermatrix einer Codierung durch Anhängenvon Prüfziffern entspricht, also einer sehr üblichen Art von Codes.BeispielDer [7, 4, 3]-Hamming-Codes hat mit

G =

1 0 0 0 0 1 10 1 0 0 1 0 10 0 1 0 1 1 00 0 0 1 1 1 1

eine Erzeugermatrix in der Form (Idk | A).ErläuterungMan sieht hier leicht, dass die Basisvektoren ein Gewicht und paarweise einen Abstandvon mindestens 3 haben. Dies reicht aber nicht um zu folgern, dass der erzeugte Co-de Minimalabstand mindestens 3 hat. Zum Beispiel haben die Vektoren (1, 1, 1, 0, 0, 0),(0, 0, 0, 1, 1, 1) und (1, 1, 0, 1, 1, 0) Gewicht > 3 und paarweisen Abstand > 3, der vonihnen erzeugte Code hat aber nur Minimalgewicht 2. Man kann nur, wie im Beweisder Gilbert-Schranke, von einem Vektor, der zu einem Untervektorraum einen Mini-malabstand hat, auf den Minimalabstand des von beiden erzeugten Untervektorraumsschließen.

64


Definition: Codierung mit Hilfe der Erzeugermatrix:Die Codierung eines (Zeilen-)Vektors v ∈ H(k, q) erfolgt nun5 durch v ·G = (GT ·vT)T ∈H(n, q). Hat G die besondere Form (Idk | A), so entsteht der Codevektor also durchAnhängen von n−k Prüfziffern, da v ·G die Form v� w für einen Vektor w der Länge n−khat. Die Prüfziffern erhält man als Linearkombination der Prüfziffern der Basiselement.

BeispielIm Beispiel wird etwa der Vektor (1, 0, 1, 1), den man als Darstellung der Binärzahl 1011bzw. der Hexadezimalzahl B auffassen kann, durch (1, 0, 1, 1) · G = (1, 0, 1, 1, 0, 1, 0)codiert.

Die Codierungsabbildung ist injektiv.

Beweis zu: Injektivität der CodierungsabbildungIm Falle des Anhängens von Prüfziffern ist dies trivialerweise gegeben; da jeder Code zueinem solchen äquivalent ist, also durch Isomorphie dazu übergeht, gilt es auch allgemein.Alternativ: Die Zeilen von G sind linear unabhängig, also gilt

rg(G) = rg(GT) = dimBild(GT) = k

und somit dimKern(GT) = 0.

Definition: PrüfmatrixEine Prüfmatrix H für einen [n, k]-Code C ist eine ((n − k) × n)-Matrix, für die C =Kern(H) gilt.

Die folgenden Aussagen sind äquivalent für einen linearen [n, k]-Code C und eine ((n−k)× n)-Matrix H:(a) H ist eine Prüfmatrix von C.(b) Es gilt H · cT = 0 für alle c ∈ C und die Zeilen von H sind linear unabhängig.(c) Es gilt G ·HT = 0 und die Zeilen von H sind linear unabhängig.

Beweis zu: äquivalente Definitionen der PrüfmatrixG ·HT = 0 ist äquivalent mit H · GT = 0 und impliziert H · cT = 0 für alle c ∈ C, dajedes c ∈ C Linearkombination von Zeilen von G ist. Dies bedeutet, dass C im Kern vonH liegt. Wegen rg(H) = dimBild(H) = n − dimKern(H) und n − k = n − dim(C) istdie lineare Unabhängigkeit der Zeilen von H mit dimKern(H) = k äquivalent und mitder ersten überlegung also zu Kern(H) = C.

65

3. Lineare Codes

Genau dann sind G und H Erzeuger- und Prüfmatrix eines [n, k]-Codes, wenn G eine(k × n)-Matrix vom Rang k und H eine ((n− k)× n)-Matrix vom Rang (n− k) ist, fürdie G ·HT = 0 ist.

Beweis zu: Eigenschaften von Erzeuger- und PrüfmatrizenErzeuger- und Prüfmatrix haben nach Definition und Satz 3.3 diese Eigenschaften. Um-gekehrt kann es eine (k × n)-Matrix G vom Rang k nur für k 6 n geben; solch eineMatrix ist dann per Definition Erzeugermatrix des Codes Bild(GT). H ist dann wiedernach Satz 3.3 eine zugehörige Prüfmatrix.

Wenn eine Erzeugermatrix G die Form (Idk | A) hat, so ist

H =(−AT Idn−k

)eine zugehörige Prüfmatrix.

ErläuterungWenn also

G =

1 0 . . . . . . 0 a11 . . . a1n−k

0. . . . . .

......

....... . . . . . . . .

......

....... . . . . . 0

......

0 . . . . . . 0 1 ak1 . . . ak n−k

,

dann ist

H =

−a11 . . . −ak1 1 0 . . . . . . 0...

... 0. . . . . .

.........

.... . . . . . . . .

.........

.... . . . . . 0

−a1n−k . . . −ak n−k 0 . . . . . . 0 1

,

denn man sieht leicht, dass dann G ·HT = 0.Der Code C ist jeweils durch G und durch H festgelegt; umgekehrt sind G und H abernicht eindeutig durch C bestimmt. In der speziellen Form sind sie zwar durch C festgelegt,für äquivalente Codes sind sie aber im allgemeinen verschieden.BeispielIm Falle des [7, 4, 3]-Hamming-Codes und der Erzeugermatrix G von oben ist

H =

0 1 1 1 1 0 01 0 1 1 0 1 01 1 0 1 0 0 1

die passende Prüfmatrix.

66


Definition: Decodierung mit Hilfe der PrüfmatrixAngenommen w ∈ H(n, q) wird empfangen. Als Decodierung wird zunächst dasjenigec ∈ C gesucht, welches minimalen Hamming-Abstand zu w hat und dann das Urbild vonc unter der Codierung (die ja injektiv ist) bestimmt. Um die Existenz von c sicherzu-stellen, nehmen wir an, dass entweder ein perfekter, e-fehlerkorrigierender Code vorliegt,oder dass höchstens e übertragungsfehler vorgekommen sind, wobei 2e + 1 6 d für dasMinimalgewicht d des Codes ist.Es gilt aufgrund dieser Annahmen dann w = c + f wobei c ∈ C und d(f, 0) 6 e. Manberechnet nun zunächst das sogenannte Syndrom von w, das ist H · wT. Es gilt dafür

H · wT = H · (c+ f)T = H · cT +H · fT = 0 +H · fT = H · fT,

d. h. das Syndrom von w ist gleich dem Syndrom des Fehlers f . Für zwei mögliche Fehlerf, f ′ gilt zudem

d(f − f ′, 0) 6 d(f, 0) + d(−f ′, 0) 6 e+ e < d,

also ist f − f ′ /∈ C und somit H · fT −H · f ′T = H · (f − f ′)T 6= 0. Verschiedene Fehlerhaben also verschiedene Syndrome.Man kann nun eine Liste der Syndrome der möglichen Fehler aufstellen. Dies sind |Be(0)|viele; eine im Vergleich mit |H(n, q)| deutlich kleinere Zahl. Die Decodierung geht dannfolgendermaßen: Man berechnet das SyndromH ·wT, schaut in der Tabelle nach, welchemFehler f es entspricht, korrigiert den Fehler, und erhält so das zugehörige Codewort c ∈ C.Zu diesem kann man nun die Umkehrung der Codierungsabbildung bestimmen; hat G diebesondere Form (Idk | A), dann besteht diese Umkehrabbildung einfach im Weglassender Prüfziffern.

ErläuterungAn der Prüfmatrix kann man das Minimalgewicht des Codes ablesen:

Sei C ein linearer Code. Dann gilt: C hat genau dann Minimalgewicht mindestens d,wenn je d− 1 Spalten der Prüfmatrix linear unabhängig sind.

Beweis zu: Prüfmatrix und Minimalgewicht des CodesEine Linearkombination 0 =

∑ni=0 aiSi der Spalten Si von H entspricht gerade einem

Vektor a = (a1, . . . , an), für welchen H · a = 0 gilt, also einem a ∈ Kern(H) = C. DieAnzahl der Komponenten ai 6= 0 in a, also der tatsächlich vorkommenden Spalten in derLinearkombination, ist gerade das Gewicht von a.

Insbesondere hat also ein Code Minimalgewicht mindestens 3, wenn je zwei Spaltender Prüfmatrix linear unabhängig sind, d. h. wenn keine null ist und keine das skalareVielfache einer anderen ist.

67

3. Lineare Codes

Definition: Hamming-CodeEin Hamming-Code ist ein linearer Code C vom Minimalgewicht 3, dessen Prüfmatrixzu gegebener Zeilenanzahl die maximale Anzahl von Spalten hat.

ErläuterungIst m die Anzahl der Zeilen der Prüfmatrix H, so bilden die Spalten von H ein Re-präsentantensystem der Vektoren Fq \ {0} bezüglich skalarer Multiplikation. d. h. keineSpalte von H ist die Nullspalte und für jeden Vektor v ∈ Fmq , v 6= 0 gibt es genau einenSpaltenvektor von H, der ein skalares Vielfaches von v ist. Mit anderen Worten: dieSpaltenvektoren sind Erzeuger eindimensionaler Unterräume von Fmq und jeder solcheUnterraum kommt genau einmal vor.Man kann sich leicht überlegen, dass die Anzahl n der Spalten dann genau qm−1

q−1 ist, dennqm − 1 ist die Anzahl der Vektoren 6= 0 und q − 1 die Anzahl der Skalarfaktoren 6= 0).Die Dimension des zugehörigen Hamming-Codes ist dann k = qm−1

q−1 −m.

Hamming-Codes sind perfekt.

Beweis zu: Hamming-Codes sind perfektEs ist also n = qm−1

q−1 und k = qm−1q−1 −m und man rechnet nach, dass

|C| · |B1(c)| = qqm−1q−1

−m ·(1 + qm−1

q−1 · (q − 1))= q

qm−1q−1 = |H( q

m−1q−1 ,Fq)|.

Erläuterung

Spezialfall q = 2: Hier ist die Situation besonders einfach: Die Spaltenvektoren vonH sind sämtliche Vektoren in Fmq ohne den Nullvektor. Ihre Anzahl n ist 2m − 1, dieDimension des Codes ist 2m− (m+1). übrigens sind alle binären Hamming-Codes festerLänge "äquivalent.Auch die Decodierung ist im Falle q = 2 besonders einfach: Die möglichen Fehler sindgerade die Standardbasisvektoren e1, . . . , en in Fn2 . Das Syndrom H · eTi von ei ist danngerade die i-te Spalte von H. Zur Decodierung von w berechnet man also das SyndromH ·wT. Ist das Syndrom 0, so ist kein Fehler aufgetreten. Andernfalls schaut man nach,in welcher Spalte i von H das Syndrom auftritt, ändert das i-te Bit von w und lässt diePrüfziffern, d. h. die letzten n− k Stellen von w, weg.

3.4. Liste der perfekten Codes

BeispielIst q eine Primzahlpotenz, so gibt es die folgenden perfekten q-ären Codes (wobei e dieAnzahl der korrigierbaren Fehler bezeichnet):

68

3.4. Liste der perfekten Codes

• triviale Codes, die nur aus einem Wort bestehen (nimmt man dafür den Nullvektor,so ist es ein [n, 0,∞]-Code mit e = n);• den triviale [n, n, 1]-Code mit e = 0 (alle Wörter sind im Code);• die q-ären Hamming-Codes: [ q

m−1q−1 ,

qm−1q−1 − m, 3]-Codes mit e = 1; sowie einige

nicht-lineare Codes mit gleichen Parametern wie Hamming-Codes;• die binären Wiederholungscodes ungerader Länge:

zu jedem e ∈ N einen [2e+1, 1, 2e+1]-Code, der nur die beiden Wörter (0, 0, . . . , 0)und (1, 1, . . . , 1) enthält;• den binären Golay-Code6: ein [23, 12, 7]-Code mit e = 3;• den ternären Golay-Code: ein [11, 6, 5]-Code mit e = 2.

Der binäre Wiederholungscode stimmt für e = 0 mit dem trivialen [1, 1, 1]-Code und füre = 1 mit dem [3, 1, 31]-Hamming-Code überein.Falls q keine Primzahlpotenz ist, so weiß man nicht, ob es perfekte nicht-triviale q-äreCodes gibt, und nur für einige wenige Werte weiß man, dass keine perfekten q-ären Codesexistieren außer den trivialen. Im allgemeinen weiß man auch wenig darüber, welches die„besten“ Codes sind (hinsichtlich der „Packungsdichte“

6Marcel Golay (1902-1989)

69

Teil II.

Algebra

71

4. Gruppen

4.1. Gruppen

Zur Erinnerung:

Definition: GruppeEine Gruppe besteht aus einer nicht-leeren Menge G und einer zweistelligen Operation◦ : G × G → G auf G, die assoziativ ist, ein neutrales Element e hat, und in der jedesElement g ∈ G ein inverses Element g−1 besitzt.G heißt kommutative Gruppe, wenn ◦ zusätzlich kommutativ ist.

Notation: Weglassen von Teilen der DefinitionNeutrale Elemente und die jeweiligen Inversen sind eindeutig bestimmt; insbesondere gilt(g−1)−1 = g und (g◦h)−1 = h−1◦g−1. Es reicht also, wenn man eine Gruppe beschreibenmöchte, die Grundmenge und die Operation anzugeben. Bei Standardbeispielen lässt mandie Operation auch weg (so ist z. B. klar, dass mit Z die Gruppe (Z,+) gemeint ist, undnicht eine etwaige andere Operation.)Notation: Schreibweisen für die Teile der DefinitionEs gibt drei gebräuchliche Schreibweisen:

Operation neutrales Element inverses Element

allgemeine Schreibweise ◦ e g−1

multiplikative Schreibweise · 1 g−1

additive Schreibweise + 0 −g

Multiplikationspunkte (und manchmal auch das Zeichen ◦) werden gerne weggelassen;die additive Schreibweise ist üblicherweise kommutativen Gruppen vorbehalten. Bei derAngabe einer GruppeBeispielErinnerung auch an wichtige Beispiele:

• die kommutative Gruppe (Z,+, 0);• die kommutative Gruppe Zm =

({0, . . . ,m− 1},+m, 0

), wobei

x+m y = „Rest von x+ y bei Division durch m“ =

{x+ y falls x+ y < m

x+ y −m falls x+ y ≥ m;

73

4. Gruppen

• die Gruppen (Sym(M), ◦, id) der Permutationen vonM , d. h. der BijektionenM →M ;• die Gruppe der Vektorraum-Isomorphismen V → V mit der Hintereinanderausfüh-

rung von Abbildungen als Operation;• die Gruppe GL(n,K) der invertierbaren (n × n)-Matrizen über einem Körper K,

d. h. der (n× n)-Matrizen mit Determinante 6= 0.

Für n = 0, 1 ist GL(n,R) kommutativ, ebenso Sym(M) für ein- oder zweielementigeMengen M . In allen anderen Fällen sind diese Gruppen nicht kommutativ.

Definition: GruppenhomomorphismusEine Abbildung φ : G → H zwischen zwei Gruppen (G, ◦G, eG) und (H, ◦H , eH) heißtGruppenhomomorphismus, falls• φ(g1 ◦G g2) = φ(g1) ◦H φ(g2) für alle g1, g2 ∈ G;• φ(eG) = eH ;• φ(g−1) = φ(g)−1 für alle g ∈ G.

Man kann zeigen, dass es ausreicht, die erste Bedingung zu prüfen, da die zweite unddritte dann automatisch erfüllt sind.

Notation: HomomorphismusWenn klar ist, dass es um Gruppen geht, spricht man auch kurz von „Homomorphismus“.BeispielBeispiele für Gruppenhomomorphismen:• Die „Rest-Abbildung“ Z→ Zm, die den Rest bei der Division durch m angibt, also

eine Zahl n = qm+ r mit 0 6 r < m auf r abbildet.• Die Determinante det : GL(n,R)→ (R \ {0}, ·).• Die Abbildung M : Sn → GL(n,R), die einer Permutation σ die zugehörige Per-

mutationsmatrix M(σ) zuordnet.• Das Signum (oder Vorzeichen) sgn : Sn → ({±1}, ·) mit sgn = det ◦M .

Definition: GruppenisomorphismusEin Gruppenhomomorphismus φ : G → H heißt (Gruppen-)Isomorphismus, falls φ bi-jektiv ist und die Umkehrabbildung φ−1 ebenfalls ein Gruppenhomomorphismus ist.Zwei Gruppen G und H heißen isomorph zueinander, G ∼= H, falls es einen Gruppeniso-morphismus G→ H gibt.

74

4.1. Gruppen

Man kann zeigen, dass ein bijektiver Gruppenhomomorphismus stets ein Isomorphismusist, also dass die Umkehrabbildung, falls sie existiert, automatisch ein Homomorphismusist.

Beispiel

• Die Gruppe der Vektorraum-Isomorphismen Rn → Rn ist isomorph zu der Matrix-gruppe GL(n,R): jede Basiswahl liefert einen Isomorphismus.• Sind M und N zwei gleichmächtige Mengen, so liefert jede Bijektion β : M → N

einen Gruppenisomorphismus β̂ : Sym(M)→ Sym(N), σ 7→ β ◦ σ ◦ β−1.Bis auf Isomorphie ist Sym(M) also durch die Anzahl der Elemente von M fest-gelegt; für |M | = n schreibt man dann auch Sn für eine zu Sym(M) isomorpheGruppe.• Man kann zeigen, dass die beiden Gruppen S3 und GL(2,F2) isomorph zueinander

sind.

Definition: UntergruppeEine Untergruppe U von G, U 6 G, ist eine Teilmenge U ⊆ G, die abgeschlossen bzgl.der Gruppenoperation ist, das neutrale Element enthält und zu jedem seiner Elementauch dessen Inverses.Eine Untergruppe ist also eine Teilmenge U , die bzgl. der auf U eingeschränkten Opera-tionen selbst wieder eine Gruppe ist.

Beispiel

• Die Gruppe G selbst und die triviale Gruppe {e} sind stets Untergruppen von G.• Untergruppen von Untergruppen sind Untergruppen: Falls U 6 V und V 6 G, so

ist U 6 G.• Jeder Untervektorraum eines Vektorraums ist insbesondere auch eine Untergruppe.

(Untervektorräume sind die unter Skalarmultiplikation abgeschlossenen Untergrup-pen.)• Falls G eine Gruppe ist, so bildet das Zentrum Z(G) := {g ∈ G | g ◦ h = h ◦g für alle h ∈ G} eine Untergruppe von G.

Es ist z. B. Z(S3) = {e} und Z(GL(n,R)

)=

r 0

. . .0 r

∣∣∣∣ r ∈ R\{0}

.

• Die Gruppe der Vektorraum-Isomorphismen V → V ist eine Untergruppe vonSymV .

75

4. Gruppen

Definition: Kern eines GruppenhomomorphismusWenn φ : G → H ein Gruppenhomomorphismus ist, so ist der Kern definiert alsKern(φ) := {g ∈ G | φ(g) = e}.

Wenn φ : G → H ein Gruppenhomomorphismus ist, so ist der Kern von φ eine Unter-gruppe von G und das Bild von φ eine Untergruppe von H.

Beweis zu: Kern und Bild sind UntergruppenEs gilt nach Definition φ(eG) = eH , also ist eG ∈ Kern(φ) und eH ∈ Bild(φ). Wenng1, g2 ∈ Kern(φ), so ist φ(g1 ◦ g2) = φ(g1) ◦ φ(g2) = e ◦ e = e, und φ(g−11 ) = φ(g1)

−1 =e−1 = e, also ist Kern(φ) eine Untergruppe. Wenn h1 = φ(g1), h2 = φ(g2), so sindh1 ◦ h2 = φ(g1) ◦ φ(g2) = φ(g1 ◦ g2) und h−11 = φ(g1)

−1 = φ(g−11 ), also ist Bild(φ) eineUntergruppe.

Definition: erzeugte UntergruppeDer Schnitt einer Menge von Untergruppen von G ist, wie man sich schnell überlegt,wieder eine Untergruppe von G. Also existiert zu jeder Teilmenge A ⊆ G die „kleinsteUntergruppe von G, die A enthält“. Diese Untergruppe wird die von A erzeugte Unter-gruppe genannt wird und mit 〈A〉 bezeichnet wird. Es gilt nun

〈A〉 ={a1±1 ◦ . . . ◦ an±1

∣∣ ai ∈ A,n ∈ N}

mit der Konvention, dass a+1 = a: Zum einen muss jede A enthaltende Untergruppeauch jedes der Produkte a1±1 ◦ . . . ◦ an±1 enthalten. Zum andern bildet die Menge dieserProdukte eine A enthaltende Untergruppe: für n = 0 enthält man das neutrale Ele-ment („leeres Produkt“); mit n = 0 enthält man jedes Element von a; die Menge istoffensichtlich unter der Gruppenoperation abgeschlossen, und ebenso unter Inversen, da(a1±1 ◦ . . . ◦ an±1)−1 = an

∓1 ◦ . . . ◦ a1∓1.

Notation: Kurzschreibweise der erzeugten UntergruppeStatt 〈{g1, . . . , gk}〉 schreibt man kurz 〈g1, . . . , gk〉.

4.2. Zyklische Gruppen

Definition: Potenz eines Gruppenelements

76


Sei G eine Gruppe und g ∈ G. Man definiert für n ∈ Z:

gn :=

g ◦ · · · ◦ g︸︷︷︸

n mal

n > 1

e n = 0

g−1 ◦ · · · ◦ g−1︸︷︷︸|n| mal

n < 1

Insbesondere gilt g1 = g, und g−1 stimmt mit dem bisher schon damit bezeichnetenInversen von g überein.

Man überzeugt sich leicht, dass für n < 0 gilt: gn = (g−1)|n| = (g|n|)−1.

Definition: alternative Definition der Potenz eines GruppenelementsMan kann die Definition auch in induktiver Form angeben:

g0 := e

gn+1 := g ◦ gn für n ∈ Ngn := (g−n)−1 für n ∈ Z \N

Notation: Potenz eines Gruppenelements bei additiver GruppeIst die Gruppe (G,+) additiv geschrieben, so schreibt man ng statt gn.

Es gelten die Potenzgesetze, wie man sie vom Spezialfall der Gruppe (R \ {0}, ·) her kennt,d. h.:

gn+m = gn ◦ gm und (gn)m = gnm

für alle g ∈ G und n,m ∈ Z.

Beweis zu: Gültigkeit der PotenzgesetzeFür die erste Regel sollte man Fallunterscheidungen nach den Vorzeichen von n und mmachen; jeder einzelne Fall ist aber nach Definition klar. Die zweite Regel ist ebenfallsunmittelbar einsichtig für n,m > 0. Falls n = 0 oder m = 0 kommt nach Definition vong0 auf beiden Seiten e heraus. Ist mindestens einer der beiden Exponenten negativ, sokann man sich durch g−n = (gn)−1 auf den positiven Fall zurückziehen.ErläuterungDie Regel (g−1)−1 = g ist nun übrigens ein Spezialfall des zweiten Potenzgesetzes, ebenso(g−1)n = (gn)−1.

77

4. Gruppen

Das erste Potenzgesetz besagt, dass es für jedes g ∈ G einen Homomorphismus gibt:

g␣ : (Z,+)→ (G, ◦), n 7→ gn.

Das Bild dieses Homomorphismus ist die von g erzeugte Untergruppe 〈g〉.

Definition: Zyklische Gruppe, Ordnung einer Gruppe, Ordnung eines Grup-penelements(a) Eine Gruppe heißt zyklisch, wenn sie von einem Element erzeugt ist.(b) Die Ordnung einer Gruppe G ist die Anzahl der Elemente von G (eine natürlicheZahl oder ∞).(c) Die Ordnung eines Gruppenelements g ∈ G, ord(g), ist die Ordnung der von gerzeugten Untergruppe 〈g〉.

Beispiel

• In jeder Gruppe ist e das einzige Element mit Ordnung 1.• Die Gruppe (Z,+) ist zyklisch; sie hat zwei Erzeuger: 1 und −1. Die Ordnung der

Gruppe ist ∞; alle Elemente außer 0 haben Ordnung ∞.• Die Gruppe Z12 ist zyklisch: 1, 5, 7 und 11 haben jeweils Ordnung 12 und sind

daher Erzeuger. Die Ordnung aller Element sieht man in der folgenden Tabelle:

Element 0 1 2 3 4 5 6 7 8 9 10 11

Ordnung 1 12 6 4 3 12 2 12 3 4 6 12

• Die Gruppe Sn hat Ordnung n! und ist für n > 2 nicht zyklisch, da nicht kommu-tativ.

ErläuterungZyklische Gruppen sind kommutativ, denn es gilt

gm ◦ gn = gm+n = gn+m = gn ◦ gm.

Allgemeiner gilt, dass homomorphe Bilder kommutativer Gruppen wieder kommutativsind, d. h. falls φ : G → H ein surjektiver Gruppenhomomorphismus ist und G kommu-tativ, dann ist H kommutativ, da h1 ◦ h2 = φ(g1) ◦ φ(g2) = φ(g1 ◦ g2) = φ(g2 ◦ g1) =φ(g2) ◦ φ(g1) = h2 ◦ h1.

Untergruppen und homomorphe Bilder zyklischer Gruppen sind wieder zyklisch.

Beweis zu: Untergruppen, homomorphe Bilder und zyklische GruppenSei φ : G = 〈g〉 → H ein surjektiver Gruppenhomomorphismus. Dann ist H = Bild(φ) ={φ(gn) | n ∈ Z} = {φ(g)n | n ∈ Z} = 〈φ(g)〉.

78


Allgemein gilt bei einem Homomorphismus φ : G→ H mitX ⊆ G, dass φ[〈X〉] = 〈φ[X]〉,d. h. die Bilder von Erzeugern sind Erzeuger des Bilds.Sei nun U 6 〈g〉. Falls U = {e}, ist U natürlich zyklisch. Andernfalls gibt es ein e 6=gn ∈ U , und dann ist auch g−n = (gn)−1 ∈ U . Wähle nun m > 0 minimal mit derEigenschaft, dass gm ∈ U . Dann ist offensichtlich 〈gm〉 ⊆ U . Falls gn ∈ U , so schreibt mann = qm+r mit r ∈ {0, . . . ,m−1} (Division mit Rest) und sieht mit den Potenzgesetzen:gr = gn−qm = gn ◦ (gm)−q ∈ U . Aus der Minimalität von m folgt also r = 0, und somitgn ∈ 〈gm〉 = U .

Eine zyklische Gruppe ist entweder von unendlicher Ordnung und isomorph zu (Z,+)oder von endlicher Ordnung m und isomorph zu (Zm,+m).

Beweis zu: Eigenschaften von zyklischen GruppenSei G = 〈g〉 zyklisch, und betrachte den surjektiven Homomorphismus g␣ : Z→ G,n 7→gn. Falls g␣ injektiv ist, so ist es ein Isomorphismus und somit G ∼= Z. Andernfalls gibtes k 6= l mit gk = gl. Dann ist gk−l = gk ◦ (gl)−1 = e, d. h. Kern(g␣) 6= {0}. Wähle nunm > 0 minimal mit m ∈ Kern(g␣), d. h. mit gm = e. Nach dem Beweis von Satz 4.2ist dann Kern(g␣) = 〈m〉; es gilt also gk = gl ⇐⇒ k − l ∈ 〈m〉 d. h. wenn m einTeiler von k − l ist. Somit ist G = {g0, g1, . . . , gm−1} und die Abbildung r 7→ gr ist einIsomorphismus Zm → G.ErläuterungIm nächsten Abschnitt werden wir sehen, dass im zweiten Fall aus dem Homomorphiesatzunmittelbar G ∼= Z/mZ folgt, wobei Z/mZ eine abstrakt gewonnenen, zu Zm isomorpheGruppe ist.

Die Ordnung von g ∈ G ist das kleinste m > 0 mit gm = e, sofern es existiert; und ∞sonst. Es gilt genau dann gk = e, wenn m ein Teiler von k ist.

ErläuterungWenn G = 〈g〉 ∼= Z eine unendliche zyklische Gruppe ist und H eine beliebige Gruppe,dann existiert zu jedem h ∈ H ein eindeutig bestimmter Gruppenhomomorphismus G→H mit g 7→ h, nämlich die Abbildung gn 7→ hn. In diesem Aspekt ähnelt also der Erzeugereiner unendlichen zyklischen Gruppe der Basis eines Vektorraums.Wenn G = 〈g〉 ∼= Zm eine endliche zyklische Gruppe ist und H eine beliebige Gruppe,dann existiert nicht unbedingt ein Gruppenhomomorphismus G → H mit g 7→ h, dennes gilt gm = e, also muss auch hm = φ(g)m = φ(gm) = φ(e) = e gelten. Dies ist aberdas einzige Hindernis, d. h. man kann zeigen, dass ein (eindeutig bestimmter) Gruppen-homomorphismus G → H mit g 7→ h genau dann existiert, wenn hm = e, also wennord(h) | ord(g).Anders als bei Vektorräumen kann man bei Gruppen also nicht Homomorphismen be-liebig auf minimalen Erzeugendensystemen vorschreiben, Das liegt daran, dass in Vek-

79

4. Gruppen

torräumen Basen „frei“ sind, also keine besonderen Abhängigkeiten vorweisen können,während in Gruppen zusätzliche Gleichungen gelten können.

Definition: Automorphismus, AutomorphismengruppeEin Automorphismus einer Gruppe G ist ein Isomorphismus G → G. Die Menge derAutomorphismen von G bildet unter der Hintereinanderausführung von Abbildungen dieAutomorphismengruppe von G, Aut(G).

Sei G = 〈g〉 zyklisch. Dann sind die Automorphismen von G genau die Homomorphismenφ : G→ G, für die φ(g) ein Erzeuger von G ist.

Beweis zu: Automorphismen und Homomorphismen und ErzeugerBild(φ) = 〈φ(g)〉, ist ein Homomorphismen φ : G→ G genau dann surjektiv, wenn φ(g)ein Erzeuger ist. Im endlichen Fall sind surjektive Abbildungen zwischen gleichmächtigenMengen automatisch injektiv. Im Fall G = Z gibt es die beiden Erzeuger 1 und −1; diezugehörigen Abbildungen id und n 7→ −n sind ebenfalls beide injektiv.BeispielZ12 hat also vier Automorphismen: die Identität, die „Spiegelung“ n 7→ −n(+12) (die aufder Uhr der Spiegelung an der Mittelsenkrechten entspricht) und zwei durch 1 7→ 5 und1 7→ 7 bestimmte Automorphismen, mit folgenden Wertetabellen:

0 1 2 3 4 5 6 7 8 9 10 11

1 7→ 11 0 11 10 9 8 7 6 5 4 3 2 11 7→ 5 0 5 10 3 8 1 6 11 4 9 2 71 7→ 7 0 7 2 9 4 11 6 1 8 3 10 5

Dies sind, neben der Identität, also die einzigen mit der Addition +12 verträglichenPermutationen von {0, . . . , 11}.Zusammenfassung der Ergebnisse über zyklische Gruppen1. Fall: unendliche Ordnung• Z ist bis auf Isomorphie die einzige zyklische Gruppe unendlicher Ordnung.• Die Ordnung von 0 ist 1, die Ordnung aller anderer Elemente ist ∞.• 1 und −1 sind Erzeuger.• Die Untergruppen von Z sind von der Form 〈n〉 = nZ := {k · n | k ∈ Z} für n ∈ N.

Es ist dabei 0Z = {0} die triviale Untergruppe und 1Z = Z.• Die homomorphen Bilder von Z sind Z selbst und alle Zm.• Aut(Z) = ({id, n 7→ −n}, ◦) ∼= Z2.

2. Fall endliche Ordnung• Zm ist bis auf Isomorphie die einzige zyklische Gruppe der Ordnung m

80

4.3. Nebenklassen und Faktorgruppen

• Die Ordnung von k in Zm ist mggT(k,m) , denn dies ist die kleinste Zahl l, so dass m

ein Teiler von l · k ist.• Die Erzeuger sind also die zu m teilerfremden Zahlen k.• Die Untergruppen von Zm sind von der Form

〈n〉 = nZm :={0, n, 2n, . . . ,

(mn − 1

)n} ∼= Zm

n

für alle Teiler n von m, wobei 1Zm = Zm und mZm = {0}. Die von einem belie-bigen Element k erzeugte Untergruppe ist von ggT(k,m) erzeugt und zu Z m

ggT(k,m)

isomorph.• Die homomorphen Bilder von Zm sind die Zk für Teiler k von m.• Aut(Zm) wird im Abschnitt ?? näher bestimmt.


Definition: Gruppenoperationen auf TeilmengenSei (G, ·, e) eine multiplikativ geschriebene Gruppe. Es ist zunächst nützlich, die Grup-penoperation notationell auf Teilmengen von G auszudehnen, indem man für X,Y ⊆ Gdefiniert:

X · Y := {x · y | x ∈ X, y ∈ Y }X−1 := {x−1 | x ∈ X}

Außerdem schreibt man x0 · Y für {x0} · Y und analog X · y0 für X · {y0} und lässt dieMultiplikationspunkte auch weg. Man kann sich leicht davon überzeugen, dass gewisseRechneregeln auch für die Multiplikation von Teilmengen gelten; beispielsweise ist sieassoziativ und es gilt g−1gX = eX = X. Es ist aber Vorsicht geboten; zum Beispiel istX ·X−1 · Y im allgemeinen verschieden von Y !Für additiv geschriebene Gruppen definiert man analog X + Y und −X.

Definition: (Fehlender Inhalt: Namen finden)Sei nun U ⊆ G. Man definiert eine zweistellige Relation U∼ durch

g1 U∼ g2 :⇐⇒ g−11 · g2 ∈ U.

U∼ ist eine genau dann eine Äquivalenzrelation, wenn U eine Untergruppe von G ist.

Beweis zu: Bedingung Äquivalenzrelation

81

4. Gruppen

Wegen g U∼ g ⇔ e = g−1 · g ∈ U ist die Relation genau dann reflexiv, wenn e ∈ U .Weiterhin gilt g U∼ h ⇔ g−1 · h ∈ U ⇔ h−1 · g = (g−1 · h)−1 ∈ U−1 ⇔ h U−1∼ g.Umgekehrt hat man: u ∈ U ⇔ e−1u ∈ U ⇔ e U∼ u und u−1 ∈ U ⇔ u−1e ∈ U ⇔ u U∼ e.Die Relation ist also genau dann symmetrisch, wenn U = U−1.Schließlich: Falls g U∼ h und h U∼ i, so hat man g−1h ∈ U und h−1i ∈ U , alsog−1i = g−1hh−1 ∈ U · U , d. h. g UU∼ i. Umgekehrt: sind g, h ∈ U , so ist g−1 U∼ eund e U∼ h, und außerdem gilt gh ∈ U ⇔ g−1 U∼ h. Die Relation ist also genau danntransitiv, wenn U = U · U .

Definition: LinksnebenklassenWenn U 6 G, so heißen die Äquivalenzklassen von U∼ Linksnebenklassen von U in G.Die Äquivalenzklasse von g ∈ G ist dabei von der Form gU := {gu | u ∈ U}. Die Mengeder Linksnebenklassen von U in G wird mit G/U bezeichnet

Definition: (Fehlender Inhalt: Namen finden)Weiter definiert man ∼U durch

g1 ∼U g2 :⇐⇒ g2 · g−11 ∈ U

und sieht analog, dass auch ∼u genau dann eine Äquivalenzrelation ist, wenn U eineUntergruppe von G ist.

Definition: RechtsnebenklassenWenn U 6 G, so heißen die Äquivalenzklassen von ∼U Rechtsnebenklassen von U in G.Die Äquivalenzklasse von g ∈ G ist dabei von der Form Ug := {ug | u ∈ U}. Die Mengeder Rechtsnebenklassen von U in G wird mit U\G bezeichnet.

Erläuterung

• Es gilt also

gU = hU ⇐⇒ g U∼ h ⇐⇒ g−1h ∈ U ⇐⇒ g−1hU = U

undUg = Uh ⇐⇒ g ∼U h ⇐⇒ hg−1 ∈ U ⇐⇒ Uhg−1 = U

• Die Rechts- wie Linksnebenklasse von einem u ∈ U , insbesondere also von e, istuU = Uu = U .• In kommutativen Gruppen sind stets Rechtsnebenklassen gleich Linksnebenklas-

sen, d. h. es gilt gU = Ug. Im allgemeinen sind sie verschieden (z. B. in S3 dieNebenklassen einer Untergruppe der Ordnung 2).

82


Notation: Nebenklassen bei additiven GruppenIm additiven Fall schreibt man natürlich g+U für die Links- und U+g für die Rechtsne-benklasse, wobei man die additive Schreibweise üblicherweise für kommutative Gruppenreserviert, in denen beide übereinstimmen.

Sei U 6 G.(a) Alle Nebenklassen haben die gleiche Anzahl von Elementen wie U .(b) Es gibt ebenso viele Rechts- wie Linksnebenklassen.

Beweis zu: Eigenschaften der Nebenklassen(a) U → Ug, u 7→ ug ist offenbar eine Bijektion mit, da x 7→ xg−1 die Umkehrabbildungist. Ebenso ist U → gU, u 7→ gu eine Bijektion.(b) G/U → U\G, gU 7→ Ug−1 ist eine Bijektion: Es gilt

gU = hU ⇐⇒ U = g−1h ⇐⇒ g−1h ∈ U ⇐⇒ Ug−1h = U ⇐⇒ Ug−1 = Uh−1

also ist die Abbildung wohldefiniert und injektiv, und Ug 7→ g−1U ist die ebenso wohl-definierte Umkehrabbildung.

[Satz von Lagrange] Wenn G endlich ist und U 6 G, dann gilt

|G| = |U | · |G : U |,

wobei |G : U | := |G/U | = |U\G| der Index von U in G ist. Die Ordnung einer Untergrup-pe teilt also die Gruppenordnung; insbesondere teilt die Ordnung eines Gruppenelementesdie Gruppenordnung.

BeispielAnwendungsbeispiel:Wenn G eine Gruppe ist, deren Ordnung |G| = p eine Primzahl ist, und g ∈ G \ {e},dann ist die Ordnung von g ungleich 1 und teilt p, ist also gleich p. Also ist G zyklisch∼= Zp und jedes Element 6= e ist ein Erzeuger von G.Bis auf Isomorphie gibt es also nur eine Gruppe von jeder Primzahlordnung. Für zu-sammengesetzte Zahlen gibt es i. a. mehrere nicht isomorphe Gruppen, z. B. gibt es diekommutative Gruppe Z6 und die nicht-kommutative Gruppe S3 der Ordnung 6. Auch fürOrdnung 4 gibt es zwei nicht-isomorphe Gruppen; für Ordnung 8 bereits fünf. (Allerdingsgibt es bis auf Isomorphie auch nur eine Gruppe der Ordnung 15.)

Sei nun φ : G→ H ein Gruppenhomomorphismus. Dann induziert φ, wie jede Abbildung,eine Äquivalenzrelation auf G, nämlich

g1 ∼φ g2 :⇐⇒ φ(g1) = φ(g2).

83

4. Gruppen

Es gilt nun

g1 ∼φ g2 ⇐⇒ e = φ(g1)−2 · φ(g2) = φ(g−11 · g2) ⇐⇒ g1 Kern(φ)∼ g1

⇐⇒ e = φ(g2) · φ(g1)−2 = φ(g2 · g−11 ) ⇐⇒ g1 ∼Kern(φ) g2

Die Äquivalenzklassen von ∼φ sind also die Rechts- wie Linksnebenklassen des Kerns vonφ.

Definition: Normale UntergruppeEine Untergruppe U von G heißt normale Untergruppe (oder Normalteiler), falls U∼und ∼U die gleiche Relation sind, also falls Linksnebenklassen und Rechtsnebenklassenübereinstimmen. Man schreibt dafür U 6CG.

ErläuterungKerne von Homomorphismen sind also normale Untergruppen. In kommutativen Grup-pen sind offenbar alle Untergruppen normal. Außerdem sind {e} und G stets normaleUntergruppen einer Gruppe G.Eine Untergruppe U vom Index 2 ist normal, denn da U eine Rechts- wie Linksneben-klasse ist, ist G \U die jeweils andere Nebenklasse, also auch eine Rechts- und Linksne-benklasse.Die von einer Transposition erzeugten Untergruppen der S3 vom Index 2 sind die kleinstenBeispiele von nicht normalen Untergruppen.

Definition: KongruenzrelationEine Äquivalenzrelation ∼ auf einer Gruppe G heißt Kongruenzrelation, falls die MengeG/∼ der Äquivalenzklassen so zu einer Gruppe gemacht werden kann, dass die natürlicheAbbildung G→ G/∼, g 7→ g/∼ ein Homomorphismus ist.

(Fehlender Inhalt: Hängender Absatz) r Gruppe ist genau dann eine Kongruenz-relation, wenn die Festlegung

(g/∼) · (h/∼) := (g · h)/∼

wohldefiniert ist, wenn also die äquivalenzklasse des Produktes unabhängig von der Wahlder Repräsentanten ist. (Die Existenz des neutrales Elements und der Inversen ergibt sichdann automatisch als e/∼ bzw. als (g/∼)−1 = (g−1/∼.)

Die Kongruenzrelationen für Gruppen sind genau die Nebenklassenrelationen normalerUntergruppen.

84


Beweis zu: Bedingungen Kongruenzrelation∼ ist genau dann eine Kongruenzrelation, wenn die natürliche Abbildung G→ G/∼ einHomomorphismus ist; also ist sie nach den überlegungen oben die Nebenklassenrelationdes Kerns.Sei umgekehrt N eine normale Untergruppe und g1N = g2N,h1N = h2N , also g2 = g1nund h2 = h1n

′ mit n, n′ ∈ N . Wegen h1N = Nh1 ist nh2 = h1n′′ für ein n′′ ∈ N . Es

folgt g2h2 = g1nh1n′ = g1h1n

′′n′ ∈ g1h1N und somit g2h2N = g1h1N .

Definition: Faktorgruppe, QuotientengruppeIst N eine normale Untergruppe von G, so heißt die Gruppenstruktur auf der MengeG/N der Nebenklassen von N in G die Faktorgruppe oder Quotientengruppe von G nachN .

[Homomorphiesatz] Ist φ : G→ H ein Gruppenhomomorphismus, so kann man φ zusam-mensetzen als Komposition der folgenden Homomorphismen:

G −→ G/Kern(φ)∼=−→ Bild(φ) −→ H

g 7→ gKern(φ) 7→ φ(g) 7→ φ(g)

surjektiv bijektiv injektiv

Erläuterung

G -

Kern(φ)

g1Kern(φ)

...

gnKern(φ) 7→

7→

7→

H

e

φ(g1)

φ(gn)

•

•

...

•Bild(φ)

Beispiel

• Die Abbildung Z → Zm, die den Rest bei der Division durch m angibt, ist einsurjektiver Homomorphismus mit Kern mZ. Die Faktorgruppe Z/mZ ist somitisomorph zu Zm. Der Unterschied zwischen den beiden Gruppen besteht darin,dass die Gruppenelemente von Z/mZ Mengen von ganzen Zahlen sind, wobei die

85

4. Gruppen

Addition die gewöhnliche Addition von Z auf den Repräsentanten ist; die Elementevon Zm dagegen sind die ganzen Zahlen 0, . . . ,m− 1, die Addition darauf ist aberdie „Addition modulo m“.• Das Signum sgn : Sn → ({±1}, ·) ∼= Z2 ist ein Homomorphismus, dessen Kern die

Alternierende Gruppe An ist. Es gilt also Sn/An ∼= Z2.

Die Drehgruppe D des Würfels permutiert die vier Raumdiagonalen des Würfels;dadurch erhält man einen Homomorphismus D → S4, von dem man sich überzeu-gen kann, dass er injektiv ist. Da beide Gruppen die gleiche Anzahl von Elementenhaben, ist also D ∼= S4. Außerdem permutiert D die drei Mittelsenkrechten desWürfels; dadurch erhält man einen Homomorphismus S4 ∼= D → S3, der surjektivist und dessen Kern die sogenannte Kleinsche Vierergruppe ist.

Für n > 5 hat die Sn keine anderen normalen Untergruppen außer {e}, An und Sn.Damit hängt zusammen, dass es für Polynomgleichungen vom Grad mindestens 5keine allgemeine Lösungsformel mit Wurzelausdrücken gibt.• det : GL(n,R) → (R \ {0}, ·) ist ein surjektiver Gruppenhomomorphimus, dessen

Kern die Gruppe SL(n,R) der Matrizen der Determinante 1 ist. Die Determinanteliefert also auch einen Homomorphismus der linearen Abbildungen Rn → Rn in diemultiplikative Gruppe von R, dessen Kern die orientierungs- und volumenerhalten-den Abbildungen sind.• Normale Untergruppen der S3 sind {e}, A3 und S3; die drei zu Z2 isomorphen

„Spiegelungsgruppen“ sind nicht normal.

ErläuterungUntergruppen und homomorphe Bilder bieten die Möglichkeit, aus einer Gruppe „klei-nere Teile“ zu gewinnen und u.U. die Struktur der Gruppe zu verstehen, indem manz. B. die Struktur eines Normalteilers und der zugehörigen Faktorgruppe analysiert. Dieeinfachste Möglichkeit, wie eine Gruppe aus zwei oder mehreren Bausteinen zusammenge-setzt werden kann, ist durch die folgende Konstruktion des sogenannte direkten Produktsbeschrieben:

Definition: Direktes ProduktDas direkte Produkt G1 × · · · × Gn von Gruppen (G1, ·), . . . , (Gn, ·) ist das kartesischeProdukt der zugrundeliegenden Mengen mit der komponentenweise Operation

(g1, . . . , gn) · (h1, . . . , hn) := (g1 · h1, . . . , gn · hn).

Man sieht leicht, dass das direkte Produkt wieder eine Gruppe ist mit neutralem Ele-ment (eG1 , . . . , eGn) und Inversem (g1, . . . , gn)

−1 = (g−11 , . . . , g−1n ). Sind alle Gruppenkommutativ, so ist auch das direkte Produkt kommutativ.

Erläuterung

86


Es gibt „natürliche“ Isomorphismen zwischen (G1 × G2) × G3, G1 × (G2 × G3) undG1 ×G2 ×G3, die notationell im Verschieben bzw. Weglassen der Klammern bestehen.üblicherweise unterscheidet man in der Mathematik daher nicht zwischen diesen dreiObjekten (und analog für größere n), d. h. man begeht hier oft eine Art „Typenfehler“.Beispiel

• Die Gruppentafel von Z2 × Z2 ist:

+ (0, 0) (1, 0) (0, 1) (1, 1)

(0, 0) (0, 0) (1, 0) (0, 1) (1, 1)(1, 0) (1, 0) (0, 0) (1, 1) (0, 1)(0, 1) (0, 1) (1, 1) (0, 0) (1, 0)(1, 1) (1, 1) (0, 1) (1, 0) (0, 0)

Man sieht, dass alle Elemente 6= (0, 0) die Ordnung 2 haben. Diese Gruppe istalso nicht isomorph zu Z4. (Man kann zeigen, dass es keine weiteren Gruppen derOrdnung 4 gibt: jede ist entweder zu Z4 oder zu Z2 × Z2 isomorph.)• In Z2 × Z3 dagegen sieht man leicht, dass das Element (1, 1) die Ordnung 6 hat,

dass also Z2 × Z3 zyklisch ist und damit zu Z6 isomorph.Allgemein gilt, dass die Ordnung eines Elementes (g1, . . . , gn) in G1× · · · ×Gn daskleinste gemeinsame Vielfache der Ordnungen der gi ist.• Die Symmetriegruppe D4 eines Quadrats hat eine normale, zu Z4 isomorphe Unter-

gruppe, nämlich die Drehungen des Quadrats, und zu Z2 isomorphe Untergruppen,die von jeweils einer Spiegelung erzeugt werden. D4 ist also von einer Drehung (um90◦ bzw. um 270◦) und von einer (beliebigen) Spiegelung erzeugt (denn die davonerzeugte Untergruppe enthält mit den Drehungen und einer Spiegelung mindestens5 Elemente, und es gibt keinen echten Teiler von 8 = |D4|, der mindestens 5 ist).D4 ist aber nicht isomorph zu Z4×Z2, da D4 nicht kommutativ ist. Dies ist also einBeispiel einer Gruppe, die auf kompliziertere Weise aus zwei Bausteinen aufgebautist. (Analog gilt dies auch schon für S3, die Symmetriegruppe eines gleichseitigenDreiecks).

87

5. Ringe

5.1. Ringe

Definition: Unterring, Ideal

• Ein Unterring U von R ist eine Teilmenge, die 0 und 1 enthält und unter +,−, ·abgeschlossen ist, d.h. bezüglich der auf U eingeschränkten Operation selbst einRing ist (mit gleichem Einselement)• Ein Ideal von R ist eine additive Untergruppe I mit der Eigenschaft: r ∈ R, i ∈ I :r · i ∈ I, i · r ∈ I

BeispielmZ sind Ideale von Z

Definition: (unitärer) RinghomomorphismusEin (unitärer) Ringhomomorphismus ψ : R→ S (R,S Ringe mit Eins) ist eine Abbildungmit folgenden Eigenschaften:• ψ(r + r′) = ψ(r) +S ψ(r

′)

• ψ(0k) = 0S

• ψ(−r) = −ψ(r)• ψ(r ·R r′) = ψ(r) ·S ψ(r′)• ψ(1R) = 1S

Beispiel

ψ : R→M2(R), r 7→(r 00 0

)Die Eigenschaften 1-4 sind erfüllt, die fünfte Eigenschaft nicht. Das Bild(ψ) ist bzgl. +und · ein Ring hat aber ein anderes Einselement als M2(R)

Die Kerne von Ringhomomorphismus sind genau die Ideale, d.h. Kongruenzrelationen vonRingen sind genau die Nebenklassenzerlegungen bzgl. Idealen: Ker(ψ) = {r ∈ R|ψ(r) =0}

Beweis zu: Kern von Ringhomomorphismen

89

5. Ringe

(Fehlender Inhalt: Beweis, S. 51)Beispiel(Fehlender Inhalt: Beispiele)

Definition: Teiler, Einheiten, kgVR kommutativer Ring mit Eins.• a, b ∈ R: ”a teilt b”, ”a ist ein Teiler von b”, ”b ist ein Vielfaches von a”, wenn einc ∈ R existiert mit a · c = b⇔ b ∈ aR⇔ b ·R ⊆ aR Man schreibt a|b.• Eine Einheit in R ist ein Element r ∈ R, das ein multiplikatives Inverses besitzt,

d.h. ein Element r−1 mit r · r−1 = 1. Die Menge der Einheiten von R wird mit R∗

bezeichnet.• in allgemeinen Ringen k ist kgV von r1, . . . , rn ⇔ r1|k, . . . rn|k und für alle e

mit r1|l, . . . , rn|l gilt k|l. (Teilbarkeit ist Quasi-Ordnung (d.h. transitiv) und k istminimales Element unter den gemeinsamen Vielfachen von r1, . . . , rn)

BeispielTeiler:• Z : 2|6,−2|6, 2| − 6,−2| − 6

• In R[X] : x+ 1|x1 − 1 = (x+ 1)(x− 1)

• −5x2 + 5|x2 − 1 = −13(−5x

2 + 5)

BeispielEinheiten:• Z∗ = {1,−1}• Z/12Z∗ = {1, 5, 7, 11}• R[X]∗ = R\{0} als konstante Polynome

ErläuterungFalls es e1, e2 ∈ R∗ gibt, dann gilt a|b ⇔ e1a|e2b ⇔ (e1 · a) · (e−1 · c) = e−12 e2b ⇔(e1 · a)(e−11 · e2 · c)) = e2b.

• In allgemeinen Ringen muss kein kgV existieren!• Falls k ein kgv von r1, . . . , rn ist und e ∈ R∗, dann ist auch e · k ein kgV vonr1, . . . , rn.• Analog für ggT!

Definition: NullteilerEin Nullteiler in R ist ein Element a ∈ R\{0}, so dass ein b ∈ R\{0} existiert mit a ·b = 0(d.h nicht trivialer Teiler der Null).

90

5.2. Die endlichen Ringe Z/mZ

Beispiel

• Z/12Z : 3 · 4 = 12 = 0, 6 · 4 = 24 = 0

• Z und R[X] haben keine Nullteiler!

• Eine Einheit kann nie Nullteiler sein• falls R endlich, dann ist jedes r ∈ R\{0} entweder Einheit oder Nullteiler

Beweis zu: Einheiten, Nullteiler(Fehlender Inhalt: Beweis Einheit, Nullteiler)

Definition: EinheitengruppeWenn R kommutativer Ring (mit Eins), dann ist (R∗, ·) eine kommutative Gruppe mitneutralem Element 1. Falls r ∈ R∗, dann auch r−1 ∈ R∗ R∗ heißt Einheitengruppe vonR.

Beispiel

• (Z∗, ·) = ({±1}, ·)• (R[X], ·) = (R\{0}, 0)• ((Z/12Z)∗, ·) = Z2 × Z2


Notation: Endliche Ringe(Fehlender Inhalt: Notation Z/mZ)

Z/mZ ist genau dann ein Körper, wenn m Primzahl.

Beweis zu: Bedingung endliche Ringe sind Körper(Fehlender Inhalt: Beweis)ErläuterungFür n > 2, p Primzahl gibt es einen endlichen Körper Fpn mit |Fpn | = pn. (Fpn ,+) =Z/pZ× · · · × Z/pZ (n−Mal). (Fpn\{0}, ·) = Z/pn − 1Z× . . .Z

(Z/mZ)∗ besteht aus den Nebenklassen der zu m teilerfremden Zahlen.

Beweis zu: Nebenklassen(Fehlender Inhalt: Beweis zu Nebenklassen)

91

5. Ringe

Definition: Eulersche φ-Funktion|(Z/mZ)∗| = die Anzahl der Zahlen ∈ {1, . . . ,m− 1}, die zu m teilerfremd sind = φ(m),die eulersche Phi-Funktion.

Berechnung der eulerschen φ−Funktion:• φ(p) = p− 1 p Primzahl• φ(pq) = p · q − q − p+ 1 = (p− 1)(q − 1) für p, q Primzahlen• allgemeine Formel (noch ohne Beweise) Sei n = pα1

1 · pαkn in Primfaktorzerlegung.φ(n) = pα1−1

1 (p1 − 1) · · · · · pαk−1k (pk − 1)

Beispiel

• φ(12) = 21 · (2− 1) · (3− 1) = 2 · 1 · 2 = 4, da n = 12 = 22 · 3• φ(155) = 4 · 30 = 120, da n = 5 · 31 = 155

• φ(72) = 23(2− 1) · 3 · (2− 1) = 24, da 72 = 23 · 32.

Satz von Lagrange: g ∈ G endlich Gruppe: ord(g)||G|

Satz von Euler: Ist m = p Primzahl, dann aφ(m) ≡ 1, d.h. ggt(a,m) = 1.

kleiner Satz von Fermat: Falls p 6 |a, dann gilt ap−1 ≡ 1modp. Für alle a gilt ap ≡ amod p.

Beispiel

• 51000000 mod 7 = (52)50000 mod 7 = 4500000 mod 7 = (42)250000 mod 7 = 2250000

mod 7

• 51000000 mod 7 = 57·q+r mod 7 = 57·q · 5r mod 7 = 5q · 5r = 5q+r

Wie berechnet man ab mod n?• 10011 mod 7

1. 100 mod 7 = 2⇒ 10011 mod 7 = 211 mod 7

2. 22·5+1 mod 7 ≡ (22)5 · 2 mod 7 ≡ 45 · 2 ≡ (42)2 · 4 · 2 mod 7 = 22 · 4 · 2mod 7 = 2 · 2 mod 7 ≡ 4 mod 7

• 51000000 mod 7, φ(7) = 7− 1 = 6:(56)166666 · 54 = 1166666 · 54 (kleiner Satz von Fermat) = (52)2 ≡ 42 = 2

92


• 51000000 mod 7 = (57)142857 · 5 = 5142858 · 5 mod 7 etc.• 51000000 mod 12? φ(12) = 4

(54)250000 = 1250000 = 1 mod 12

ErläuterungAnwendung:Problem: gegeben n ∈ N ist n Primzahl? Definition testen dauert zu lange. Fermat-Test:Prüfe für ausgewählte Zahlen a, ob der kleine Satz von Fermat gilt, d.h. ob an−1 mod n ≡1 Falls nein, handelt es sich um keine Primzahl, falls ja: keine Aussage. Problem: es gibtsogenannte Carmichael-Zahlen, die den Test immer bestehen, aber keine Primzahlen sind(z.B. 561). Davon gibt es unendlich viele. Zudem kann man nicht gut quantifizieren, wiegroß die Wahrscheinlichkeit ist, dass ein zusammengesetzt Zahl den Test besteht.

RSA-Verschlüsselung (Rivest, Shamin, Adlenan)Eine Nachricht soll für einen Spion zwischen A und B unlesbar übertragbar werden.Vorgehen:

1. B wählt zwei große, verschiedene, unbekannte Primzahlen p und q. Dann gilt n =p · q, φ(n) = (p− 1)(q − 1).

2. B wählt ein zu φ(n) teilerfremdes, ”zufälliges” e: öffentlicher Schlüssel: n und e,privater Schlüssel p, q, φ(n).

3. Nachricht wird ”geschickt” in Zn kodiert, d.h. eine Nachricht ist ein Tuppel(a1, . . . , ak) ∈ Zkn. Geheimverschlüsselung ist (ae1, . . . , aek) in Zkn

4. Entschlüsselung: B rechnet Inverses d = e−1 in ()Z/phiZ,+, ·) aus, d.h. d · e ≡mod φ(n) (mit dem euklidischen Algorithmus).

5. B berechnet ((ae1)d, . . . , (aek)d) in Zkn.

Beweis zu: RSA-Verfahren(Fehlender Inhalt: Beweis RSA-Verfahren)

Definition: direktes ProduktSeien R1, . . . , Rn Ringe (mit Eins). Dann wird R1 × · · · × Rn durch komponentenweiseAddition und Multiplikation zu einem Ring mit Eins, genannt das ”direkte Produkt”.Wenn alle Ri kommutativ, ist auch R1 × · · · ×Rn kommutativ.

ErläuterungAchtung: Falls R1, . . . , Rn Körper und n ≥ 2, dann ist R1 × · · · ×Rn kein Körper. Aber:Falls r1 ∈ R∗1, . . . , rn ∈ R∗n, dann ist (r−11 , . . . , r−1n ) = (r1, . . . , rn)

−1

Beispiel

93

5. Ringe

n = 2: (0, 1) 6= (0, 0) hat aber kein Inverses. Zudem hat R1 ×R2 mit (0, 1)(1, 0) = (0, 0)Nullteiler.

(Fehlender Inhalt: vielleicht auch Notation?) (R1 × · · · ×Rn)∗ = R∗1 × · · · ×R∗n

Chinesischer Restsatz: Seien m1, . . . ,mn paarweise teilerfremde Zahlen. Dann ist

Z/(m1 · · · · ·mn) ∼→ Z/m1Z× · · · × Z/mnZa+m1 · · · · ·mn 7→ (a+m1Z, . . . , a+mnZ)

ein Ringisomorphismus.

Beweis zu: Chinesischer Restsatz(Fehlender Inhalt: Beweis Chinesischer Restsatz)

Folgerung: Die Abbildung ist surjektiv, d.h. für gegebene Reste r1, . . . , rn existiert stetsein a mit

a ≡ r1 mod m1

a ≡ rn mod mn

Falls a eine Lösung ist, sind a+m1 · · · · ·mnZ sämtliche Lösungen!

Wie findet man ein solches a?• n = 2, ggT (m1,m2) = 1: Es existiert a1, a2 ∈ Z mit a1m2 + a2m2 = 1. a =r2a1m1 + r1a2m2 ist Lösung des Kongruenzssystem.• Allgemein per Induktion: Annahme:

bn−1 = r1 mod m1

. . .

bn−1 = rn−1 mod mn−1

Suche nun mit dem Fall n = 2 ein a mit

a = bn−1 mod m1 · · · · ·mn−1

a = rn mod mn

Das gefundene a ist das gesuchte.

Beweis zu: Finden eines a

94


(Fehlender Inhalt: Beweis zu Finden eines a)

Folgerung aus dem chinesisch Restsatz: Sei n = pα11 · · · · ·p

αkk ∈ N in Primfaktorzerlegung.

Dann sind die pα11 , . . . , pαkn paarweise teilerfremd!

Dann gilt:Z/nZ = Z/pα1

1 Z× · · · × Z/pαkkund

(Z/nZ)∗ = (Z/pα11 )∗ × · · · × (Z/pakk Z)∗

Also φ(n) = |(Z/mZ)∗| = φ(pα11 · · · · · φ(p

akk )

φ(pa) = (p− 1)pα−1 für p Primzahl.

Beweis zu: für Primzahl(Fehlender Inhalt: Beweis zu für Primzahl)ErläuterungAnwendungen:• Alter ISBN-Code: (a1, . . . , a9) eigentliche Information a1, . . . a9 ∈ {0, . . . , 9, X} ⊆Z11 = F11. Hinzugefügt wird eine Prüfziffer a10 so, dass

10∑i=0

i · ai = 0 in F11

Da F11 Körper mit 10 6= 0, existiert 10−1 = (−1)−1 = −1 = 10.– Code erkennt einen Fehler– Code erkennt Vertauschungen von 2 Ziffern

• Ausblick Quadrate in (Z/nZ)∗: p Primzahl p−12 Quadratzahlen in (Z/pZ)∗.Beweis zu: Eigenschaften von ISBN-Code(Fehlender Inhalt: Beweis zu Eigenschaften von ISBN-Code)

95

Teil III.

Analysis mehrerer Veränderlicher

97

6. Vorüberlegungen

6.1. Stetigkeit

Definition: offene Untermenge, abgeschlossene Untermenge

• offene Untermenge: O ⊆ R ist offen ⇔ ∀x ∈ O∃ε > 0 mit (x− ε, x+ ε) ⊆ 0 ⇔= isteine Vereinigung von offenen Intervallen.• A ⊆ R ist abgeschlossen⇔ R\A ist offen⇔ für jede konvergente Folge mit an ∈ A

ist auch der Grenzwert in A.• R, ∅ sind offen und abgeschlossen.

Definition: Stetigkeit im PunktFür jede offene Menge O ⊆ R mit f(x0) ∈ O gibt es eine offene Menge x0 ∈ O′, so dassO′ ⊆ f−1(O) .

Notation: mehrdimensionale FunktionWie versteht man Funktionen f : Rn → Rm:

Graph von f = {(x1, . . . , xn, f1(x1, . . . , xn), . . . , fm(x1, . . . , xn)} ⊆ Rn+m

Definition: Stetigkeitf : Rn → Rm stetig ⇔ Komponentenfunktionen f1, . . . , fm stetig.

Definition: WegEin Weg ist eine stetige Funktion g : (−ε, ε)→ R2, g(0) = (0, 0)

Beispiel

f : R2 → R (x, y) 7→

{x·y

x2+y2falls (x, y)f(0, 0)

0 für (x, y) = (0, 0)Für jedes feste x0 ∈ R bzw. y0 ∈ R

sind die Funktionen Fy0 : R → R, x 7→ f(x0, y) bzw. fx0 : R → R, y 7→ f(x0, y) stetig.Aber f ist nicht stetig in (0, 0). (Einzusehen an der Folge ( 1k ,

1k ), k ≥ 1).

99

6. Vorüberlegungen

• Die Verknüpfung stetiger Funktionen ist stetig• Addition und Multiplikation sind stetig• alle Polynomfunktionen sind stetig• exp : R→ R, x 7→ ex R3 → R, (x, y, z) 7→ ey ist stetig.• Die Projektion (Auswahl von Teilkomponenten) Rn → Rm,m < n; (x1, . . . , xn) 7→(xi1, . . . , xim) ist stets stetig.

100

7. Differentialrechnung

7.1. Differenzierbarkeit

Definition: Höherdimensionale DifferenzierungZunächst nur für F : Rn → R.• n = 2: f : R → R Annäherung von f durch ”Tangentialebene” im Punkt

(x0, y0, f(x0, y0)):

f ′(x, y) = f(x0, y0) + a(x− x0) + b(y − y0) +R(x, y)

wobei a die Steigung der Tangentialebene in x−Richtung ist, b die Steigung iny−Richtung und R(x, y) der Rest. Der Rest geht ”schnell” gegen 0 für (x, y) →(x0, y0).• Eine Funktion f : Rn → R ist (total) differenzierbar in x0 = (x01, . . . , x0n), wenn

es eine lineare Abbildung A : Rn → R gibt mit f(x1, . . . , xn) = f(x0) + A · (x −x) +R(x), wobei lim

x→x0||R(x)||||x−xo|| für alle Ri

• Falls F in x0 differenzierbar ist, dann ist die lineare Abbildung A eindeutig be-stimmt• A heißt (totale) Ableitung bzw. (totales) Differential von f im Punkt x0, man

schreibt f ′(x0) oder Df(x0)

• A kann als Matrix geschrieben werden:(δf(x0δx1

, . . . , δf(x0)δxn

)·

x1 − x01. . .x1 − x0n

Die Matrix

heißt Jacobi-Matrix (bei Rn → R auch Gradient) von f an x0 die Einträge sind diepartiellen Ableitungen von f in x0.• δf

δxi(x0) = ”Steigung der Tangentialhyperebene” in xi−Richtung im Punkt

(x0, f(x0)) am Graph von f .• Definiere gi : R→ R als y 7→ f(x01, . . . , x0i−1, y, x0i+1, . . . , x0n): δf

δxi(x0) = g′i(x0i)

Beispiel

101


f(x1, x2, x3) = 3x1x2 + 4x33x1 Jacobi-Matrix an (1, 1,−2)?

g1(x1) = 3 · 1 · x1 + 4 · (−2)3 · x1 = −29x1g′1(x1) = −29g′1(1) = −29g3(x3) = 3 + 4x33

g′3(x3) = 12x23

g′3(−2) = 48

g2(x2) = 3x2 − 32

g′2(x2) = 3

g′2(1) = 3

Jacobi-Matrix von f an (1,−1,−2) : (−29, 3, 48)

Definition: Jacobi-Matrix im Fall Rn → Rm δf1δx1

(x0) . . . δf1δxn

(x0)

. . .δfmδx1

(x0) . . . δfmδxn

(x0)

BeispielDifferenzierbarkeit in 0

• x 7→√x2: - 10 - 5 5 10

2

4

6

8

10

nicht differenzierbar in 0

• x 7→ x2: - 10 - 5 5 10

20

40

60

80

100

differenzierbar in 0

102

7.1. Differenzierbarkeit

• x 7→√x21 + x22

- 10- 5

05

10

- 10- 5

05

10

0

5

10

nicht differenzierbar in (0, 0)

• x 7→ x21 + x221

- 10- 5

05

10

- 10- 5

05

10

0

50

100

150

200

differenzierbar (0, 0)

• x 7→ |x1|+ x22:

- 10- 5 0 5

10

- 10- 5

05

100

50

100

nicht differenzierbar in (0, 0)

Definition: Richtungsableitungf : Rn → R, v ∈ Rn: Die Richtungsableitung von f in Richtung v ist Dvf(x) = δf

δv (x0) =f(x0+tv−f(x0)

t

ErläuterungWenn e1, . . . , en die Standardbasis, dann ist δf

δei= δf

δxi

f : Rn → R, v ∈ Rn, v = (v1, . . . , vn). Dann:• Wenn f in x0 (total) differenzierbar ist, dann existieren alle Richtungsableitungen.

• Falls f in x0 differenzierbar ist, gilt δfδv (x0) = f ′(x) · v =

i=1∑n

δfδxi

(x0 · vi = δfδx1

(x0 =

. . . δfδxn (xn)

103


|δfδv

(x0| = |grad(f)(x0) · v|

= ||grad(f)(x0)|| · ||v|| · | cos(]grad(f)(x0), v)|

d.h. der Gradient zeigt in die Richtung maximaler Steigung/Gefälle

Ableitungsregeln• Linearität: Falls f, g : Rn → Rm differenzierbar in x0 und r ∈ R, dann sind auch f+g, r ·f in x0 differenzierbar mit D(f +g)(x0) = Df(x0)+Dg(x0) und D(rf)(x0) =r ·Df(x0)• Produktregel Falls f, g : Rn → R differenzierbar in x0, dann ist auch f · g : Rn →

R, x 7→ f(x) · g(x differenzierbar in x0 mit D(f · g)(x0) = f(x0) ·Dg(x0)+Df(x0) ·g(x)

• Kettenregel Falls f : Rn → Rm differenzierbar in x0 und g : Rm → Rl differenzier-bar in f(x0), dann g ◦ f : Rn → Rl differenzierbar in x0 mit D(g ◦ f)(x0)(y) =Dg(f(x0)) ◦Df(x0)(y)• Umkehrabbildung f : Rn → Rn bijektiv, differenzierbar in x0, f−1 sei stetig inf(x0), det(Df(x0) 6= 0 (d.h. Df(x0) ist invertierbar) Dann ist f−1 differenzierbarin f(x0) und es ist Df−1(f(x0)) = (Df(x0))

−1.

7.2. Höhere Ableitungen

Erläuterung(Fehlender Inhalt: Wie ist das hier einzusortieren?)• f : R→ R, f ′(x) ∈ R differenzierbar, x 7→ f ′(x) Funktion R→ R:• Rn → Rm, f ′(x ∈ Lin(Rn,Rm), die Menge der linearen Abbildungen von Rn → Rm,x 7→ f ′(x),Rn → Lin(Rn,Rm)

Wir können für differenzierbares f : Rn → Rn die Ableitung als Funktion Rn → Rn·mauffassen.ErläuterungMan muss sich überlegen, das die Art der Identifikation von Lin(Rn,Rm) mit Rn·m nichtsan der Differenzierbarkeit ändert! Den Basiswechsel sind lineare Abbildungen und daherdifferenzierbar (nämlich ihrer eigene Ableitung).

Definition: Höhere partielle Ableitungf : Rn → R partielle Ableitung in Richtung xi im Punkt x0: δf

δxi(x0) ∈ R, d.h. δf

δxi: x0 7→

104


δfδxi

(x0) ∈ R,Rn → R Also partielle Ableitung sind ohne weiteres iterierbar!

Notation: mehrfache AbleitungenMan schreibt

•δ δfδxiδxj

= δδxj

δfδxi

= δ2fδxjδxi

• allgemein: δkfδxik...δxil

• Spezialfall: δ2fδxi

= δ2fδxiδxi

• Satz von Schwarz: Falls f zweimal (total) differenzierbar, dann ist δ2fδxiδxj

= δ2fδxjδxi

• f k−mal differenzierbar, dann kommt es bei den k−ten partielle Ableitungen nichtauf die Reihenfolge an!

BeispielWie berechnet man δ2f

δxiδxj?

f(x1, x2) = x21 · sin(x1 · x2) + x1 · ex2+e1

δf

δx1= 2x1 sin(x1 · x2) + x21 cos(x1 · x2) · x2 + ex2+xn + x1e

x1+x2

δf

δx2= x21cos(x1x2)x1 + x1e

x2+x1

δf

δx1δx2= 2x1cos(x1x2)− xs1in(x1x2)x2 + ex2+x1 + x1e

x1+x2

δ2f

δx2δx1= 2x21cos(x1x2)− x31x2sin(x1x2) + x21cos(x1x2) + ex2+x1 + x1e

x1+x2

Definition: bilineare Abildungen(Fehlender Inhalt: Definition bilinear)

Beispiel(Fehlender Inhalt: Beispiel bilineare Abbildungen)

105


2. Abbleitung w ∈ R: Wie ändert sich Drf(x0) in Richtung w?

DwDrf(x0) =n∑j=1

δ

δxj(n∑i=1

δf

δxi(x0 · vi) · wj

=

n∑i,j=1

δ2f

δxjδxi(x0)viwj

man sieht: DwDvf(x0) = (w1, . . . , wn) ·

δ2fDx21

f(x0)δ2f

Dx1x2f(x0)

δ2fDx1xn

f(x0)

δ2fDx2x1

f(x0)

. . .δ2f

Dx1x1f(x0) . . . δ2f

Dx2nf(x0)

·v1. . .vn

= w ·Hf(x0) · vT = (Hf(x0) · vT )T · wT , wobei die große Matrix Hesse-Matrix

von f an der Stelle x0 genannt wird. Sie ist nach Cauchy-Schwarz symmetrisch.Fall v = w: DvDvf(x0) ’ ’Richtungskrümmung” von f an der Stelle x0 in Richtungv = f ′′v (0) mit fv : R→ R, t 7→ f(x0 + t · v).

Definition: Maxima, Minima, Sattelpunkte

• x ∈ Rn heißt ”kritischer Punkt”, falls gradf(x) = f ′(x) = Dx(x0) = 0, eine ’hori-zontale Tangentialebene”• x ∈ Rn heißt lokales Minimum (bzw. lokales Maximum), falls es ein ε > 0 gibt mit

f(y > f(x)∀y 6= x : ||y − x|| < ε bzw. f(y) < f(x)

• alle anderen kritischen Punkte heißen Sattelpunkte• lokale Maxima und Minima sind kritische Punkte• f : Rn → R zweimal differenzierbar, x kritischer Punkt. Falls alle Richtungskrüm-

mungen in xn echt positiv sind, d.h. falls v ·Hf(x0) · vT > 0(< 0) für alle v 6= 0,liegt in x0 ein lokales Minimum (lokales Maximum) vor.

Beispiel

106


•- 10

- 50

510

- 10- 5

05

10

0

50

100

150

200

hat lokales Minimum in (0, 0).

•

- 10

- 5

0

5

10- 10

- 5

0

5

10

- 200

- 150

- 100

- 50

0

hat lokales Maximum in (0, 0).

Definition: definit

• Hf(x0) heißt positiv (negativ) definit, falls v ·Hf(x0)vT > 0(< 0) für alle v 6= 0

• Hf(x0) heißt indefinit definit, falls v1, v2 ∈ Rn gibt mit v1Hf(x0)vT1 > 0 undv2Hf(x0)v

R2 < 0.

ErläuterungEin kritischer Punkt mit indefiniter Hesse-Matrix ist ein Sattelpunkt. Achtung: Es kannsein, dass Hf(x0) weder positiv noch negativ definit ist, noch indefinit!

Definition: Hurwitz-Kriterium

• Eine quadratische, symmetrische (n×n)−Matrix A über R ist positiv definit, genaudann wenn: die Determinanten der quadratischen Teilmatrizen ab links oben alle

107


größer Null sind, d.h.:

det((a11)> 0

det(

(a11 a12a21 a22

)) > 0

det(

a11 a12 a13. . .a31 a32 a33

) > 0

. . .

det(

a11 . . . a1n−1. . .

an−1,1 . . . an−1,n−1

) > 0

det(A) > 0

• A ist negativ definit⇔ −A positiv definit, die Matrizen aus positiv definit wechselndas Vorzeichen der Determinante mit jedem Schritt (beginnend bei < 0).

Satz aus der linearen Algebra: Zu jeder symmetrische Matrix über R gibt es eine Ortho-normalbasis, so dass die Matrix bezüglich dieser Orthonormalbasis Diagonalgestalt hatmit reellen Einträgen.

(Fehlender Inhalt: Eigenwerte, S.82)ErläuterungAnwendungenhauptsächlich in Physik:• V : Rn → Rn Vektorfelder• f : Rn → R Skalarfelder• Gradientenfeld: f : R→ R grad(f) : Rn → Rn

• Divergenz: V : R3 → R3 divV : R3 → R, x 7→ δvδx1

(x) + δv1δx2

(x) + δv2δx3

(x)

• Rotation V : R3 → R3 : rot(V ) : R3 → R3, x 7→

δv3δx2

(x)− δv2δx3

(x)δv1δx3

(x)− δv3δx1

(x)δv2δx1

(x)− δv1δx2

(x)

Erläuterungtypische Ergebnisse:rot(gradf) = 0, umgekehrt (V ”schön genug”) gegeben V , dann exisitert f mit V =grad(f)⇔ rot(V ) = 0, div(rotV ) = 0.

108

8. Integralrechnung

8.1. Höherdimensionale Integration

f : R→ R: Volumenbestimmung über einem Rechteck: [a1, b1]x[a2, b2] (falls f stetig ist):

b2∫a2

b1∫a1

f(x, y)dxdy =

b1∫a1

b2∫a2

f(x, y)dxdy

Beispielf(x, y) = 2

b2∫a2

b1∫a1

2dxdy =

b2∫a2

(2x|b1a1)dxdy

=

b2∫a2

(2b1 − 2a1)dy

= (2b1 − 2a1) · y|b2a2= (2b1 − 2a1)b2 − (2b1 − 2a1)a2

= 2(b1 − a1) · (b2 − a2)

Beispiel

109

8. Integralrechnung

f(x, y) = x · y

1∫0

1∫0

xydxdy =

1∫0

1∫0

0, 5yx2|10dy

=

1∫0

(0, 5y − 0)dy

=1

4y2|10

=1

4

8.1.1. Integration über Normalgebiete in R2

Definition: Integrationsgebietg1, g2 : [a, b]→ R stetig mit g1(x) ≤ g2(x)Integrationsgebiet:

N = {(x, y) ∈ R2|a ≤ x ≤ b, g1(x) ≤ y ≤ g2(x)}

:

∫N

f(x, y)dxy :

b∫a

g2(x)∫g1(x)

f(x, y)dydx

Reihenfolge kann nicht umgedreht werden!

Definition: Höherdimensionale NormalgebieteHöherdimensionale Normalgebiete können analog definiert werden: [a, b], a1/a2 : [a, b]→R, b1, b2 : N → R N2 := {(x, y, z)|a ≤ x ≤ b, g1(x) ≤ y ≤ g2(x), b1(x, y) ≤ z ≤ b2(x, y)}

Beispiel

110


f(x, y) = 1− x− y, [a, b] = 0, 1, g1(x) = 0, g2(x) = 1− x

0∫1

g2(x)∫g1(x)

1− x− ydydx =

1∫0

0∫1−x

1− x− ydydx

=

1∫0

((1− x)y − 0, 5y2|1−x0 )dyx

=

1∫0

(1− x)2 − (1− x) · 0− 0, 5(1− x)2 − 0, 5 · 0dx

=

1∫0

0, 5(1− x)2dx

= −1

6(1− x)3|10

= 0 +1

6· 1

=1

6

BeispielSpezialfall f = 1, Normalgebiet in R2:

∫N

1dxy = Fläche von N , [a, b] = [−1, 1]; g1(x) =

−√1− x2, g2(x) = +

√1− x2

Kreisfläche (Radius 1) =1∫−1

√1−x2∫

−√1−x2

1dydx

= . . .

= π

Kugelvolumen (Radius 1) =1∫−1

√1−x2∫

−√1−x2

√1−x2−y2∫

−√

1−x2−y2

1dydx

8.1.2. Wegintegrale/Kurvenintegrale

”durch ein Skalarfeld”:

111

8. Integralrechnung

Definition: Wegintegralg : [a, b]→ Rn mit [a, b] ⊆ Rn ein stetig differenzierbarer Weg, f : Rn → R stetig”Integral von f längs des Weges g”, ”Mittelwert von f längs g”:

b∫a

f(g(t)) · ||g′(t)||dt =b∫a

f(g(t)) ·√g′1(t)

2 + · · ·+ g′n(t)2

Beispielg : [0, π2 ]→ R2.t 7→ (cos(t), sin(t)), g′(t) = (−sin(t), cos(t)), ||g′(t)|| =

√(−sin(t)2 + (cos(t)2 =

1 gleichmäßige Geschwindigkeit , genannt Bogenlängeparametrisierung:π2∫0

1dt = π2

BeispielSpezialfall: f = 1

b∫a

||g′(t)||dt = Länge der von g beschriebenen Kurve

h : [0, 1]→ R2, t 7→ (1− t,√1− (1− t)2

h′(t) = (−1, (1− t)√1− (1− t)2

)

||h′(t)|| =

√1 +

(1− t)21− (1− t)2

=

√1

1− (1− t)2

1∫0

1−

√1

1− (1− t)2= · · · = π

2

”durch ein Vektorfeld”

Definition: (Fehlender Inhalt: Was soll das sein?)

g : [a, b]→ Rn stetig differenzierbar, n = 2,b∫af(g(t)) · g′(t) · dt

Beispiel

112


n = 2, g : [−1, 1]→ R2, t 7→ (t,√a− t2), f =

(0−1

)1∫−1

<

(0−1

),

(1−t√1−t2

)dt =

1∫−1

t√1− t2

dt

= 0

Nicht behandelt:• Oberflächenintegrale• Satz von Stokes

113

Documents

Mathe-II-Skript - Lehrkörper / Mitarbeiterhome.mathematik.uni-freiburg.de/junker/skripte/scriptMatheII.pdf · UnterMitarbeitvonDavidZschockeDiesesSkriptentstehtnachundnachundsollim