Mathematik Für Informatiker
Mathematik Für Informatiker
press
[Link] ist eine Reihe, die Theorie und
Praxis aus allen Bereichen der Informatik für
die Hochschulausbildung vermittelt.
Bernd Kreußler · Gerhard Pfister
123
Dr. Bernd Kreußler Prof. Dr. Gerhard Pfister
Mary Immaculate College Fachbereich Mathematik
South Circular Road Technische Universität Kaiserslautern
Limerick 67653 Kaiserslautern
Irland Deutschland
[Link]@[Link] pfister@[Link]
DOI 10.1007/978-3-540-89107-9
c 2009 Springer-Verlag Berlin Heidelberg
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der
Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funk-
sendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in
Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Ver-
vielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der
gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. Septem-
ber 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwider-
handlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk be-
rechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der
Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann
benutzt werden dürften.
Satz: Datenerstellung durch die Autoren unter Verwendung eines Springer LaTeX-Makropakets
Einbandgestaltung: KünkelLopka, Heidelberg
987654321
[Link]
Für Andrea, Manja, Jana
B. K.
Dieses Buch richtet sich vor allem an Informatikstudenten der ersten Semes-
ter. Es ist hervorgegangen aus Vorlesungen, die von den Autoren an der TU
Kaiserslautern gehalten wurden. Der Inhalt und Stoffumfang wurden mehr-
fach in der Praxis erprobt. Da in Kaiserslautern sowohl im Frühjahr als auch
im Herbst ein Studieneinstieg möglich ist, beginnen dort einige Studenten
mit Algebra (Kapitel 1 und 2), andere jedoch mit Analysis und Diskreter
Mathematik (Kapitel 3–5). Der Text ist so aufgebaut, dass dies möglich ist.
Ein guter Informatiker benötigt ein breites mathematisches Grundwissen.
Dabei geht es nicht vordergründig um Formeln und Fakten, sondern um die
Fähigkeit, abstrakte Strukturen zu erkennen und zu verstehen. Bevor ein
Rechner ein kompliziertes Problem lösen kann, muss es in der Regel vom
Menschen (Informatiker) bearbeitet werden. Die besten Ergebnisse werden
dabei erzielt, wenn die dem Problem innewohnenden abstrakten Strukturen
erkannt und ausgenutzt werden.
Die Konzeption dieses Lehrbuches unterscheidet sich von vielen anderen Ma-
thematikbüchern vor allem in den folgenden drei Punkten:
• Jedes Kapitel beginnt mit konkreten, dem Leser vertrauten Begriffen oder
Situationen. Davon ausgehend wird schrittweise abstrahiert bis hin zu den
gebräuchlichen abstrakten Begriffen der modernen Mathematik.
• In jedem Kapitel werden viele interessante Situationen des Alltagslebens
beschrieben, in denen die zuvor eingeführten abstrakten Begriffe und die
bewiesenen Ergebnisse zum Einsatz kommen. Dabei stehen Anwendungen
im Mittelpunkt, die einen engen Bezug zur Informatik besitzen.
• Das Kapitel über Mengenlehre ist am Ende des Buches zu finden. Es kann
jederzeit unabhängig vom restlichen Text gelesen werden.
Dieses Lehrbuch besteht aus drei Teilen, die jeweils zwei Kapitel enthalten
und weitgehend voneinander unabhängig sind. Sie sind so angelegt, dass sie
im Wesentlichen einzeln verstanden werden können:
Teil I – Algebra Teil II – Analysis Teil III – Diskrete Strukturen.
vii
viii Vorwort
Teil I besteht aus den zwei Kapiteln Zahlen und Lineare Algebra. Besonderer
Wert wird auf die Vermittlung wichtiger Beweistechniken und der Methode
der Abstraktion (Äquivalenzklassenbildung) gelegt.
Im ersten Kapitel werden, ausgehend von den ganzen Zahlen, die wichti-
gen algebraischen Strukturen Gruppe, Ring und Körper erklärt. Als Anwen-
dung werden die Grundlagen der modernen Kryptographie und das RSA Ver-
schlüsselungsverfahren erläutert. Man findet auch die zur Zeit größte bekann-
te Primzahl. Im Zusammenhang mit dem Gruppenbegriff wird erläutert, was
es mit Geldscheinnummern, der ISBN und der EAN auf sich hat. Es kommt
auch der Rubik-Würfel und seine Interpretation als Gruppe vor. Im zweiten
Kapitel wird die Lineare Algebra dargestellt. Sie beschäftigt sich nicht nur
mit Verfahren zur Bestimmung von Lösungsmengen linearer Gleichungssys-
teme, sondern auch mit strukturellen Eigenschaften solcher Lösungsmengen.
Als Anwendung findet man fehlerkorrigierende Codes und deren Bedeutung
für die gute Qualität der Musikwiedergabe eines CD-Spielers.
Der Teil II enthält die Kapitel Reelle Zahlen und Folgen und Funktionen.
Zunächst werden die Grundlagen der Differential- und Integralrechnung be-
handelt. Darauf aufbauend werden verschiedene Möglichkeiten der Approxi-
mation von Funktionen diskutiert. Dies umfasst die Approximation stetiger
Funktionen durch Polynome und die Approximation periodischer Funktio-
nen durch Fourier-Reihen. Das führt schließlich zu den schnellen Fourier-
Transformationen und deren Anwendung bei der Bildkompression (JPEG-
Verfahren) und Audiokompression (MP3-Verfahren). Weitere Anwendungen,
die in diesem Kapitel besprochen werden, sind verschiedene Methoden zur
Berechnung der Zahl π und die näherungsweise Berechnung von n! für sehr
große natürliche Zahlen n.
Die Kapitel im Teil III heißen Diskrete Mathematik und Grundlagen der
Mathematik. In der Diskreten Mathematik werden die elementaren Grund-
lagen der Kombinatorik, Wahrscheinlichkeitstheorie und Graphentheorie be-
handelt. Als Anwendungen werden einerseits die Funktionsweise von Spam-
filtern und die Verwaltung großer Datenmengen mit Hashtabellen diskutiert.
Andererseits wird erklärt, wie Suchmaschinen effizient Informationen im In-
ternet finden und wie ein Routenplaner einen optimalen Weg bestimmt. Es
wir auch der mathematische Hintergrund eines Sudokus erklärt. Schließlich
werden effiziente Primzahltests, die auf Methoden der Wahrscheinlichkeits-
theorie beruhen, vorgestellt.
Das Kapitel über die Grundlagen der Mathematik beschäftigt sich mit Aus-
sagenlogik, Mengenlehre und Relationen. Darin wird das Standardvokabular
der modernen Mathematik erläutert. Es ist so angelegt, dass es mehr als nur
eine trockene, kurze und knappe Sprachschulung ist. Durch die Darstellung
einiger Bezüge zur Arbeit mit Datenbanken wird der Versuch unternommen,
die Relevanz der Grundbegriffe der Mathematik in der Informatik den Lesern
nahezubringen. Dieses Kapitel kann jeder Zeit unabhängig vom übrigen Teil
dieses Buches gelesen werden.
Vorwort ix
Teil I Algebra
1 Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Rechnen mit ganzen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Restklassen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4 Ringe und Körper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.5 Kryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2 Lineare Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.1 Lineare Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.2 Vektorräume und lineare Abbildungen . . . . . . . . . . . . . . . . . . . . 93
2.3 Anwendungen des Gaußschen Algorithmus . . . . . . . . . . . . . . . . . 110
2.4 Quadratische Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
2.5 Fehlerkorrigierende Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Teil II Analysis
4 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
4.1 Stetigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
4.2 Differentialrechnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
4.3 Potenzreihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
4.4 Integralrechnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
4.5 Approximation von Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
xi
xii Inhaltsverzeichnis
Lösungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
Symbolverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
Personenverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
Sachverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
Teil I
Algebra
Kapitel 1
Zahlen
Die ganzen Zahlen dienen als Modell für alle weiteren algebraischen Struktu-
ren, die wir in diesem Kapitel untersuchen. Als Vorbereitung auf die axioma-
tische Einführung abstrakterer Begriffe konzentrieren wir uns auf die grundle-
genden Eigenschaften der Rechenoperationen mit ganzen Zahlen. Außerdem
lernen wir das Prinzip der vollständigen Induktion und den Euklidischen
Algorithmus kennen. Das sind wichtige Werkzeuge für den Alltagsgebrauch
eines Informatikers.
Auf eine axiomatische Einführung der natürlichen Zahlen wird hier bewusst
verzichtet. Der interessierte Leser findet eine solche in [EbZ].
Für die Gesamtheit aller ganzen Zahlen hat sich das Symbol Z eingebürgert:
3
4 1 Zahlen
Die Summe, das Produkt und die Differenz (jedoch nicht der Quotient) zweier
ganzer Zahlen ist stets eine ganze Zahl. Die Addition und die Multiplikati-
on sind die Operationen auf die sich das algebraische Studium der ganzen
Zahlen gründet. Wir listen hier in aller Ausführlichkeit ihre wesentlichen Ei-
genschaften auf. Das hilft uns später, abstraktere Begriffe wie Gruppe, Ring
und Körper besser zu verstehen. Für beliebige ganze Zahlen a, b, c ∈ Z gilt:
x = x + 0 = x + (a + y) = (x + a) + y = 0 + y = y .
Wir haben also unter alleiniger Benutzung der Gesetze (1.1), (1.2) und (1.3)
gezeigt, dass die Gleichung a + x = 0 höchstens eine Lösung besitzen kann.
Das Gesetz (1.4) beinhaltet nun die Aussage, dass es eine solche Lösung
tatsächlich gibt. Ein weiteres Beispiel der ausschließlichen Benutzung der
Gesetze (1.1)–(1.8) ist die folgende Herleitung der wohlbekannten Gleichung
(−1) · (−1) = 1:
Bei der ersten Umformung benutzen wir, dass für alle ganzen Zahlen a die
Gleichung 0 · a = 0 gilt. Um dies aus den Grundregeln abzuleiten, bemerken
wir zunächst, dass die Gleichungen a · 0 = a · (0 + 0) = a · 0 + a · 0 aus
1.1 Rechnen mit ganzen Zahlen 5
(1.3) und (1.8) folgen. Nach Addition von −(a · 0) ergibt sich daraus, unter
Benutzung von (1.4) und (1.2), die Gleichung 0 = a · 0. Kommutativität der
Multiplikation (1.5) liefert schließlich 0 · a = 0.
Derartig elementare Rechnungen sind wichtig, weil wir sie auf abstraktem
Niveau wiederholen können. Im Verlauf dieses Kapitels werden wir lernen, mit
mathematischen Strukturen umzugehen, bei denen nur noch die algebraischen
Operationen an unsere konkrete Erfahrung mit ganzen Zahlen angelehnt sind,
nicht aber die Objekte, mit denen wir operieren. In Beweisen können wir dann
ausschließlich auf Grundregeln wie (1.1)–(1.8) zurückgreifen. Diese werden als
Axiome (das heißt zu Beginn vorgegebene, charakteristische Eigenschaften)
der betrachteten Struktur bezeichnet.
Die Fähigkeit, Argumentationen auf der Grundlage einer kleinen Zahl klar
vorgegebener Regeln zu führen, ist für die exakten Wissenschaften so wich-
tig, dass sie von Anfang an und kontinuierlich trainiert werden muss. Wenn
Sie die bisher angegebenen Beweise elementarer Aussagen nur überflogen ha-
ben, dann empfehlen wir Ihnen deshalb, dass Sie sich vor dem Weiterlesen
nochmals etwas intensiver damit beschäftigen.
Solche Begriffe wie Teiler und Primzahl sind dem Leser vermutlich bereits
vertraut. Wir werden sie hier kurz wiederholen, um von vornherein mit kla-
ren und einheitlichen Begriffen zu operieren. Eine derartige Vorgehensweise
ist in Mathematik und Informatik von prinzipieller Wichtigkeit, um Miss-
verständnisse, nicht funktionierende Software oder gar Milliardenverluste zu
vermeiden.
Eine ganze Zahl b heißt Teiler der ganzen Zahl a, falls es eine ganze Zahl c
gibt, so dass bc = a gilt. Wir schreiben dann b | a (sprich: b teilt a).
So hat zum Beispiel a = 6 die Teiler −6, −3, −2, −1, 1, 2, 3, 6. Die Zahl a = 0
ist die einzige ganze Zahl, die unendlich viele Teiler besitzt. Entsprechend
unserer Definition ist sie durch jede ganze Zahl teilbar. Jede ganze Zahl a
hat mindestens die Teiler −a, −1, 1, a, und wenn a 6= ±1, 0 ist, sind dies vier
verschiedene Teiler. Außer a = 0 besitzt keine ganze Zahl den Teiler 0.
Wir nennen eine Zahl a ∈ Z zusammengesetzt, wenn es ganze Zahlen b 6= ±1,
c 6= ±1 gibt, so dass a = bc. Eine von ±1 verschiedene Zahl, die nicht zusam-
mengesetzt ist, nennt man Primzahl . Da 0 = 0 · 2 gilt, ist 0 zusammengesetzt,
also keine Primzahl. Da 2 = 1 · 2 und 2 = (−1) · (−2) bis auf die Reihenfolge
der Faktoren die einzigen Darstellungen von a = 2 als Produkt zweier ganzer
Zahlen sind, ist 2 eine Primzahl.
Eine Zahl c heißt gemeinsamer Teiler von a und b falls c | a und c | b. Wir
nennen zwei Zahlen teilerfremd , wenn 1 und −1 die einzigen gemeinsamen
Teiler dieser Zahlen sind.
Definition 1.1.1. Seien a 6= 0, b 6= 0 ganze Zahlen. Wir nennen eine posi-
tive ganze Zahl d > 0 größten gemeinsamen Teiler von a und b, wenn die
folgenden beiden Bedingungen erfüllt sind:
(i) (gemeinsamer Teiler) d | a und d | b;
(ii) (Maximalität) Für jedes c ∈ Z gilt: Wenn c | a und c | b, dann gilt c | d.
6 1 Zahlen
Der Euklidische 1 Algorithmus ist einer der ältesten und grundlegendsten Al-
gorithmen der Mathematik. Uns dient er hier sowohl als Beweistechnik als
auch als Methode für konkrete Rechnungen. Sein mathematisches Kernstück
ist die Division mit Rest. Darunter verstehen wir die folgende Eigenschaft
ganzer Zahlen, die sich nicht aus den Grundregeln (1.1)–(1.8) ergibt, da die
Ordnungsrelation < darin auftritt:
Wenn a, b ∈ Z mit b 6= 0, dann gibt es ganze Zahlen r und n,
so dass a = nb + r und 0 ≤ r < |b| gilt.
1 Euklid von Alexandria wirkte um 300 v.u.Z. in Alexandria, genaue Lebensdaten und
sichere Information, ob es sich wirklich um eine einzelne Person handelt, sind nicht bekannt.
Vgl. Fußnote auf Seite 76.
1.1 Rechnen mit ganzen Zahlen 7
Die Zahl r heißt Rest von a bei Division durch b. Hier und im Folgenden
bezeichnet |b| den Betrag der ganzen Zahl b, das heißt |b| = b wenn b ≥ 0
und |b| = −b wenn b ≤ 0. Verallgemeinerungen des hier vorgestellten Euklidi-
schen Algorithmus, etwa für Polynome oder Gaußsche ganze Zahlen, beruhen
jeweils auf einer entsprechend angepassten Version der Division mit Rest.
Als Eingabedaten seien zwei positive ganze Zahlen a, b mit a > b gegeben.
Am Ende wird ggT(a, b) ausgegeben.
Jeder Schritt des Algorithmus besteht aus einer Division mit Rest, gefolgt von
einem Test, in dem entschieden wird, ob das Ende bereits erreicht wurde.
Initialisierung: A := a, B := b
Division: Bestimme N ∈ Z, so dass 0 ≤ A − N · B < B.
C := A − N · B ist der Rest von A bei Division durch B.
Test: Wenn C = 0, dann Ausgabe von ggT(a, b) := B und stopp.
Wenn C > 0, dann Division mit Rest für A := B, B := C.
Wie bei jedem Algorithmus sind zunächst folgende Fragen zu klären:
Endet dieser Algorithmus stets nach endlich vielen Schritten?
Liefert er wirklich den größten gemeinsamen Teiler?
Um diese Fragen zu beantworten, schauen wir uns den Algorithmus Schritt
für Schritt an. Wir setzen a1 := a, b1 := b. Bei jedem Schritt wird ein neues
Paar von Zahlen (ak , bk ) produziert. Das neue Paar (ak , bk ) ergibt sich für
jedes k ≥ 1 aus dem vorherigen durch folgende Formeln:
bk+1 = ak − nk bk
ak+1 = bk .
Hier ist nk eine geeignete ganze Zahl und es gilt stets 0 ≤ bk+1 < bk . Nach
dem k-ten Schritt liegt uns das Paar (ak+1 , bk+1 ) vor. Nach dem N -ten Schritt
stoppt der Algorithmus genau dann, wenn bN +1 = 0 gilt. In diesem Fall ist
0 = aN − nN · bN und für die Korrektheit des Algorithmus wäre zu beweisen,
dass bN = ggT(a, b) gilt. Schauen wir uns zunächst ein Beispiel an.
k (ak , bk ) ak − n k b k = bk+1
1 (287, 84) 287 − 3 · 84 = 35
2 (84, 35) 84 − 2 · 35 = 14
3 (35, 14) 35 − 2 · 14 = 7
4 (14, 7) 14 − 2 · 7 = 0
Wir haben hier N = 4, b4 = 7 und es gilt tatsächlich ggT(287, 84) = 7.
Bemerkung 1.1.3. Pro Schritt produziert der Algorithmus nicht zwei, son-
dern nur eine neue Zahl, nämlich bk+1 . Wenn wir b0 := a1 setzen, dann
8 1 Zahlen
können wir die Berechnung in jedem Schritt des Algorithmus auch in der
Form
bk+1 = bk−1 − nk bk
schreiben. Dabei soll wieder 0 ≤ bk+1 < bk gelten. Der Algorithmus termi-
niert, sobald bk+1 = 0 ist.
Da b1 > b2 > . . . > bn ≥ 0 und die bi ganze Zahlen sind, ist nach maxi-
mal b1 Schritten sicher die Bedingung bk+1 = 0 erfüllt. Die Endlichkeit des
Algorithmus ist damit garantiert.
Die Korrektheit des Euklidischen Algorithmus wird mittels vollständiger In-
duktion bewiesen. Da diese Beweistechnik häufig verwendet wird und hier
zum ersten Mal auftritt, stellen wir sie sehr ausführlich dar.
Beweis. Sei N die Zahl der Schritte im Euklidischen Algorithmus, das heißt
Zu zeigen ist bN = ggT(a1 , b1 ). Die Induktion wird über N , die Anzahl der
Schritte, durchgeführt.
Induktionsanfang: Als erstes beweisen wir den Satz für den Fall N = 1.
Dazu müssen wir prüfen, ob b1 die Bedingungen der Definition 1.1.1 erfüllt.
Wegen N = 1 gilt a1 = n1 · b1 und somit b1 | a1 . Zusammen mit b1 | b1 ist
das gerade die Bedingung (i) der Definition. Wenn eine ganze Zahl c Teiler
von a1 und b1 ist, dann gilt offenbar c | b1 , also ist auch die Bedingung (ii)
erfüllt. Damit haben wir gezeigt, dass b1 = ggT(a1 , b1 ), wenn N = 1 ist.
Induktionsschritt: Wir setzen voraus, dass die Behauptung des Satzes für
einen festen Wert N ≥ 1 wahr ist und wollen daraus schließen, dass sie auch
für N + 1 gilt.
Voraussetzung. Für jedes Zahlenpaar (a, b), für welches der Euklidische Al-
gorithmus nach N Schritten terminiert (d.h. 0 = aN − nN bN ), liefert uns der
Algorithmus den größten gemeinsamen Teiler, d.h. es gilt bN = ggT(a, b).
Behauptung. Für jedes Zahlenpaar (a, b), für welches der Euklidische Algo-
rithmus nach N + 1 Schritten terminiert, liefert uns dieser Algorithmus den
größten gemeinsamen Teiler.
Beweis. Sei (a, b) = (a1 , b1 ) ein Paar positiver ganzer Zahlen mit a > b, so dass
der Euklidische Algorithmus nach N +1 Schritten terminiert. Dann endet der
Euklidische Algorithmus für das Paar (a2 , b2 ) bereits nach N Schritten. Wir
können daher die Induktionsvoraussetzung auf das Paar (a2 , b2 ) anwenden
und erhalten bN +1 = ggT(a2 , b2 ). Man beachte hier die verschobene Num-
merierung. Der Erste Schritt des Algorithmus liefert uns die Gleichungen
1.1 Rechnen mit ganzen Zahlen 9
b 2 = a1 − n 1 b 1
(1.9)
a2 = b 1 ,
a1 = b 2 + n 1 a2
(1.10)
b 1 = a2 .
1 = 7−2·3
= 7 − 2 · (10 − 1 · 7) = 3 · 7 − 2 · 10
= 3 · (47 − 4 · 10) − 2 · 10 = 3 · 47 − 14 · 10
= 3 · 47 − 14 · (104 − 2 · 47) = (−14) · 104 + 31 · 47 .
Wir haben damit den größten gemeinsamen Teiler d = 1 der beiden Zahlen
a = 104 und b = 47 in der Gestalt d = r · a + s · b dargestellt. Dabei sind
10 1 Zahlen
r = −14 und s = 31 ganze Zahlen. Dies ist ganz allgemein möglich und man
kann damit sogar den größten gemeinsamen Teiler charakterisieren.
Satz 1.1.6 Seien a 6= 0, b 6= 0 ganze Zahlen. Eine Zahl d > 0 ist genau
dann der größte gemeinsame Teiler von a und b, wenn die folgenden beiden
Bedingungen erfüllt sind:
(1) Es gibt ganze Zahlen r, s, für die d = ra + sb gilt.
(2) Jede ganze Zahl der Gestalt ra + sb ist durch d teilbar.
Beweis von II. Sei nun d = ra+ sb > 0 eine ganze Zahl, welche die Bedingung
(2) erfüllt. Außerdem sei d′ = ggT(a, b). Nach dem bereits gezeigten Teil I
gibt es r′ , s′ ∈ Z mit d′ = r′ a + s′ b und d′ erfüllt die Bedingung (2). Da
d = ra + sb folgt daraus d′ | d. Weil d′ = r′ a + s′ b und d nach Voraussetzung
die Bedingung (2) erfüllt, folgt d | d′ . Daraus ergibt sich, wie bereits zuvor,
d = d′ . ⊓
⊔
Das bisher erworbene Verständnis über den größten gemeinsamen Teiler wen-
den wir nun an, um eine nützliche Charakterisierung von Primzahlen zu ge-
ben.
1.1 Rechnen mit ganzen Zahlen 11
Beweis. (a) Da ggT(a, b) = 1, gibt es nach Satz 1.1.6 ganze Zahlen r, s mit
ra+ sb = 1. Also ist c = c·(ra+ sb) = a·rc+ bc·s. Da wir a | bc vorausgesetzt
haben, folgt daraus a | c.
(b) Der Beweis der behaupteten Äquivalenz zweier Eigenschaften zerfällt er-
neut in zwei Teile:
Teil I. Zunächst nehmen wir an, dass die Zahl p die Bedingung erfüllt, dass
aus p | ab stets p | a oder p | b folgt. Es ist zu zeigen, dass p eine Primzahl
im Sinne unserer Definition auf Seite 5 ist. Dazu nehmen wir an, dass p
als Produkt p = ab geschrieben werden kann. Dann gilt p | ab, also nach
Voraussetzung p | a oder p | b. Wir können annehmen b = rp. Der Fall p | a
erledigt sich in gleicher Weise. Wir erhalten p = ab = arp, woraus, wegen
p 6= 0, ar = 1 folgt. Daher muss a = r = 1 oder a = r = −1 gelten. Also ist
p eine Primzahl.
Teil II. Sei nun p eine Primzahl. Wir haben zu zeigen, dass aus p | ab stets p | a
oder p | b folgt. Seien dazu a, b ganze Zahlen, für die p | ab gilt. Wir nehmen
an p ist kein Teiler von a, sonst wären wir ja fertig. Da p eine Primzahl ist,
hat p nur die beiden positiven Teiler 1 und p. So kann ggT(p, a) nur 1 oder
p sein. Da aber p kein Teiler von a ist, muss ggT(p, a) = 1 sein. Wir können
nun Teil (a) des Satzes 1.1.7 anwenden und erhalten p | b. ⊓
⊔
Unter Benutzung dieser Charakterisierung von Primzahlen können wir jetzt
den folgenden Satz beweisen. Er bringt zum Ausdruck, dass die Primzahlen
die Grundbausteine der ganzen Zahlen bezüglich ihrer multiplikativen Struk-
tur sind.
Beweis. Wenn n < 0 ist, wählen wir u = −1, sonst sei u = 1. Es genügt,
den Fall n > 0 zu untersuchen, der Rest lässt sich durch Multiplikation mit
(−1) darauf zurückführen. Zu beweisen ist für jede ganze Zahl n ≥ 2 die
Existenz und Eindeutigkeit einer Darstellung n = p1 · . . . · pk mit Primzahlen
1 < p1 ≤ · · · ≤ pk . Die Beweise werden wieder induktiv geführt.
Existenzbeweis: (Vollständige Induktion über n.)
Induktionsanfang: n = 2. Da p1 = 2 eine Primzahl ist, sind wir fertig.
12 1 Zahlen
Zum Abschluss dieses Abschnittes beweisen wir einen sehr wichtigen Satz,
der bereits vor über 2000 Jahren im antiken Griechenland bekannt war – der
Beweis ist bereits bei Euklid2 zu finden.
Beweis. Der Beweis wird indirekt geführt, das bedeutet, wir nehmen an, dass
das (streng mathematische) Gegenteil der Behauptung wahr wäre. Daraus
versuchen wir durch logische Schlüsse einen Widerspruch herzuleiten. Wenn
uns das gelingt, muss unsere Annahme (nämlich, dass die Behauptung des
Satzes nicht gelten würde) falsch sein. Die Behauptung des Satzes ist dann
2 Vgl. Fußnote auf Seite 6.
1.1 Rechnen mit ganzen Zahlen 13
bewiesen. Dies ist ein zweites wichtiges Beweisprinzip, welches wir häufig
benutzen werden. Die Theorie dazu befindet sich im Kapitel 6: Satz 6.1.1
und nachfolgende Erläuterungen.
Nun zum Beweis: Wir nehmen an, es gäbe nur endlich viele Primzahlen. Qn Dies
seien die Zahlen p1 , p2 , . . . , pn . Nun untersuchen wir die Zahl a := 1+ i=1 pi .
Da wir (nach Satz 1.1.8) diese Zahl in Primfaktoren zerlegen können und a >
1 ist (da uns ja p1 = 2 schon als Primzahl bekannt ist), gibt es eine Primzahl
p > 1, welche a teilt. Diese muss, wegen unserer Annahme der Endlichkeit, Qn
unter den Zahlen p1 , . . . , pQ n vorkommen. Daher teilt p das Produkt i=1 pi
n
und somit auch 1 = a − i=1 pi . Dies ist aber für eine Zahl p > 1 nicht
möglich. Damit haben wir den gewünschten Widerspruch erhalten und der
Beweis ist vollständig. ⊓
⊔
Definition 1.1.10. Für jede positive ganze Zahl n bezeichnet ϕ(n) die An-
zahl der zu n teilerfremden Zahlen k, für die 1 ≤ k < n gilt. Diese Funktion
ϕ heißt Eulerfunktion 3 oder Eulersche ϕ-Funktion.
In Kurzschreibweise: ϕ(n) = |{k | 1 ≤ k < n, ggT(k, n) = 1}|. Hier und
im Folgenden wird durch |A| die Kardinalität, also die Anzahl der Elemente,
einer Menge A bezeichnet, vgl. Beispiel 6.3.15.
Satz 1.1.11 Sei p eine Primzahl und seien k, m, n positive ganze Zahlen.
Dann gilt:
(1) ϕ(p) = p − 1;
(2) ϕ(pk ) = pk−1 (p − 1) = pk − pk−1 ;
(3) Wenn ggT(m, n) = 1, dann ist ϕ(mn) = ϕ(m)ϕ(n).
Beweis. Die Aussage (1) ist klar, da unter den Zahlen 1, 2, . . . , p − 1 keine
durch p teilbar ist.
Es ist genau dann ggT(a, pk ) 6= 1, wenn p | a gilt. Unter den Zah-
len 1, 2, . . . , pk sind genau die folgenden pk−1 Vielfachen von p enthalten:
1 · p, 2 · p, . . . , pk−1 · p. Also bleiben pk − pk−1 Zahlen, die zu pk teilerfremd
sind.
Den Beweis von (3) können wir leicht führen, wenn wir einige Grundbegriffe
der Gruppentheorie kennengelernt haben (siehe Satz 1.3.34). Daher verzich-
ten wir an dieser Stelle auf einen Beweis. Dem Leser wird jedoch empfohlen,
einen Beweis mit elementaren Mittels selbst auszuarbeiten. ⊓
⊔
3 Leonard Euler (1707–1783), Schweizer Mathematiker.
14 1 Zahlen
Auf der Grundlage von Satz 1.1.11 ist es sehr leicht, für jede ganze Zahl,
deren Primfaktorzerlegung uns bekannt ist, den Wert der Eulerfunktion zu
bestimmen. Die Faktorisierung einer Zahl in Primfaktoren ist jedoch ein re-
chenaufwändiges Problem und somit auch die Berechnung von ϕ. Man könnte
zwar mit dem Euklidischen Algorithmus für jede Zahl k zwischen 1 und n
testen, ob sie zu n teilerfremd ist oder nicht, aber auch dies ist ziemlich re-
chenaufwändig. Diese Schwierigkeit ist die Grundlage des RSA-Verfahrens,
das im Abschnitt 1.5 behandelt wird.
Aufgaben
Übung 1.1. Berechnen Sie mit Hilfe des Euklidischen Algorithmus für jedes
der folgenden Zahlenpaare (a, b) den größten gemeinsamen Teiler d und finden
Sie ganze Zahlen r, s, so dass d = ra + sb gilt.
Übung 1.2. Beweisen Sie, dass Definition 1.1.1 für d > 0 äquivalent ist zu
(i) d | a und d | b;
(ii’) Für c ∈ Z gilt: Wenn c | a und c | b, dann gilt auch c ≤ d.
Übung 1.3. Benutzen Sie vollständige Induktion zum Beweis der folgenden
Formel: 2
Xn
3 n(n + 1)
k = .
2
k=1
Übung 1.4. Versuchen Sie mittels vollständiger Induktion die folgenden bei-
den Formeln für jede ganze Zahl n ≥ 0 zu beweisen. Dabei ist q 6= 1 eine
reelle Zahl und wir setzen stets q 0 = 1 (auch für q = 0).
n
X n
X
q n+1 − q 2 + q − 1 q n+1 − q 2 + q − 1
qk = + q, qk =
q−1 q−1
k=0 k=0
Übung
1.5. Wir definieren hier für ganze Zahlen n ≥ 0 und k die Symbole
n
k durch folgende rekursive Vorschrift (Pascalsches4 Dreieck, siehe S. 283):
• 00 = 1,
• wenn k < 0 oder k > n, dann ist nk = 0 und
• wenn 0 ≤ k ≤ n, dann ist nk = n−1 k−1 +
n−1
k .
Übung 1.6. Zeigen Sie mittels vollständiger Induktion und unter Benutzung
der Definition in Aufgabe 1.5 für 0 ≤ k ≤ n die folgende explizite Formel:
n n!
= ,
k k! · (n − k)!
Übung 1.9. (a) Beweisen Sie (ohne die allgemeinere Eigenschaft (3) aus Satz
1.1.11 zu benutzen), dass für Primzahlen p 6= q stets gilt:
ϕ(pq) = ϕ(p)ϕ(q) = (p − 1)(q − 1).
(b) Berechnen Sie: ϕ(101), ϕ(141), ϕ(142), ϕ(143), ϕ(169), ϕ(1024).
(c) Für welche Zahlen n gilt n = 2 · ϕ(n)?
Übung 1.10. Gilt für jede ungerade Zahl n, dass das um eins verminder-
te Quadrat dieser Zahl, also n2 − 1, durch 8 teilbar ist? Beweisen Sie Ihre
Antwort.
4 Blaise Pascal (1623–1662), französischer Mathematiker.
16 1 Zahlen
1.2 Restklassen
Abstraktion ist eine wichtige Methode zur Beschreibung und Analyse kom-
plexer Situationen. Das betrifft sowohl mathematische Sachverhalte als auch
Gegenstände und Vorgänge der realen Welt. Bei einer Abstraktion ignoriert
man einige als unwesentlich betrachtete Merkmale und konzentriert sich da-
durch auf eine geringere Zahl einfacher strukturierter Aspekte. Dabei können
jedoch bestimmte Vorgänge oder Gegenstände ununterscheidbar werden, ob-
wohl sie in Wirklichkeit verschieden sind. Wenn wir zum Beispiel von Bäumen
sprechen und es uns dabei vor allem darauf ankommt, diese von Blumen,
Steinen, Tieren und Wolken zu unterscheiden, dann haben wir bereits ab-
strahiert. Wir unterscheiden in diesem Moment nicht zwischen Ahorn, Birke,
Buche, Eiche, Kiefer, Lärche und Weide oder gar konkreten Exemplaren sol-
cher Gewächse.
Um Abstraktionen mit mathematischer Präzision durchführen zu können,
wird die Sprache der Mengen, Relationen und Abbildungen benutzt. Eine
Einführung in diese mathematischen Grundbegriffe befindet sich im Kapi-
tel 6, in den Abschnitten 6.2 und 6.3. Die Zusammenfassung verschiedener
Objekte deren wesentliche Merkmale übereinstimmen, wird in der Mathe-
matik durch die Bildung von Äquivalenzklassen realisiert. Wir werden diese
Methode in diesem Abschnitt am Beispiel der Restklassen ganzer Zahlen il-
lustrieren.
Der Nutzen dieser Begriffsbildungen zeigt sich dann in den Anwendungen:
Wir beweisen einige Teilbarkeitsregeln und beschäftigen uns mit Prüfziffern
als Mittel zur Erkennung von Datenübertragungsfehlern.
Bevor wir die allgemeine Definition geben, betrachten wir ein Beispiel. Hierzu
stellen wir uns vor, dass wir uns nur dafür interessieren, ob das Ergebnis einer
Rechenoperation gerade oder ungerade ist. Wir benutzen dazu die folgende
Schreibweise für ganze Zahlen a:
Für a = 17 601 000 und b = 317 206 375 gilt a ≡ 0 mod 2 und b ≡ 1
mod 2. Diese Schreibweise drückt aus, dass a den Rest 0 und b den Rest 1
bei Division durch 2 lässt.
Um zu entscheiden, welche Reste a + b und a · b bei Division durch 2 las-
sen, muss man die Summe oder das Produkt nicht wirklich ausrechnen. Wir
erhalten leicht a + b ≡ 1 mod 2 und a · b ≡ 0 mod 2. Wir bekommen
dieses Resultat, indem wir die gewünschte Rechenoperation mit den Resten
0, 1 durchführen:
Das ist wesentlich schneller als die Rechnung mit den großen Zahlen a, b. Wir
erhalten das gleiche Resultat, wenn wir a durch eine beliebige andere gerade
Zahl und b durch eine beliebige ungerade Zahl ersetzen. Wir können also mit
den Resten, oder besser den Restklassen rechnen. Um dies zu formalisieren,
bezeichnen wir mit [0] die Menge aller geraden Zahlen und mit [1] die Menge
aller ungeraden Zahlen. Diese Mengen nennt man Restklassen.
Es gilt a ∈ [0], b ∈ [1] und unsere Rechnung hat jetzt die folgende einfache
Form: a + b ∈ [0 + 1] = [1] und a · b ∈ [0 · 1] = [0]. Das führt uns dazu, Summe
und Produkt der Restklassen [0], [1] folgendermaßen zu definieren:
[0] + [0] = [0], [0] + [1] = [1] + [0] = [1], [1] + [1] = [0],
[0] · [0] = [0] · [1] = [1] · [0] = [0], [1] · [1] = [1] .
Es ist leicht nachzuprüfen, dass diese Addition und Multiplikation der Rest-
klassen [0], [1] die Grundgesetze (1.1)–(1.8) des Rechnens mit ganzen Zahlen
erfüllen. Für das Rechnen mit Resten gelten dieselben Regeln wie beim Rech-
nen mit ganzen Zahlen.
Um dieses Beispiel zu verallgemeinern, benutzen wir den Begriff der Äquiva-
lenzrelation (Definition 6.3.12). Im obigen Beispiel liegen zwei ganze Zahlen
in derselben Restklasse, wenn sie entweder beide gerade oder beide ungerade
sind. Da zwei Zahlen genau dann dieselbe Parität haben, wenn ihre Differenz
gerade ist, ist die zugehörige Äquivalenzrelation ∼ durch a ∼ b ⇐⇒ 2 | a − b
gegeben. Üblicherweise schreibt man in dieser Situation a ≡ b mod 2 statt
a ∼ b, also
a ≡ b mod 2 ⇐⇒ 2|a−b.
Wenn wir die Zahl 2 durch eine beliebige ganze Zahl n ≥ 0 ersetzen, erhalten
wir die folgende Definition.
Definition 1.2.1. a ≡ b mod n ⇐⇒ n | a − b.
Dadurch ist auf der Menge Z aller ganzen Zahlen eine Äquivalenzrelation
definiert. Wenn a ≡ b mod n, dann sagen wir: a ist kongruent b modulo n.
Unter Benutzung der Division mit Rest erhalten wir a = ra + ka · n und
b = rb + kb · n, wobei ka , kb ∈ Z und 0 ≤ ra < n, 0 ≤ rb < n. Dann ist
a − b = (ra − rb ) + (ka − kb ) · n und es ergibt sich
a ≡ b mod n ⇐⇒ ra = rb .
Daher ist a genau dann kongruent b modulo n, wenn a und b den gleichen Rest
bei Division durch n lassen. Die Äquivalenzklassen dieser Äquivalenzrelation
nennen wir Restklassen modulo n. Die Restklasse modulo n, in der a ∈ Z
enthalten ist, wird mit [a]n , oder wenn keine Verwechslungen möglich sind
mit [a], bezeichnet. Für festes n ≥ 0 liegt nach Satz 6.3.16 jede ganze Zahl in
genau einer Restklasse modulo n. Jedes Element b ∈ [a] heißt Repräsentant
der Restklasse [a]. Wenn b ein Repräsentant von [a] ist, dann gilt [a] = [b]. Die
18 1 Zahlen
Menge aller Restklassen modulo n bezeichnen wir mit Z/nZ, vgl. Definition
6.3.13.
Bemerkung 1.2.2. Wenn n > 0 ist, dann gibt es genau n verschiedene Rest-
klassen modulo n, dies sind [0], [1], . . . , [n − 1], d.h.
Z/nZ = [0], [1], . . . , [n − 1] .
Wie im Fall n = 2 möchten wir ganz allgemein mit den Restklassen modulo
n rechnen.
Definition 1.2.3. Auf der Menge Z/nZ definieren wir eine Addition und
eine Multiplikation durch [a] + [b] := [a + b] und [a] · [b] := [a · b].
Dies besagt, dass wir Restklassen addieren oder multiplizieren, indem wir
diese Operationen mit Repräsentanten dieser Restklassen durchführen. Um
zu klären, ob eine solche Definition sinnvoll ist, müssen wir beweisen, dass
wir stets dasselbe Resultat erhalten, ganz gleich welche Repräsentanten wir
gewählt haben. Es ist daher zu zeigen, dass aus [a] = [a′ ] und [b] = [b′ ] stets
[a] + [b] = [a′ ] + [b′ ] und [a] · [b] = [a′ ] · [b′ ] folgt. Da, wie leicht einzusehen
ist, die Addition und die Multiplikation von Restklassen kommutativ sind,
ergibt sich dies aus zweimaliger Anwendung der Implikation
[a] = [a′ ] =⇒ [a] + [b] = [a′ ] + [b] und [a] · [b] = [a′ ] · [b].
Um dies zu beweisen, bemerken wir zuerst, dass [a] = [a′ ] genau dann gilt,
wenn a ≡ a′ mod n, das heißt a′ = a + kn für ein k ∈ Z. Daraus erhalten
wir a′ + b = a + kn + b und somit
Für die Zukunft halten wir fest: Wenn wir mathematische Operationen oder
Abbildungen auf Mengen von Äquivalenzklassen definieren, dann müssen
wir immer sicherstellen, dass die Definition nicht von der Wahl der Re-
präsentanten abhängt. Man spricht dann von Wohldefiniertheit der Operation
oder Abbildung.
1.2 Restklassen 19
Der folgende Satz sagt, dass das Rechnen mit Restklassen genauso funktio-
niert wie mit ganzen Zahlen.
Satz 1.2.4 Die Gesetze (1.1)–(1.8) für das Rechnen in (Z, +, ·) gelten auch
in (Z/nZ, +, ·).
Beweis. Wenn wir [0], [1] als neutrale Elemente für die Addition bzw. Multi-
plikation verwenden und −[a] := [−a] setzen, dann ergeben sich diese Gesetze
unmittelbar aus denen, die wir für Z formuliert hatten, indem wir dort a, b, c
durch [a], [b], [c] ersetzen. ⊓
⊔
Bevor wir weitere, etwas verstecktere Beispiele des Rechnens in Z/nZ aus
dem Alltagsleben kennenlernen, befassen wir uns mit der Division in Z/nZ.
Dabei werden wir Erkenntnisse aus Abschnitt 1.1 aus einem neuen Blickwin-
kel betrachten und die mathematischen Grundlagen für die angekündigten
Anwendungen bereitstellen.
Bei der Division in Z/nZ geht es darum, für gegebene a, b ∈ Z die Gleichung
a · x ≡ b mod n zu lösen. Es ist sinnvoll, zunächst die einfachere Gleichung
ggT(a, n) = 1 ⇐⇒ ∃ r ∈ Z : r · a ≡ 1 mod n
⇐⇒ ∃ [r] ∈ Z/nZ : [r] · [a] = [1] .
Der Euklidische Algorithmus liefert also eine Methode, mit der wir Gleichun-
gen der Form (1.11) lösen können. Die Eindeutigkeit einer solchen Lösung
wird im folgenden Satz geklärt.
Satz 1.2.6 Wenn a, n teilerfremde ganze Zahlen sind, dann gibt es genau
eine Restklasse [r] ∈ Z/nZ mit [r] · [a] = [1], d.h. r · a ≡ 1 mod n.
5 Der Existenzquantor ∃ und der Allquantor ∀ sind in Abschnitt 6.1 ab S. 360 erklärt.
20 1 Zahlen
Beweis. Die Existenz haben wir bereits gezeigt (Satz 1.1.6). Angenommen,
für r, r′ ∈ Z gilt r · a ≡ 1 mod n und r′ · a ≡ 1 mod n. Dann folgt ra ≡ r′ a
mod n und somit n | a(r − r′ ). Da nach Voraussetzung ggT(a, n) = 1, liefert
Satz 1.1.7, dass n ein Teiler von r − r′ ist. Damit ist r ≡ r′ mod n also
[r] = [r′ ]. ⊓
⊔
Wenn n eine Primzahl ist, ergibt sich als Spezialfall aus Satz 1.2.6:
Folgerung 1.2.8. Wenn a ∈ Z und n eine Primzahl ist, so dass [a] 6= [0] ∈
Z/nZ, dann gibt es genau ein [r] ∈ Z/nZ, für das [r] · [a] = [1] in Z/nZ gilt.
Falls n eine Primzahl und [a] 6= [0] in Z/nZ ist, genügt das, um jede Gleichung
der Gestalt
ax ≡ b mod n (1.12)
zu lösen. Dazu schreiben wir die Kongruenz (1.12) in der Form [a] · [x] = [b]
und erhalten unter Benutzung von [r] · [a] = [1]
Also ist [x] = [r · b] die gesuchte und einzige Lösung. Die Menge aller ganz-
zahligen Lösungen der Kongruenz (1.12) ist daher [r · b]n = {rb + kn | k ∈ Z}.
Falls n keine Primzahl ist, dann gibt es zu jeder Lösung x ∈ Z der Kongruenz
(1.12) eine ganze Zahl s ∈ Z, so dass ax + sn = b gilt. Aus Satz 1.1.6 erhalten
wir, dass dies genau dann möglich ist, wenn d = ggT(a, n) ein Teiler von b ist.
Das ist die Lösbarkeitsbedingung für die Kongruenz (1.12). Wenn sie erfüllt
ist, dann sind a′ = ad , b′ = db und n′ = nd ganze Zahlen und x ∈ Z ist genau
dann Lösung von (1.12), wenn
a′ x ≡ b ′ mod n′ .
Beispiel 1.2.10 (Teilbarkeit durch 3). Viele kennen die 3-er Regel: Eine
ganze Zahl ist genau dann durch drei teilbar, wenn ihre Quersumme durch
drei teilbar ist. Als Quersumme einer Zahl bezeichnet man die Summe ihrer
Ziffern.
Unter Verwendung von Kongruenzen lässt sich die Richtigkeit dieser Regel
sehr elegant beweisen. Da eine Zahl a genau dann durch 3 teilbar ist, wenn
a ≡ 0 mod 3 gilt, genügt es zu zeigen, dass jede ganze Zahl kongruent ihrer
Quersumme modulo 3 ist. P
Wenn eine Zahl a die Ziffern ak ak−1 . . . a1 a0 hat, dann ist a = ki=0 ai 10i
Pk
und i=0 ai ist die Quersumme dieser Zahl. Da 10 ≡ 1 mod 3 ergibt sich
k
X k
X k
X
a= ai · 10i ≡ ai · 1 i ≡ ai mod 3 .
i=0 i=0 i=0
Damit ist die 3-er Regel bewiesen. Da 10 ≡ 1 mod 9, gilt die gleiche Regel
auch für Teilbarkeit durch 9.
Nach dem gleichen Muster lassen sich weitere, zum Teil weniger bekannte
Teilbarkeitsregeln herleiten und beweisen. Unsere Beweise beruhen stets auf
einer Kongruenz der Gestalt 10r ≡ ±1 mod n. Das funktioniert für solche
n, die Teiler einer Zahl der Gestalt 10r ± 1 sind.
Beispiel 1.2.12 (Teilbarkeit durch 101). Die Zahl 101 ist eine Primzahl
und es gilt 100 ≡ −1 mod 101. Zur Beschreibung einer Teilbarkeitsregel
teilen wir deshalb die Ziffern einer Zahl a in Zweiergruppen. Wir beginnen
dabei am Ende der Zahl. Wenn Ak , Ak−1 , . . . , A1 , A0 diese Zweiergruppen
Pk
sind, dann ist 0 ≤ Ai ≤ 99 und a = i=1 Ai 102i . Damit ergibt sich
k
X
a≡ (−1)i Ai mod 101 .
i=1
Also ist a genau dann durch 101 teilbar, wenn die alternierende Summe der
am Ende beginnend gebildeten 2-er Gruppen durch 101 teilbar ist.
Die 2-er Gruppen unserer Beispielzahl 317 206 375 lauten A4 = 03, A3 =
17, A2 = 20, A1 = 63, A0 = 75. Da 3 − 17 + 20 − 63 + 75 = 18 nicht durch 101
teilbar ist, ist auch 317 206 375 nicht durch 101 teilbar.
Beispiel 1.2.13 (Teilbarkeit durch 7 und 13). Der Ausgangspunkt ist
die Gleichung 1001 = 7 · 11 · 13. Daraus erhalten wir 1000 ≡ −1 mod 7
und 1000 ≡ −1 mod 13. Daher können wir die Teilbarkeit durch 7 und 13
durch Betrachtung der alternierenden Summe der 3-er Gruppen (am Ende
beginnend) testen.
Für die uns bereits vertraute Zahl 317 206 375 erhalten wir als alternierende
Summe der Dreiergruppen 317 − 206 + 375 = 486. Da 486 ≡ −4 mod 7 und
486 ≡ 5 mod 13 gilt, ist weder 13 noch 7 ein Teiler von 317 206 375.
Bei der Übermittlung von Informationen können Fehler oder Datenverlus-
te auftreten. Oft ist es wichtig, dass solche Fehler erkannt oder sogar kor-
rigiert werden. Bei der menschlichen Sprache erlernen wir diese Fähigkeit
frühzeitig, wodurch es uns oft möglich ist, auch mit einer Person zu kommu-
nizieren, die nuschelt oder einen unvertrauten Dialekt spricht. Wenn es sich
bei der übermittelten Information jedoch um eine Zahl handelt, zum Beispiel
eine Kontonummer, Artikelnummer, Kreditkartennummer oder Ähnliches,
dann ist es für ein menschliches Wesen nicht so einfach, Fehler zu erkennen.
Das Anhängen einer sogenannten Prüfziffer ist die einfachste Methode, eine
Fehlererkennung zu ermöglichen. In den folgenden beiden Beispielen werden
zwei weltweit praktizierte Prüfzifferverfahren vorgestellt. In beiden Fällen
wird die Prüfziffer durch eine Rechnung modulo n bestimmt. Im Kapitel 2.5
werden wir uns mit Methoden beschäftigen, die eine Korrektur von Fehlern
ermöglicht.
Beispiel 1.2.14 (EAN – European Article Number). In vielen Su-
permärkten werden an der Kasse die auf den Waren aufgedruckten Strich-
codes gelesen, woraus dann die Rechnung für den Kunden und eine Übersicht
1.2 Restklassen 23
über den Lagerbestand erstellt wird. Der Strichcode spiegelt in einer be-
stimmten Weise die 13-stellige EAN wieder. Davon tragen die ersten 12 Zif-
fern a1 , . . . , a12 die Information, die 13. Ziffer a13 ist eine Prüfziffer. Die
ersten 12 Ziffern sind in drei Gruppen unterteilt. Die erste Zifferngruppe ist
eine Länderkennung, sie umfasst die ersten drei Ziffern. Die Nummern 400–
440 sind Deutschland, 760–769 der Schweiz und Liechtenstein und 900–919
Österreich zugeordnet. Aus den ersten drei Ziffern kann man in der Regel nur
auf den Firmensitz des Herstellers schließen, nicht aber auf das Land in dem
der Artikel tatsächlich hergestellt wurde.
Die zweite Gruppe besteht meist aus vier, manchmal aber auch aus fünf
oder sechs Ziffern. Sie codiert das produzierende Unternehmen, welches die
verbleibenden Ziffern als Artikelnummer frei vergeben kann. Bei der EAN
4 399148 405508
sieht die Einteilung in Zifferngruppen folgendermaßen aus:
4 3 9 9 1 4 8 4 0 5 5 0 8
a a a a a a a a a9 a10 a11 a12 a
| 1 {z2 3} | 4 5{z 6 7} |8 {z } 13
|{z}
Land Hersteller Artikel Prüfziffer
Bereits 1973 wurde in den USA ein 12-stelliger Produktcode eingeführt, der
kurz darauf in Europa zur EAN erweitert wurde. Seit die 13-stellige EAN auch
in Nordamerika verwendet wird, spricht man von der International Article
Number . Die Prüfziffer ergibt sich aus den ersten 12 Ziffern wie folgt:
Wenn genau eine der 13 Ziffern fehlt oder unleserlich ist, dann lässt sie sich
mit Hilfe der Prüfgleichung (1.13) rekonstruieren. Das ist offensichtlich, wenn
die fehlende Ziffer mit Faktor 1 in der Prüfgleichung auftritt. Wenn sie mit
dem Faktor 3 versehen ist, dann nutzen wir die Kongruenz 3 · 7 ≡ 1 mod 10
um sie zu bestimmen.
Zur Unterscheidung dieser beiden Typen spricht man von der ISBN-10 und
der ISBN-13. Jeder ISBN-10 ist in eindeutiger Weise eine ISBN-13 zugeord-
net, nicht aber umgekehrt.
Die ISBN-13 eines Buches ist identisch mit seiner EAN. Die Prüfziffer wird
nach der Vorschrift im Beispiel 1.2.14 bestimmt. Bei der ISBN-10 erfolgt die
Berechnung des Prüfzeichens auf eine mathematisch interessantere Art.
Ähnlich zur Struktur der EAN, sind die 10 Zeichen einer ISBN-10 in vier
Gruppen unterteilt. Die einzelnen Gruppen repräsentieren das Land bzw.
den Sprachraum, den Verlag, eine verlagsinterne Nummer des Buches, sowie
das Prüfzeichen. Details sind durch die Norm DIN ISO 2108 geregelt. Die
erste Zifferngruppe besteht oft nur aus einer, kann aber bis zu fünf Ziffern
umfassen. Der deutsche Sprachraum entspricht der Ziffer 3. In der ISBN
dieses Buches finden Sie die Verlagsnummer 540 des Springer-Verlags vor.
Auch die Verlagsnummern können aus unterschiedlich vielen Ziffern bestehen.
Wenn wir die einzelnen Zeichen einer ISBN-10, von links beginnend, mit
a1 , a2 , . . . , a9 , a10 bezeichnen, dann lautet die Prüfgleichung:
10
X
i · ai ≡ 0 mod 11 . (1.14)
i=1
3 + 2 · 5 + 3 · 2 + 4 · 8 + 5 · 7 + 6 · 7 + 7 · 2 + 8 · 1 + 9 · 7 ≡ 4 mod 11
Damit erhalten wir 8 als neue Prüfziffer und die zu 3-528-77217-4 gehörige
ISBN-13 lautet 9783528772178. Auf Büchern, die vor dem 1. Januar 2007
gedruckt wurden, sind in der Regel beide Nummern vorzufinden:
1.3 Gruppen 25
ISBN 3-528-77217-4
9 783528 772178
Außer 978 ist auch das Präfix 979 im Gebrauch, wodurch sich die Zahl der
prinzipiell möglichen Buchnummern verdoppelt. Die ISBN-13, die gleichzeitig
auch die EAN darstellt, gibt ein Beispiel dafür, dass aus den ersten drei Ziffern
einer EAN nicht das Herkunftsland des Artikels bestimmt werden kann, es
sei denn, man ist der Ansicht, dass alle Bücher aus Buchland“ kommen.
”
Aufgaben
P
2000
Übung 1.11. Zeigen Sie, dass k 13 = 113 + 213 + · · · + 199913 + 200013
k=1
durch 2001 teilbar ist.
Übung 1.12. Vor geraumer Zeit empfahl mir ein guter Freund zwei Bücher.
Aus Bequemlichkeit sandte er mir lediglich die folgenden beiden ISBN-10:
3-423-62015-3 und 3-528-28783-6. Beim Versuch diese Bücher zu kaufen,
musste ich leider feststellen, dass eine der beiden Nummern fehlerhaft war.
Überprüfen Sie unter Benutzung der Prüfgleichung (1.14) die Gültigkeit bei-
der ISBN’s. Geben Sie alle Möglichkeiten an, die fehlerhafte ISBN-10 an
genau einer Stelle so zu verändern, dass die Prüfgleichung erfüllt ist.
Übertragen Sie die so gefundenen korrigierten ISBN-10 in das ISBN-13-
Format und ermitteln Sie (z.B. mit Hilfe einer Internetrecherche) welche da-
von tatsächlich zu einem Buch gehört.
1.3 Gruppen
Zu Beginn des vorigen Abschnittes haben wir die Wichtigkeit der Methode
der Abstraktion hervorgehoben. Als wichtigstes Beispiel eines Abstraktions-
prozesses diente uns dort der Übergang von ganzen Zahlen zu Restklassen.
Wir nehmen nun den scheinbar wenig spektakulären Satz 1.2.4 als Ausgangs-
punkt für unsere weiteren Überlegungen. Er sagt, dass die Grundgesetze des
Rechnens beim Übergang zu Restklassen nicht verloren gehen. In diesem Sin-
ne gehören die Axiome (1.1)–(1.8) zu den wesentlichen Merkmalen, welche
sich bei der Abstraktion herauskristallisiert haben. Auf dem neuen Abstrak-
tionsniveau, auf das wir uns in diesem Abschnitt begeben, sind solche Re-
chengesetze das Einzige, was wir noch als wesentlich betrachten wollen. Die
26 1 Zahlen
(Assoziativgesetz) ∀ a, b, c ∈ G : a ∗ (b ∗ c) = (a ∗ b) ∗ c. (1.15)
(neutrales Element) ∃ e ∈ G ∀ a ∈ G : e ∗ a = a. (1.16)
(inverses Element) ∀ a ∈ G ∃ a′ ∈ G : a′ ∗ a = e. (1.17)
(Kommutativgesetz) ∀ a, b ∈ G : a ∗ b = b ∗ a, (1.18)
Zur Vermeidung von Unklarheiten sprechen wir oft von der Gruppe (G, ∗)“
”
und nicht nur von der Gruppe G“. Das Symbol ∗ dient uns zur allgemeinen
”
Bezeichnung der Verknüpfung in einer Gruppe. In Beispielen ersetzen wir
nicht nur G durch eine konkrete Menge, sondern oft auch den ∗ durch eines
der gebräuchlichen Verknüpfungssymbole wie etwa +, ·, ◦ oder ×.
Wenn + als Verknüpfungsymbol verwendet wird sprechen wir von einer ad-
ditiven Gruppe. Dann schreiben wir 0 statt e und das additive Inverse a′ von
a bezeichnen wir mit −a.
Wenn · als Verknüpfungsymbol verwendet wird, sprechen wir von einer mul-
tiplikativen Gruppe. In diesem Fall wird das neutrale Element durch 1 statt
durch e bezeichnet. Für das multiplikative Inverse hat sich die Bezeichnung
a−1 eingebürgert.
Beispiel 1.3.2. (i) (Z, +), (Q, +), (R, +) und (C, +) sind abelsche Grup-
pen. Hier und im Folgenden bezeichnet Q die Menge der rationalen Zah-
len, R die Menge der reellen Zahlen und C die Menge der komplexen
Zahlen, vgl. Beispiel 1.4.20 und Abschnitt 3.1.
(ii) Aus Satz 1.2.4 ergibt sich, dass (Z/nZ, +) eine abelsche Gruppe ist.
(iii) (Q r {0}, ·) und (R r {0}, ·) sind abelsche Gruppen. Die Zahl 0 mussten
wir wegen (1.17) entfernen, da sie kein multiplikatives Inverses besitzt.
6 Niels Henrik Abel (1802–1829), norwegischer Mathematiker.
1.3 Gruppen 27
(iv) Im Gegensatz dazu ist (Z r {0}, ·) keine Gruppe, denn keine von ±1
verschiedene ganze Zahl hat ein multiplikatives Inverses in Z. Die größte
multiplikative Gruppe, die nur ganze Zahlen enthält, ist daher {1, −1}.
(v) Aus Satz 1.2.6 folgt, dass (Z/nZ)∗ := {[a] ∈ Z/nZ | ggT(a, n) = 1} eine
Gruppe bezüglich Multiplikation ist.
(vi) Auf dem kartesischen Produkt G × H (siehe Abschnitt 6.2) zweier Grup-
pen (G, ∗) und (H, ·) erhalten wir die Struktur einer Gruppe (G × H, ◦)
indem wir (g, h) ◦ (g ′ , h′ ) := (g ∗ g ′ , h · h′ ) definieren. Das ist jedem von
der additiven Gruppe R2 – Vektoren in der Ebene – vertraut.
σ : {1, 2, . . . , n} → {1, 2, . . . , n}
und eine solche lässt sich durch Angabe einer Wertetabelle beschreiben. Dazu
werden einfach die Zahlen 1, 2, . . . , n und deren Bilder unter der Abbildung
σ ∈ Sn in zwei Zeilen übereinander angeordnet
1 2 ... n
.
σ(1) σ(2) . . . σ(n)
Durch die folgende Rechnung erkennen wir, dass S3 nicht abelsch ist:
123 123 123 123 123 123
◦ = 6= = ◦ .
213 321 312 231 321 213
Diesen Zyklus kann man sich etwa wie im folgenden Bild vorstellen:
5 4
Jede durch die Permutation σ nicht veränderte Zahl k, d.h. k = σ(k), wird
nicht aufgeschrieben. Jedes von σ veränderte Element der Menge {1, . . . , n}
muss jedoch betrachtet werden. Im Allgemeinen werden wir daher ein Pro-
dukt mehrerer Zyklen erhalten:
123456
= (1 6) ◦ (2 4 5) .
643521
Der Vorteil der effektiveren Schreibweise wird mit einer Mehrdeutigkeit er-
kauft. So kann zum Beispiel der Zyklus (1 2) jeder der folgenden Wertetabellen
entsprechen:
12 123 1234 12345 123456
, , , , , etc.
21 213 2134 21345 213456
je nachdem in welchem Sn wir gerade arbeiten. Das ist jedoch nicht weiter
dramatisch, da Sn−1 auf natürliche Weise als Untergruppe in Sn enthalten
ist, siehe Beispiel 1.3.14.
Die sechs Elemente der Gruppe S3 haben in Zyklenschreibweise die Gestalt
1.3 Gruppen 29
12 3 12 3 12 3
Id = , (1 2) = , (1 3) = ,
12 3 21 3 32 1
12 3 12 3 12 3
(2 3) = , (1 2 3) = , (1 3 2) = .
13 2 23 1 31 2
Beispiel 1.3.4. Obwohl wir uns dem Gruppenbegriff durch Abstraktion von
den ganzen Zahlen genähert haben, liegt sein historischer Ursprung in der
Geometrie. Viele Menschen sind von Symmetrien in Natur, Kunst und Wis-
senschaft fasziniert. Das mathematische Studium von Symmetrien führt un-
ausweichlich zum Begriff der Symmetriegruppe. Die elementarsten Beispiele
erhält man als Menge aller Symmetrien einer ebenen Figur wie etwa eines
Kreises oder eines Dreiecks. Unter einer Symmetrie wollen wir hier eine Kon-
gruenztransformation einer solchen Figur verstehen, also eine Verschiebung,
Drehung oder Spiegelung, unter der diese Figur auf sich selbst abgebildet
wird.
Die Menge aller Symmetrien eines regelmäßigen ebenen n-Ecks (n ≥ 3)
bezeichnet man mit Dn . Sie heißt Diedergruppe (auch Di-edergruppe oder
Diëdergruppe). Zur Illustration betrachten wir hier den Fall n = 5 (Abb. 1.1).
P0 = P5
b
t
P1 b b P4
b b
P2 P3
Es gibt keine Verschiebung, welche ein Fünfeck in sich selbst überführt. Als
Symmetrien kommen also nur Drehungen und Spiegelungen in Frage. Jede
Drehung mit Zentrum im Mittelpunkt des Fünfecks um einen Winkel der
30 1 Zahlen
Größe k · 2π5 , k ∈ Z, bildet das Fünfeck auf sich selbst ab. Mit t ∈ D5 be-
zeichnen wir die Drehung um 2π 5 entgegen dem Uhrzeigersinn. Die weiteren
Drehungen sind dann t2 , t3 , t4 und t5 = Id.
Jede Kongruenztransformation ist durch ihr Wirken auf der Menge der Eck-
punkte {P0 , P1 , P2 , P3 , P4 } vollständig festgelegt. Daher ist t ∈ D5 durch
t(Pi ) = Pi+1 gegeben, wobei wir die Indizes als Elemente von Z/5Z auffas-
sen, also P5 = P0 setzen. Diese bequeme Vereinbarung nutzen wir auch im
Folgenden.
Als weitere Symmetrien kommen noch die Spiegelungen an den Verbindungs-
geraden des Mittelpunktes mit den Eckpunkten des Fünfecks in Betracht. Sei
zum Beispiel s die Spiegelung an der Achse durch P0 , siehe Abb. 1.1. Dann
gilt s(Pi ) = P5−i und s, st, st2 , st3 , st4 ist eine komplette Liste aller Spiege-
lungen, die das Fünfeck auf sich selbst abbilden. Das ergibt:
Beweis. Wir beginnen mit (d). Sei a′′ ein inverses Element zu a′ , welches
nach (1.17) in Definition 1.3.1 existiert und a′′ ∗ a′ = e erfüllt. Wir erhalten
a ∗ a′ = e ∗ (a ∗ a′ ) = (a′′ ∗ a′ ) ∗ (a ∗ a′ )
(1.16)
= a′′ ∗ (a′ ∗ a) ∗ a′ = a′′ ∗ (e ∗ a′ )
(1.15) (1.17)
Als Nächstes zeigen wir (a). Dazu nehmen wir an, dass ē ein weiteres neutrales
Element ist. Das heißt nach (1.16), dass für jedes a ∈ G die Gleichung ē∗a = a
erfüllt ist, insbesondere e = ē ∗ e. Wenn wir in (b) a = ē einsetzen, erhalten
wir ē ∗ e = ē und somit die gewünschte Eindeutigkeit e = ē.
Nun können wir (c) beweisen. Wenn ā′ ein weiteres Inverses zu a ist, dann gilt
ā′ ∗a = e. Es ergibt sich ā′ = ā′ ∗e = ā′ ∗(a∗a′ ) = (ā′ ∗a)∗a′ = e∗a′ = a′ .
(b) (d) (1.15) (1.16)
Schließlich folgt (e) durch Multiplikation mit a′ von links (bzw. rechts). ⊓
⊔
Bemerkung 1.3.6. Die Aussage (d) in Satz 1.3.5 besagt nicht, dass die
Gruppe G abelsch ist. Sie besagt nur, dass ein von links zu multiplizierendes
Inverses mit dem von rechts zu multiplizierenden Inversen übereinstimmt.
Bemerkung 1.3.7. Aus Satz 1.3.5 (c) folgt (a−1 )−1 = a und (a ∗ b)−1 =
b−1 ∗ a−1 in jeder multiplikativ geschriebenen Gruppe.
Definition 1.3.8. (1) Eine nichtleere Teilmenge U ⊂ G einer Gruppe (G, ∗)
heißt Untergruppe von G, wenn für alle a, b ∈ U stets a ∗ b ∈ U und
a−1 ∈ U gilt.
(2) Eine Abbildung f : G → H zwischen zwei Gruppen (G, ∗) und (H, ◦)
heißt Gruppenhomomorphismus, wenn für alle a, b ∈ G stets f (a ∗ b) =
f (a) ◦ f (b) gilt.
(3) Ein bijektiver8 Gruppenhomomorphismus heißt Isomorphismus. Wenn es
hervorzuheben gilt, dass f : G → H ein Isomorphismus ist, dann schrei-
∼
ben wir f : G −−→ H.
Bemerkung 1.3.9. Wenn U ⊂ G eine Untergruppe ist, dann ist (U, ∗) eine
Gruppe, wobei ∗ die Einschränkung der Verknüpfung ∗ von G auf U ist.
Bemerkung 1.3.10. Da jede Untergruppe U ⊂ G nichtleer ist, gibt es min-
destens ein Element a ∈ U . Die Definition besagt, dass damit auch a−1 ∈ U
und e = a−1 ∗ a ∈ U sein muss. Daher ist das neutrale Element e ∈ G in je-
der Untergruppe enthalten. Man kann also in Definition 1.3.8 die Bedingung
U 6= ∅ durch die gleichwertige Forderung e ∈ U ersetzen.
Bemerkung 1.3.11. Wenn f : (G, ∗) → (H, ◦) ein Gruppenhomomorphis-
mus ist und eG ∈ G, eH ∈ H die neutralen Elemente bezeichnen, dann gilt
f (eG ) = eH , denn eH ◦ f (eG ) = f (eG ) = f (eG ∗ eG ) = f (eG ) ◦ f (eG ), woraus
wegen Satz 1.3.5 (e) eH = f (eG ) folgt.
Ferner gilt f (a−1 ) = f (a)−1 für alle a ∈ G, was wegen der Eindeutigkeit des
Inversen, Satz 1.3.5 (c), aus eH = f (eG ) = f (a−1 ∗ a) = f (a−1 ) ◦ f (a) folgt.
Bemerkung 1.3.12. Wenn f : G → H ein Isomorphismus ist, dann ist auch
f −1 : H → G ein Isomorphismus.
Beispiel 1.3.13. 2Z := {2n | n ∈ Z} ⊂ Z ist Untergruppe von (Z, +). Die
ungeraden Zahlen {2n + 1 | n ∈ Z} ⊂ Z bilden keine Untergruppe, zum
Beispiel weil 0 nicht darin enthalten ist.
8 Siehe Definition 6.3.3.
32 1 Zahlen
Wenn wir f auf Zyklen anwenden, sehen wir keine Veränderung in der
Schreibweise, es ändert sich nur die Interpretation. Das Bild der Abbildung f
ist die Untergruppe f (Sn ) = Un := {σ ′ ∈ Sn+1 | σ ′ (n + 1) = n + 1} ⊂ Sn+1
∼
und f definiert einen Isomorphismus f : Sn −−→ Un . Daher können wir Sn
als Untergruppe von Sn+1 auffassen. Dadurch ist die scheinbar ungenaue Zy-
klenschreibweise mathematisch gerechtfertigt, bei der z.B. (1 2) als Element
in jedem Sn aufgefasst werden kann.
hgi := {g k | k ∈ Z} = {. . . , g −3 , g −2 , g −1 , eG , g, g 2 , g 3 , . . .}
(Division mit Rest). Da die Untergruppe U sowohl a als auch n enthält, ist
auch r = a − sn ∈ U . Da n das kleinste Element von U + und r < n ist, folgt
r 6∈ U + . Daher ist r = 0 und somit a = s · n. Daraus ergibt sich U = nZ. ⊓
⊔
Beispiel 1.3.19. Die Abbildung f : Z → Z mit f (k) := n · k (fixiertes n) ist
ein Gruppenhomomorphismus, denn f (k + l) = n · (k + l) = n · k + n · l =
f (k) + f (l).
Die durch f (k) := k 2 definierte Abbildung ist hingegen kein Gruppenho-
momorphismus Z → Z der additiven Gruppen, denn f (2) = 4 6= 1 + 1 =
f (1) + f (1).
Wenn (G, ∗) eine Gruppe ist und a ∈ G, (a 6= e), dann ist durch f (g) := a ∗ g
kein Gruppenhomomorphismus f : G → G definiert, da f (e) = a ∗ e = a 6= e.
Wenn U ⊂ G eine Untergruppe einer Gruppe (G, ∗) ist, dann liefert uns
die folgende Definition eine Äquivalenzrelation (siehe Abschnitt 6.3) auf der
Menge G:
a ∼ b ⇐⇒ a−1 ∗ b ∈ U . (1.19)
Reflexivität: Da U ⊂ G eine Untergruppe ist, gilt a−1 ∗ a = e ∈ U für alle
a ∈ G. Daher folgt a ∼ a.
Symmetrie: Wenn a ∼ b, dann gilt a−1 ∗ b ∈ U und somit (a−1 ∗ b)−1 ∈ U .
Unter Verwendung von Bemerkung 1.3.7 folgt daraus (a−1 ∗ b)−1 = b−1 ∗
(a−1 )−1 = b−1 ∗ a ∈ U , also b ∼ a.
Transitivität: Wenn a ∼ b und b ∼ c, dann gilt a−1 ∗ b ∈ U und b−1 ∗ c ∈ U .
Also ist a−1 ∗ c = (a−1 ∗ b) ∗ (b−1 ∗ c) ∈ U und damit a ∼ c.
Aus der Definition folgt unmittelbar, dass die Äquivalenzklassen die Beschrei-
bung [a] = a ∗ U := {a ∗ b | b ∈ U } besitzen. Die Abbildung U → a ∗ U , die b
auf a ∗ b abbildet, ist bijektiv, ihr Inverses bildet c auf a−1 ∗ c ab.
Die Mengen a ∗ U nennt man Linksnebenklassen. Für die Äquivalenz-
klassenmenge G/ ∼ schreiben wir G/U und nennen sie die Menge der Links-
nebenklassen. Den Spezialfall U = nZ ⊂ G = Z haben wir ausführlich im
Abschnitt 1.2 studiert.
|G| = |U | · |G/U | .
Definition 1.3.21. (1) Die Anzahl der Elemente ord(G) := |G| einer Gruppe
G heißt Ordnung der Gruppe G.
(2) Für jedes Element g ∈ G einer Gruppe G heißt ord(g) := ord(hgi) Ord-
nung des Elements g.
Obwohl diese Definition auch für Gruppen mit unendlich vielen Elementen
gültig ist, werden wir uns hier vorrangig mit Ordnungen in endlichen Grup-
pen befassen. Die Ordnung eines Elements einer endlichen Gruppe ist stets
eine positive ganze Zahl. Die Definition der Ordnung eines Elements g ∈ G
übersetzt sich in
Beweis. Die Aussage (1) ergibt sich unmittelbar aus dem Satz 1.3.20 unter
Benutzung des neu eingeführten Begriffes der Ordnung. Aussage (2) ergibt
sich aus (1), denn ord(g) = ord(hgi).
Da es nach (2) eine ganze Zahl k gibt, für die ord(G) = k · ord(g) gilt, ergibt
k
sich g ord(G) = g k·ord(g) = g ord(g) = ek = e. ⊓
⊔
Zur Anwendung dieses Satzes auf die multiplikative Gruppe (Z/nZ)∗ erinnern
wir uns an die Eulerfunktion (Definition 1.1.10):
ϕ(n) = k ∈ Z1 ≤ k < n, ggT(k, n) = 1 = ord ((Z/nZ)∗ ) .
Satz 1.3.24 (kleiner Satz von Fermat10 ) (1) Für jede Primzahl p und
jede ganze Zahl a, die nicht durch p teilbar ist, gilt: ap−1 ≡ 1 mod p.
(2) Wenn a, n teilerfremde ganze Zahlen sind, dann gilt aϕ(n) ≡ 1 mod n.
Beweis. Da ϕ(p) = p− 1 für jede Primzahl p und ϕ(n) = ord ((Z/nZ)∗ ), folgt
die Behauptung aus Satz 1.3.23 (3). ⊓
⊔
Beispiel 1.3.25. (i) Wenn ggT(a, 10) = 1, dann ist a4 ≡ 1 mod 10, da
ϕ(10) = ϕ(5) · ϕ(2) = 4. Mit anderen Worten: die vierte Potenz jeder
ungeraden Zahl, die nicht auf 5 endet, hat als letzte Ziffer eine 1. Aus
dieser Kongruenz ergibt sich auch, dass für jede ganze Zahl a, die zu
10 teilerfremd ist, die letzte Ziffer einer beliebigen Potenz am gleich der
letzten Ziffer von ar ist, sobald r ≡ m mod 4. Dies ergibt sich aus m =
4k + r und am ≡ a4k+r ≡ (a4 )k · ar ≡ 1k · ar ≡ ar mod 10.
(ii) Ebenso lässt sich der Rechenaufwand für die Bestimmung von zwei oder
mehr Endziffern großer Zahlen verringern. Bei der Berechnung der letzten
zwei Ziffern kann man wegen ϕ(100) = ϕ(52 · 22 ) = 5 · 4 · 2 = 40 die
Exponenten modulo 40 reduzieren. Da 99 ≡ 9 mod 40, folgt zum Beispiel
9
9(9 ) ≡ 99 mod 100. Ohne technische Hilfsmittel berechnet man leicht
9
99 ≡ 89 mod 100. Die letzten beiden Ziffern von 9(9 ) lauten also 89.
Als Nächstes werden wir den Prozess der Vererbung der Addition von Z auf
Z/nZ (Definition 1.2.3) für Gruppen verallgemeinern.
Satz 1.3.26 Sei (G, ∗) eine abelsche Gruppe und U ⊂ G eine Untergruppe.
Dann ist auf der Menge der Linksnebenklassen G/U durch [a] ∗ [b] := [a ∗ b]
die Struktur einer abelschen Gruppe definiert.
Beweis. Das Hauptproblem ist hier, ebenso wie bei Satz 1.2.4, die Wohl-
definiertheit. Dazu ist zu zeigen, dass aus [a] = [a′ ] und [b] = [b′ ] stets
[a′ ∗ b′ ] = [a ∗ b] folgt. Entsprechend der in (1.19) gegebenen Definition bedeu-
ten [a] = [a′ ] und [b] = [b′ ], dass es r, s ∈ U gibt, so dass a′ = a∗r und b′ = b∗s
gilt. Damit ergibt sich a′ ∗ b′ = (a ∗ r) ∗ (b ∗ s) = a ∗ (r ∗ b ∗ s) = a ∗ (b ∗ r ∗ s).
Für die letzte Gleichung haben wir benutzt, dass G abelsch ist. Da U eine
Untergruppe ist, gilt r ∗ s ∈ U und es folgt a′ ∗ b′ = (a ∗ b) ∗ (r ∗ s) ∈ (a ∗ b) ∗ U ,
also tatsächlich [a′ ∗ b′ ] = [a ∗ b]. Die Gruppeneigenschaften übertragen sich
nun unmittelbar von G auf G/U . ⊓
⊔
Da die Gruppen Sn und Dn nicht abelsch sind, entsteht die Frage, ob für
solche Gruppen die Vererbung der Gruppenstruktur auf Linksnebenklassen-
mengen ebenfalls möglich ist. Als Beispiel betrachten wir die Untergruppe
{1, s} ⊂ D5 . Sie besitzt die folgenden 5 = ord(D5 )/2 Nebenklassen
[1] = {1, s}, [t] = {t, ts}, [t2 ] = {t2 , t2 s}, [t3 ] = {t3 , t3 s}, [t4 ] = {t4 , t4 s} .
Gruppenstruktur vererbt sich daher nicht auf D5 /{1, s}. Beim Umgang mit
nicht-abelschen Gruppen ist also Vorsicht geboten.
Bei genauerer Betrachtung des Beweises von Satz 1.3.26 sehen wir, dass nur
an einer Stelle benutzt wurde, dass G abelsch ist, nämlich beim Beweis von
a ∗ (r ∗ b ∗ s) ∈ (a ∗ b) ∗ U . Diesen Beweisschritt kann man jedoch auch
ausführen, wenn es ein Element r′ ∈ U gibt, so dass r ∗ b = b ∗ r′ , denn dann
folgt a ∗ (r ∗ b ∗ s) = a ∗ (b ∗ r′ ∗ s) ∈ (a ∗ b) ∗ U .
Eine Untergruppe U ⊂ G, welche die Eigenschaft hat, dass für jedes b ∈ G
und jedes r ∈ U ein r′ ∈ U mit r ∗ b = b ∗ r′ existiert, nennt man einen
Normalteiler. Mit anderen Worten: Eine Untergruppe U ⊂ G ist genau dann
Normalteiler, wenn b ∗ U = U ∗ b für alle b ∈ G. Mit dem gleichen Beweis wie
von Satz 1.3.26 erhalten wir nun, dass sich die Gruppenstruktur von G auf
G/U vererbt, sobald U ⊂ G ein Normalteiler ist.
Wenn G abelsch ist, dann ist jede Untergruppe U ⊂ G ein Normalteiler, da
stets r ∗ b = b ∗ r. In nicht-abelschen Gruppen gibt es im Allgemeinen jedoch
Untergruppen, die nicht Normalteiler sind. Zum Beispiel ist {1, s} ⊂ D5 kein
Normalteiler, da ts 6∈ {t, st} in D5 .
f¯ : G/ ker(f ) −→ im(f ) .
Beweis. Nach Bemerkung 1.3.31 ist ker(f ) ⊂ G stets Normalteiler, also wird
die Gruppenstruktur von G auf G/ ker(f ) vererbt. Die Wohldefiniertheit von
f¯ sehen wir wie folgt: Sei [a] = [a′ ] ∈ G/ ker(f ), dann gibt es ein b ∈ ker(f ) ⊂
G mit a′ = a ∗ b. Damit erhalten wir f (a′ ) = f (a ∗ b) = f (a) ∗ f (b) =
f (a)∗ eH = f (a), wie gewünscht. Aus der Definition von f¯ folgt sofort, dass f¯
ein surjektiver Gruppenhomomorphismus ist. Für den Beweis der Injektivität
betrachten wir [a] ∈ ker(f¯) ⊂ G/ ker(f ). Dann ist f (a) = f¯([a]) = eH , d.h.
a ∈ ker(f ) und somit [a] = eG/ ker(f ) . Wegen Satz 1.3.30 (3) ist f¯ injektiv
und daher ein Isomorphismus. ⊓
⊔
Als erste Anwendung erhalten wir den folgenden Satz.
Satz 1.3.33 Sei G eine Gruppe und g ∈ G ein Element der Ordnung n.
Dann gibt es einen Isomorphismus Z/nZ → hgi.
Für Anwendungen praktischer Art ist allerdings der im Abschnitt 1.4 gege-
bene konstruktive Beweis von größerer Bedeutung, vgl Satz 1.4.23.
Beweis. Sei g : Z → Z/mZ × Z/nZ der durch g(a) := [a]m , [a]n definierte
Gruppenhomomorphismus. Dann ist
Daraus sehen wir mnZ ⊂ ker(g). Es gilt aber auch ker(g) ⊂ mnZ, denn jedes
a ∈ ker(g) ist durch m und n teilbar. Das heißt, es gibt k ∈ Z, so dass a = kn
ist und da ggT(m, n) = 1 folgt dann m | k aus Satz 1.1.7. Damit ist a durch
mn teilbar und somit ker(g) ⊂ mnZ, also schließlich ker(g) = mnZ. Der
Homomorphiesatz besagt dann, dass g einen Isomorphismus ḡ : Z/mnZ →
im(g) induziert. Das zeigt, dass ord(im(ḡ)) = ord (Z/mnZ) = mn gilt. Weil
(Z/mZ)×(Z/nZ) ebenfalls von Ordnung mn ist, muss im(ḡ) = Z/mZ×Z/nZ
gelten, und es folgt, dass f = ḡ ein Isomorphismus ist.
Für die Aussage über (Z/mnZ)∗ wechseln wir von der additiven zur mul-
tiplikativen Struktur von Z/mnZ. Obwohl wir erst im Abschnitt 1.4, bei
der Beschäftigung mit Ringen, Addition und Multiplikation gleichzeitig be-
trachten werden, können wir bereits an dieser Stelle einen direkten Beweis
∗
geben. Wir benutzen dazu, dass für [a] ∈ Z/nZ die Eigenschaft
[a] ∈ (Z/nZ)
12
zu ggT(a, n) = 1 äquivalent ist . Daher ist f [a]mn = [a]m , [a]n ge-
∗ ∗
nau dann in Z/mZ × Z/nZ enthalten, wenn ggT(a, m) = 1 und
ggT(a, n) = 1 gilt. Für solche a gibt es ganze Zahlen r, s, r′ , s′ , so dass
ra + sn = 1 und r′ a + s′ m = 1. Daraus erhalten wir ram + smn = m und
1 = r′ a + s′ (ram + smn) = (r′ + s′ rm)a + (s′ s)mn.
Somit ist ggT(a, mn) = 1,
d.h. [a]mn ∈ (Z/mnZ)∗ . Also ist f (Z/mnZ)∗ = (Z/mZ)∗ × (Z/nZ)∗ und
wegen der Injektivität von f folgt die Behauptung. ⊓
⊔
Bemerkung 1.3.35. Man kann zeigen, dass jede endliche abelsche Gruppe
isomorph zu einer Gruppe der Gestalt
ist. Durch Anwendung von Satz 1.3.34 kann man immer erreichen, dass die
ni Primzahlpotenzen sind.
Zum Abschluss dieses Abschnittes wenden wir uns nochmals der Fehlererken-
nung zu. Wir beginnen mit einer genaueren Analyse der Güte der Prüfzeichen
bei EAN und ISBN, die wir am Ende von Abschnitt 1.2 betrachtet hatten.
Anschließend benutzen wir den in diesem Abschnitt eingeführten Begriff der
Gruppe, um diese Beispiele zu verallgemeinern. Das erlaubt es uns schließlich,
die Prüfgleichung, die bei der Nummerierung ehemaliger deutscher Bankno-
ten verwendet wurde, zu verstehen.
Sowohl EAN als auch P ISBN-13 bestehen aus 13 Ziffern a1 , . . . , a13 , welche
die Prüfgleichung 13 i=1 wi ai ≡ 0 mod 10 erfüllen. Dabei haben wir wi =
2 + (−1)i gesetzt, oder im Klartext
(
1 falls i ungerade,
wi =
3 falls i gerade.
Eine ISBN-10 besteht dagegen aus 10 Zeichen a1 , . . . , a10 , die aus der Menge
{0, 1, . . . , 9, X} sind. Das Symbol X wird als [10] ∈ Z/11Z interpretiert und
P10
ist nur als a10 zugelassen. Die Prüfgleichung lautet i=1 iai ≡ 0 mod 11.
In beiden Situationen finden wir eine Prüfgleichung der Gestalt
k
X
wi ai ≡ c mod n (1.20)
i=1
vor, wobei die ai Repräsentanten von Elementen von Z/nZ sind, die mit
sogenannten Gewichten“ wi ∈ Z zu multiplizieren sind.
”
Wir können ganz allgemein mit einem endlichen Alphabet starten und
Prüfgleichungen für Worte fester Länge untersuchen. Dazu werden die Ele-
mente des Alphabets nummeriert, wodurch wir eine Bijektion zwischen einem
n Symbole enthaltenden Alphabet und Z/nZ erhalten. Wenn die Wortlänge
gleich k ist, dann wählen wir k Gewichte [wi ] ∈ Z/nZ, i = 1, . . . , k und fi-
xieren ein Element [c] ∈ Z/nZ. In dieser Situation messen wir die Güte der
Prüfgleichung (1.20) durch die Zahl der Fehler, die durch sie erkannt werden.
Bei der manuellen Übermittlung von Daten sind typische Fehler:
Einzelfehler: Genau eines der ai ist falsch.
Transposition: Zwei benachbarte Symbole ai und ai+1 sind vertauscht.
Um festzustellen, ob die Prüfgleichung (1.20) diese Fehler erkennt, nehmen
wir an, das korrekte Wort lautet a1 a2 . . . ak und das möglicherweise fehlerhaft
übermittelte ist b1 b2 . . . bk .
Über das korrekte Wort, welches uns als Empfänger des Wortes b1 b2 . . . bk ja
nicht wirklich bekannt ist, wissen wir lediglich, dass die Prüfgleichung
40 1 Zahlen
k
X
wi ai ≡ c mod n
i=1
Pk
gilt. Als weitere Information können wir die Summe i=1 wi bi berechnen.
Deshalb kennen wir auch die Diskrepanz
k
X k
X
δ := wi (ai − bi ) ≡ c − wi bi mod n .
i=1 i=1
Bei Vorliegen eines Einzelfehlers bzw. einer Transposition heißt das konkret:
Einzelfehler: Wenn nur aj falsch ist, dann ist δ ≡ wj (aj − bj ) mod n;
Transposition: Wenn bj+1 = aj und bj = aj+1 , ansonsten aber alles korrekt
übermittelt wurde, dann ist δ ≡ (wj − wj+1 ) · (aj − aj+1 ) mod n.
Pk
Ein Fehler wird erkannt, wenn die Prüfsumme i=1 wi bi nicht kongruent c
modulo n ist, also genau dann, wenn die Diskrepanz δ von Null verschieden
ist. Das führt auf folgende Bedingungen zur Fehlererkennung:
Einzelfehler: Ein Fehler liegt vor, wenn [aj ] 6= [bj ]. Er wird erkannt, wenn
dies [wj ] · ( [aj ] − [bj ] ) 6= [0] zur Folge hat.
Transposition: Ein Fehler liegt vor, wenn [aj ] 6= [aj+1 ]. Er wird erkannt,
wenn dann auch ( [wj ] − [wj+1 ] )( [aj ] − [aj+1 ] ) 6= [0] gilt.
Um jeden Einzelfehler erkennen zu können, muss [wj ] ein multiplikatives
Inverses besitzen, das heißt [wj ] ∈ (Z/nZ)∗ . Diese Bedingung ist für EAN
und ISBN-10 erfüllt.
Zur Erkennung aller Transpositionen muss [wj ] − [wj+1 ] ∈ (Z/nZ)∗ sein. Bei
der EAN ist jedoch [wj ] − [wj+1 ] = ±[2] 6∈ (Z/10Z)∗ , denn ggT(±2, 10) = 2.
Daher werden Transpositionen zweier Zahlen, deren Differenz fünf ist, durch
die Prüfsumme nicht erkannt. Die Übermittlung von 61 statt 16 bleibt zum
Beispiel unbemerkt. Dagegen wird die fehlerhafte Übermittlung von 26 statt
62 erkannt. Bei der ISBN-10 ist wj = j, also [wj ]− [wj+1 ] = [−1] ∈ (Z/11Z)∗ .
Damit werden in diesem Fall alle Transpositionen erkannt.
Daran sehen wir, dass die Prüfgleichung der inzwischen abgeschafften ISBN-
10 derjenigen der EAN und der neuen ISBN-13 bei der Fehlererkennung
überlegen war. Beim maschinellen Lesen von Strichcodes sind allerdings
Transpositionsfehler von untergeordneter Bedeutung, so dass diese Schwäche
kaum praktische Relevanz haben sollte.
Der Nachteil der Prüfgleichung der ISBN-10 war die Notwendigkeit der
Einführung eines elften Symbols X“. Wenn wir ein Alphabet mit zehn
”
Symbolen bevorzugen, dann führt uns die geschilderte Methode auf eine
∗
Prüfgleichung in Z/10Z. Da Z/10Z = {±1, ±3}, sind auf diese Weise keine
wesentlichen Verbesserungen der EAN möglich. Um bessere Fehlererkennung
zu erreichen, kann man versuchen, die additive Gruppe Z/10Z durch eine
andere Gruppe zu ersetzen. Man kann zeigen, dass jede Gruppe der Ordnung
10 zu Z/10Z oder D5 isomorph ist.
1.3 Gruppen 41
Doch zunächst sei ganz allgemein (G, ∗) eine Gruppe mit n Elementen und
c ∈ G fixiert. Statt einer Multiplikation mit Gewichten wi erlauben wir nun
beliebige Permutationen σi ∈ sym(G), 1 ≤ i ≤ k. Das führt zur Prüfgleichung
Q
Satz 1.3.36 Eine Prüfgleichung der Form ki=1 σ i (ai ) = c erkennt alle Ein-
zelfehler. Wenn für x 6= y ∈ G stets x ∗ σ(y) 6= y ∗ σ(x) gilt, dann werden
auch alle Transpositionen erkannt.
Beweis. Da δ = σ 1 (a1 )∗σ 2 (a2 )∗. . .∗σ k (ak )∗σ k (bk )−1 ∗. . .∗σ 2 (b2 )−1 ∗σ 1 (b1 )−1 ,
kann ein Einzelfehler an Position j nur dann unerkannt bleiben, wenn e =
σ j (aj ) ∗ σ j (bj )−1 , also σ j (aj ) = σ j (bj ) gilt. Da σ j bijektiv ist, ist das nur
möglich, wenn aj = bj , also überhaupt kein Fehler vorliegt. Damit ist die
Erkennung aller Einzelfehler gesichert.
Wenn an den Positionen i und i + 1 statt (a, b) das Paar (b, a) übermittelt
wurde, dann wird dies durch die Prüfgleichung genau dann erkannt, wenn
σ i (a) ∗ σ i+1 (b) 6= σ i (b) ∗ σ i+1 (a) gilt. Mit x := σ i (a) 6= σ i (b) =: y folgt dies
aus der Voraussetzung x ∗ σ(y) 6= y ∗ σ(x). ⊓
⊔
Beispiel 1.3.37. Sei jetzt G = D5 = {1, t, t2 , t3 , t4 , s, st, st2 , st3 , st4 }. Wir
nummerieren die Elemente dieser Gruppe, indem wir jede der Ziffern 0, . . . , 9
in der Form 5i + j schreiben und dann dem Element tj si ∈ D5 zuordnen. Das
führt zu folgender Tabelle
0 1 2 3 4 5 6 7 8 9
1 t t2 t3 t4 s st4 st3 st2 st
Dadurch kann die Permutation
0123456789
σ = (0 1 5 8 9 4 2 7) ◦ (3 6) = ∈ S10
1576283094
als Permutation der Elemente der Gruppe D5 aufgefasst werden. Man erhält
x 1 t t2 t3 t4 s st st2 st3 st4
σ(x) t s st3 st4 t2 st2 t4 st 1 t3
Es gilt tatsächlich xσ(y) 6= yσ(x) für x 6= y ∈ D5 , siehe Aufgabe 1.23.
42 1 Zahlen
Aus Satz 1.3.36 erhalten wir, dass dadurch alle Einzelfehler und Transposi-
tionen erkannt werden konnten. Da an der Position 10 ein Buchstabe und an
Position 11 eine Ziffer verwendet wurde, ist es nicht nötig, den Beweis an die
leicht veränderte Prüfgleichung anzupassen.
Abb. 1.2 Eine ehemalige 10-DM Banknote mit Nummer DS1170279G9 vom 1. 10. 1993
Position i 1 2 3 4 5 6 7 8 9 10 11
Ziffer a 1 6 1 1 7 0 2 7 9 2 9
Potenz von σ σ σ2 σ3 σ4 σ5 σ6 σ7 Id σ σ2 Id
σi (a) 5 6 9 4 9 2 4 7 4 0 9
Element in D5 s st4 st t4 st t2 t4 st3 t4 1 st
Tabelle 1.1 Überprüfung der Nummer einer ehemaligen Banknote
d.h. M ist die kleinstmögliche Zahl, für die sich der Würfel aus jeder belie-
bigen Stellung mit höchstens M Drehungen wieder in Grundstellung bringen
lässt. Anfang der achtziger Jahre wurde gezeigt, dass 18 ≤ M ≤ 52 ist. Bis
heute ist die Zahl M nicht bekannt. Man weiß jetzt, dass 20 ≤ M ≤ 22 gilt.
Dieses Ergebnis geht auf Tomas Rokicki (USA) zurück, der das Problem auf
aufwändige Rechnungen mit Nebenklassen einer geeigneten Untergruppe von
W zurückführte, die er dann von Computern durchführen ließ, siehe [Rok].
Aufgaben
Übung 1.13. Zeigen Sie, dass die durch f (x, y) := x − y gegebene Abbil-
dung f : Z × Z → Z ein Gruppenhomomorphismus bezüglich der additiven
Gruppenstruktur (vgl. Bsp. 1.3.2 (vi)) ist. Bestimmen Sie ker(f ) und im(f ).
1.3 Gruppen 45
Übung 1.14. Bestimmen Sie die Ordnung von jedem der sechs Elemente der
symmetrischen Gruppe S3 .
Übung 1.15. Zeigen Sie: ord([a]) = n/ ggT(a, n) für [0] 6= [a] ∈ (Z/nZ, +).
∗
Übung 1.16. (a) Welche der Gruppen D5 , S3 , Z/5Z, (Z/5Z) ist zyklisch?
(b) Beweisen Sie, dass jede endliche Gruppe, deren Ordnung eine Primzahl
ist, eine zyklische Gruppe ist.
Übung 1.17. Zeigen Sie, dass die durch g([a]) := [7a ] definierte Abbildung
∗
g : Z/16Z → (Z/17Z) ein Isomorphismus von Gruppen ist.
Übung 1.20. Sei (G, ∗) eine Gruppe und g ∈ G irgendein Element. Beweisen
Sie, dass die durch K(x) = g ∗ x ∗ g −1 gegebene Abbildung K : G → G ein
Isomorphismus von Gruppen ist.
Übung 1.23. Zeigen Sie, dass die im Beispiel 1.3.37 angegebene Permutation
σ tatsächlich die im Satz 1.3.36 für die Erkennung von Transpositionsfehlern
angegebene Bedingung erfüllt.
Übung 1.25. Bestimmen Sie die fehlende letzte Ziffer der Nummer einer
ehemaligen DM-Banknote DY3333333Z?.
Übung 1.26. Sei (G, ∗) eine Gruppe mit neutralem Element e ∈ G. Wir
nehmen an, dass für jedes a ∈ G die Gleichung a ∗ a = e gilt. Beweisen Sie,
dass G eine abelsche Gruppe ist.
46 1 Zahlen
In den Abschnitten 1.2 und 1.3 wurde die Methode der Abstraktion anhand
des konkreten Beispiels der Restklassen ganzer Zahlen und des allgemeinen
Begriffes der Gruppe illustriert. Ein Vergleich der Gruppenaxiome (Def. 1.3.1)
mit der Liste der Eigenschaften ganzer Zahlen im Abschnitt 1.1 zeigt jedoch,
dass der Gruppenbegriff nicht alle Aspekte des Rechnens mit ganzen Zahlen
reflektiert. Wir benötigen eine mathematische Struktur mit zwei Rechen-
operationen: einer Addition und einer Multiplikation. Das führt uns zu den
Begriffen Ring und Körper. Diese Begriffe umfassen sowohl die uns vertrau-
ten Zahlbereiche als auch Polynomringe. Letztere besitzen verblüffend große
strukturelle Ähnlichkeit zum Ring der ganzen Zahlen.
Als Anwendung werden wir im folgenden Abschnitt 1.5 erste Schritte in der
Kryptographie unternehmen.
Wenn n keine Primzahl ist, dann ist Z/nZ kein Körper, denn die Eigenschaft
(1.25) ist für zusammengesetztes n verletzt. Zum Beispiel gilt [2] · [3] = [0] in
Z/6Z. Echte Teiler von n haben kein multiplikatives Inverses modulo n und
somit ist (Z/nZ) r {[0]} keine Gruppe bezüglich der Multiplikation. Daher
ist es notwendig, den etwas allgemeineren Begriff des Ringes einzuführen.
Wenn im Folgenden von einem Ring die Rede ist, dann meinen wir stets einen
kommutativen Ring mit Eins. In anderen Lehrbüchern wird bei dem Begriff
des Ringes mitunter in (1.28) auf die Kommutativität der Multiplikation oder
auf die Existenz eines neutralen Elements
1 ∈ R verzichtet.
Die Menge aller 2×2-Matrizen ac db mit ganzzahligen Einträgen a, b, c, d ∈ Z
bilden einen Ring bezüglich der gewöhnlichen Addition von Matrizen und der
Matrizenmultiplikation (Def. 2.2.22) als Produkt. Die Einheitsmatrix ( 10 01 )
ist das Einselement dieses Ringes und die Matrix, deren Einträge sämtlich
gleich Null sind, ist das Nullelement dieses Ringes. Da
01 00 10 00 00 01
◦ = 6= = ◦ ,
00 10 00 01 10 00
ist dieser Ring nicht kommutativ. Er wird also in diesem Buch nicht weiter
auftauchen.
Der einzige Unterschied zwischen den Definitionen der Begriffe Ring und
Körper ist, dass für einen Ring nicht gefordert wird, dass zu jedem r ∈ R mit
r 6= 0 ein multiplikatives Inverses existiert. Allerdings ist deshalb in einem
Ring nicht mehr automatisch 1 6= 0. Wenn jedoch in einem Ring 0 = 1 gilt,
dann sind alle Elemente dieses Ringes gleich 0. Mit anderen Worten: Der
einzige Ring, in dem 0 = 1 ist, ist der Nullring R = {0}. In jedem anderen
Ring gilt 1 6= 0. In allen Ringen gelten weiterhin (1.24) und (1.26). Die
Aussage (1.25) gilt in allgemeinen Ringen jedoch nicht.
Beispiel 1.4.4. (i) Jeder Körper, insbesondere R und Q, aber auch die
Menge der ganzen Zahlen Z sind Ringe.
(ii) Für jedes n ∈ Z ist Z/nZ ein Ring.
(iii) Wenn R und R′ Ringe sind, dann ist das kartesische Produkt R × R′ mit
den Verknüpfungen
(r, r′ ) + (s, s′ ) := (r + s, r′ + s′ )
(r, r′ ) · (s, s′ ) := (r · s, r′ · s′ )
ebenfalls ein Ring. Selbst wenn R und R′ Körper sind, ist R × R′ kein
Körper. Das liegt daran, dass stets (1, 0) · (0, 1) = (0, 0) = 0 gilt.
Beispiel 1.4.5 (Polynomringe). Sei R ein Ring. Dann definieren wir den
Polynomring R[X] wie folgt. Die zugrunde liegende Menge enthält alle Poly-
nome in der Unbestimmten X mit Koeffizienten aus dem Ring R:
48 1 Zahlen
( )
n
X
R[X] = ai X i n ≥ 0, ai ∈ R .
i=0
Ein Polynom ist somit ein formaler Ausdruck, in dem die Unbestimmte“ X
”
auftritt. Zwei solche Ausdrücke sind genau dann gleich, wenn ihre Koeffizien-
ten ai übereinstimmen. Polynome sind nicht dasselbe wie Polynomfunktio-
nen, die man durch das Einsetzen von Elementen x ∈ K für X aus Polynomen
erhält, vgl. Aufgabe 1.35. Die Addition ist komponentenweise definiert:
n m max(m,n)
X X X
ai X i + bj X j := (ai + bi )X i
i=0 j=0 i=0
n
! m
n+m k
!
X X X X
ai X i · bj X j = ai bk−i X k .
i=0 j=0 k=0 i=0
Konkret erhalten wir für X 2 +1, 2X−3 ∈ Z[X] folgende Summe und Produkt:
(X 2 + 1) · (2X − 3) = 2X 3 − 3X 2 + 2X − 3, sowie
(X 2 + 1) + (2X − 3) = X 2 + 2X − 2 .
Der Polynomring K[X] über einem Körper K weist viel Ähnlichkeit mit dem
in Abschnitt 1.1 studierten Ring der ganzen Zahlen auf. Die Ursache dafür
besteht im Vorhandensein eines Euklidischen Algorithmus für Polynome, der
auf der folgenden Division mit Rest basiert.
Beweis. Der Beweis erfolgt per Induktion über k := deg(f )− deg(g) ≥ 0. Der
Induktionsanfang (k = 0) und der Induktionsschritt (Schluss von k auf k + 1)
ergeben sich aus der folgenden Überlegung, bei der k ≥ 0 beliebig ist. Sei
f = aX n+k + . . . und g = bX n + . . ., wobei nur die Terme höchsten Grades
(Leitterme) aufgeschrieben sind. Die Leitkoeffizienten sind a 6= 0 und b 6= 0.
Es gilt also deg(f ) = n + k und deg(g) = n. Dann ist
deg f − ab · X k · g < n + k = deg(f ),
denn der Leitterm von f wird durch Subtraktion von ab X k g entfernt. ⊓ ⊔
f = X 4 − 1 und g = X 3 − 1 .
(X 4 − 1) − X · (X 3 − 1) = X − 1
(X 3 − 1) − (X 2 + X + 1)(X − 1) = 0 .
f − (X − 3)g = 3X − 3 und
1
(X 2 − 1) − (X + 1)(3X − 3) = 0 .
3
1.4 Ringe und Körper 51
Der Beweis, dass dieser Algorithmus stets nach endlich vielen Schritten endet
und tatsächlich den größten gemeinsamen Teiler berechnet, ist fast wörtlich
derselbe wie für den Euklidischen Algorithmus in Z. Daher wird er hier weg-
gelassen. Alle Eigenschaften der ganzen Zahlen, die mit Hilfe des Euklidischen
Algorithmus bewiesen wurden, lassen sich auch für Polynomringe K[X] mit
Koeffizienten in einem Körper K beweisen. Die Beweise übertragen sich aus
Abschnitt 1.1 fast wörtlich.
Satz 1.4.13 (1) Für f, g, h ∈ K[X] gilt genau dann h = ggT(f, g), wenn es
Polynome r, s ∈ K[X] gibt, so dass h = rf + sg und wenn jedes andere
Polynom dieser Gestalt durch h teilbar ist.
(2) Wenn f, g, h ∈ K[X] Polynome sind, für die ggT(f, h) = 1 und f | g · h
gilt, dann folgt f | g.
(3) Ein Polynom f heißt irreduzibel, wenn aus f = g · h stets g ∈ K oder
h ∈ K folgt. Dies ist äquivalent dazu, dass aus f | gh stets f | g oder
f | h folgt.
(4) Jedes Polynom 0 6= f ∈ K[X] hat eine, bis auf die Reihenfolge eindeutige,
Darstellung f = u·p1 ·p2 ·. . .·pk , wobei u ∈ K ∗ und pi ∈ K[X] irreduzible
Polynome mit Leitkoeffizient 1 sind.
Da der Ring K[X] in seiner Struktur dem Ring Z so sehr ähnlich ist, entsteht
die Frage, ob es auch für Polynomringe möglich ist, auf Restklassenmengen
in ähnlicher Weise wie auf Z/nZ eine Ringstruktur zu definieren. Das führt
allgemeiner auf die Frage, für welche Teilmengen I ⊂ R eines beliebigen
Ringes R sich die beiden Rechenoperationen + und · auf R/I vererben. Dafür
ist nicht ausreichend, dass Summen und Produkte von Elementen aus I stets
in I sind. Eine Analyse des Wohldefiniertheitsproblems führt auf die folgende
Definition.
Definition 1.4.14. Sei R ein Ring und I ⊂ R eine nichtleere Teilmenge. Wir
nennen I ein Ideal 13 , falls die folgenden beiden Bedingungen erfüllt sind:
Aus (1.30) und (1.31) folgt, dass I ⊂ R ist eine Untergruppe bezüglich der
Addition ist.
13 Der deutsche Mathematiker Richard Dedekind (1831–1916) führte den Begriff des
Ideals ein, um für bestimmte Erweiterungen des Ringes der ganzen Zahlen eine Verallge-
meinerung der in der Formulierung von Satz 1.1.8 dort nicht mehr gültigen eindeutigen
Primfaktorzerlegung zu erhalten.
52 1 Zahlen
ein Ideal. Für k = 1 erhalten wir hai = a · R = {ra | r ∈ R}. Dies verall-
gemeinert die Ideale nZ ⊂ Z. Ideale der Gestalt hai heißen Hauptideale.
(iii) Stets ist h1i = R ein Ideal. Es ist das einzige Ideal, das ein Unterring ist.
Satz 1.4.16 Sei R ein Ring, I ⊂ R ein Ideal. Dann wird auf der additiven
Gruppe R/I durch [a] · [b] := [a · b] die Struktur eines Ringes definiert.
Satz 1.4.17 Wenn K ein Körper ist, dann ist K[X] ein Hauptidealring.
Das heißt, für jedes Ideal I ⊂ K[X] gibt es ein f ∈ K[X], so dass I = hf i.
Beweis. Der Beweis ist analog zum Beweis von Satz 1.3.18. Sei I ⊂ K[X] ein
Ideal. Wenn I = {0}, dann können wir f = 0 wählen und sind fertig. Sei von
nun an I 6= {0}. Da für g 6= 0 der Grad deg(g) ≥ 0 stets eine nicht-negative
ganze Zahl ist, gibt es mindestens ein Element f ∈ I von minimalem Grad.
Das heißt, für jedes 0 6= g ∈ I ist deg(f ) ≤ deg(g). Jedes 0 6= g ∈ I lässt
sich als g = r + h · f mit r, h ∈ K[X] schreiben, so dass deg(r) < deg(f )
(Division mit Rest). Da I ein Ideal ist, muss r = g − hf ∈ I sein. Wegen der
Minimalität des Grades von f folgt r = g − hf = 0, d.h. g ∈ hf i und somit
I = hf i. ⊓
⊔
Definition 1.4.18. (1) Ein Element a ∈ R eines Ringes R heißt Nullteiler,
wenn ein 0 6= b ∈ R mit a · b = 0 existiert.
(2) Ein Element a ∈ R heißt Einheit, wenn ein b ∈ R mit a · b = 1 existiert.
(3) Ein Ring R heißt nullteilerfrei, wenn 0 ∈ R der einzige Nullteiler ist.
Bei der Benutzung dieser Begriffe ist Vorsicht geboten, denn für jedes a ∈
R gilt a | 0, auch wenn a kein Nullteiler ist. Ein Ring R ist genau dann
nullteilerfrei, wenn aus a · b = 0 stets a = 0 oder b = 0 folgt. Das heißt, dass
1.4 Ringe und Körper 53
Beispiel 1.4.19. (i) Die Einheiten eines Ringes sind genau die Elemente,
die ein multiplikatives Inverses besitzen. Daher ist die Menge aller Ein-
heiten
R∗ := {a ∈ R | a ist Einheit in R}
eine multiplikative Gruppe.
Es gilt (Z/nZ)∗ = {[a] ∈ Z/nZ | ggT(a, n) = 1}. Für jeden Körper K ist
K ∗ = K r {0}. Ein Ring R ist genau dann Körper, wenn R∗ = R r {0}.
(ii) Wenn n ≥ 2, dann ist in Z/nZ jedes Element entweder Nullteiler oder
Einheit (vgl. Aufg. 1.32), denn
(iii) Der einzige Nullteiler in Z ist 0, also ist Z nullteilerfrei. Außerdem gilt
Z∗ = {1, −1}. In dem Ring Z ist somit jedes von 0, 1 und −1 verschiedene
Element weder Nullteiler, noch Einheit.
(iv) Für beliebige Ringe R, S gilt (R × S)∗ = R∗ × S ∗ .
Man sieht leicht ein, dass 0 = (0, 0) und 1 = (1, 0) gilt, womit man die in der
Definition eines Körpers geforderten Eigenschaften leicht nachrechnen kann.
Der interessanteste Teil dieser recht ermüdenden Rechnungen ist die Angabe
eines multiplikativen Inversen für (a, b) 6= (0, 0):
a −b
(a, b)−1 = , .
a2 + b 2 a2 + b 2
Zur Vereinfachung ist es üblich i = (0, 1) zu schreiben. Statt (a, b) wird dann
a + bi geschrieben. Dadurch lässt sich die oben angegebene Definition der
54 1 Zahlen
2 + 3i (2 + 3i)(1 + i) 2 + 2i + 3i − 3 −1 + 5i 1 5
= = = =− + i.
1−i (1 − i)(1 + i) 1+1 2 2 2
Die graphische Darstellung14 der komplexen Zahlen in der reellen Ebene und
die geometrische Interpretation der Addition und Multiplikation (Abb. 1.4)
sind nützliche Hilfsmittel. Dadurch lässt sich die algebraische Struktur, die
wir dadurch auf den Punkten der reellen Ebene erhalten, zur Lösung von
Problemen der ebenen Geometrie anwenden.
• z1 + z2 •z1 · z2
z2 •
z2 r2 z1
•
• z1 z1
•
0 1 r2 = |z2 |
14 Die früheste, heute bekannte Publikation der Idee, komplexe Zahlen durch Punkte einer
Ebene zu repräsentieren, erschien im Jahre 1799. Sie stammt von dem norwegisch-dänischen
Mathematiker Caspar Wessel (1745–1818), blieb aber damals weitgehend unbemerkt.
Zum Allgemeingut wurde diese Idee durch ein kleines Büchlein, welches im Jahre 1806 vom
Schweizer Buchhalter und Amateurmathematiker Jean-Robert Argand (1768–1822) in
Paris veröffentlicht wurde. In der englischsprachigen Literatur spricht man daher von der
Argand Plane, in der französischen dagegen manchmal von der plan de Cauchy. Der deut-
sche Mathematiker Carl Friedrich Gauß (1777–1855) trug durch eine Publikation im
Jahre 1831 zur Popularisierung dieser Idee bei. Daher spricht man in der deutschsprachigen
Literatur von der Gaußschen Zahlenebene.
1.4 Ringe und Körper 55
f = c · (X − a1 ) · (X − a2 ) · . . . · (X − an ) .
Dabei ist c ∈ C∗ der Leitkoeffizient, n = deg(f ) der Grad und die ai ∈ C sind
die Nullstellen von f .
Eine komplexe Zahl a ∈ C ist genau dann Nullstelle von f , wenn f (a) = 0 gilt.
Jedes Polynom f ∈ C[X] von positivem Grad hat mindestens eine Nullstelle
in C. Für Teilkörper von C ist dies nicht der Fall.
Bevor wir uns den versprochenen Anwendungen der bisher entwickelten Theo-
rie zuwenden können, müssen noch zwei sehr nützliche Werkzeuge behandelt
werden. Es handelt sich um den Homomorphiesatz und um den Chinesischen
Restsatz.
ϕ : R/ ker(ϕ) → im(ϕ)
Beweis. Der Teil (a) ist lediglich eine andere Formulierung von 1.4.23. Statt
des angegebenen konstruktiven Beweises kann man (a) aber auch per In-
duktion aus Satz 1.3.34 gewinnen. Dazu muss man noch bemerken, dass für
beliebige k ∈ Z stets [ab]k = [a]k · [b]k und [1]k = 1 im Ring Z/kZ gilt, und
dass somit der Gruppenhomomorphismus in Satz 1.3.34 sogar ein Ringiso-
morphismus ist.
Da nach Beispiel 1.4.19 (iv) für beliebige Ringe Ri die Einheitengruppe von
R = R1 × . . . × Rk gleich R∗ = R1∗ × . . . × Rk∗ ist, folgt (b) aus (a). ⊓
⊔
15 In einem chinesischen Mathematiklehrbuch, welches vermutlich etwa im dritten Jahr-
hundert u.Z. geschrieben wurde, wird nach einer Zahl x gefragt, welche die drei Kongru-
enzen x ≡ 2 mod 3, x ≡ 3 mod 5 und x ≡ 2 mod 7 erfüllt. Die Lösung wurde dort mit
der gleichen Methode ermittelt, die auch dem hier angegebenen Beweis zugrunde liegt. Es
handelt sich dabei um die früheste bekannte Quelle, in der ein solches Problem behandelt
wurde, daher der Name des Satzes.
1.4 Ringe und Körper 57
Wochentag Mo Di Mi Do Fr Sa So
Häufigkeit 2 3 4 1 6 5 7
Person P1 P2 P3 P4 P5 P6 P7
Tabelle 1.2 Häufigkeit der Waschmaschinenbenutzung
in der diese Häufigkeit dem Wochentag zugeordnet ist, an dem die betref-
fende Person in der ersten Woche ihre Wäsche zu waschen beabsichtigte. So
wäscht zum Beispiel der Mieter der am Montag wäscht jeden zweiten Tag
seine Wäsche, danach dann am Mittwoch, am Freitag, am Sonntag u.s.w.
Wie lange hatten die Hausbewohner Zeit, die Waschmaschine reparieren
zu lassen, ohne dass jemand seinen Rhythmus ändern musste?
Zur Beantwortung dieser Frage gilt es herauszufinden, wann erstmalig alle
Mieter am selben Tag waschen wollten. Dazu nummerieren wir die Tage fort-
laufend, beginnend mit 1 am Montag nach der Zusammenkunft der Mieter.
Die Mieter bezeichnen wir mit P1 , P2 , . . . , P7 , so dass Pi am Tag i wäscht. Die
Waschhäufigkeit mi von Pi ist der Eintrag in der mittleren Zeile von Tabelle
1.2. Die Person Pi wäscht somit genau dann am Tag mit der Nummer x, wenn
x ≡ i mod mi gilt. Zur Lösung des Problems suchen wir daher die kleinste
ganze Zahl x > 0, welche sämtliche der folgenden Kongruenzen erfüllt:
eine Zahl x, für die x ≡ 3 mod 4 gilt, ungerade ist, können wir die Kongruenz
x ≡ 1 mod 2 ebenfalls streichen. Es verbleiben die folgenden Kongruenzen:
Wenn man die Gleichung rpi + smi = 1 als Kongruenz rpi ≡ 1 mod mi
schreibt und pi durch Reduktion modulo mi verkleinert, dann verringert sich
der Rechenaufwand ein wenig. Die Ergebnisse xi ändern sich dadurch jedoch
nicht. Als Lösung der simultanen Kongruenzen (1.35) ergibt sich
4
X
x= ai xi = 2 · 280 + 3 · 105 + 1 · 336 + 0 · 120 = 1211 .
i=1
Die allgemeine Lösung hat daher die Gestalt 1211 + n · 420 mit n ∈ Z und die
kleinste positive Lösung ist 1211 − 2 · 420 = 371. Die Hausbewohner haben
also 371 Tage – mehr als ein Jahr – Zeit, die Waschmaschine reparieren zu
lassen, vorausgesetzt keine weitere Waschmaschine fällt aus und keiner der
Mieter ändert seinen Waschrhythmus.
Eine genaue Betrachtung des oben beschriebenen Algorithmus zur Lösung si-
multaner Kongruenzen zeigt, dass in jeder Teilaufgabe mit den relativ großen
Zahlen pi gerechnet wird. Wenn eine hohe Anzahl von Kongruenzen vorliegt
kann dies durchaus zu beträchtlichem Rechenaufwand führen. Durch eine
schrittweise Berechnung der Lösung x kann man hier eine Verbesserung errei-
chen. Die Idee besteht darin, dass man induktiv aus der allgemeinen Lösung
1.4 Ringe und Körper 59
der ersten t Kongruenzen die allgemeine Lösung der ersten t+1 Kongruenzen
bestimmt.
Als Induktionsanfang können wir x = a1 wählen. Sei xt eine Lösung der
ersten t Kongruenzen: xt ≡ ai mod mi für 1 ≤ i ≤ t. Dann gilt für jede
Lösung xt+1 der ersten t + 1 Kongruenzen
Um xt+1 zu bestimmen, müssen wir alle ganzen Zahlen y ermitteln, für die
x1 = 2 y ≡ (a2 − x1 )m−1
1 mod m2
−1
y ≡ (3 − 2)3 mod 4
y ≡ 3 mod 4
x2 = x1 + 3y = 11 y ≡ (a3 − x2 )(m1 m2 )−1 mod m3
−1
y ≡ (1 − 11)12 mod 5
y ≡ 0 mod 5
x3 = x2 + 12y = 11 y ≡ (a4 − x3 )(m1 m2 m3 )−1 mod m4
−1
y ≡ (0 − 11)60 mod 7
y ≡ 6 mod 7
x4 = x3 + 60y = 371 =⇒ x = 371 .
Bemerkung 1.4.26. Beim Rechnen mit sehr großen ganzen Zahlen kommt
der Chinesische Restsatz in der Informatik zur Anwendung. Nehmen wir
an, ein polynomialer Ausdruck P (a1 , . . . , ar ) soll für konkret gegebene, aber
sehr große ai ∈ Z berechnet werden. Bei bekanntem Polynom P kann man
zunächst leicht eine obere Schranke für das Ergebnis berechnen. Sei m ∈ Z
so, dass |P (a1 , . . . , ar )| < m/2 gilt. Dann genügt es, die Rechnung in Z/mZ
durchzuführen. Wenn m sehr groß ist, mag das noch keine bemerkenswerte
Verbesserung bringen. An dieser Stelle kann der Chinesischen Restsatz helfen.
Dazu wählen wir relativ kleine paarweise teilerfremde Zahlen mi , deren Pro-
dukt m = m1 · m2 · . . . · mk sich als Schranke wie zuvor eignet. Bei der
Berechnung von P (a1 , . . . , ar ) mod mi treten nun keine sehr großen Zahlen
mehr auf. Mit Hilfe des obigen Algorithmus zur Lösung simultaner Kongruen-
60 1 Zahlen
Zum Abschluss dieses Abschnittes wenden wir uns einem sowohl theoretisch
als auch praktisch sehr nützlichen Resultat zu. Mit seiner Hilfe kann man
Multiplikationen im Körper Fp für große Primzahlen p wesentlich schneller
ausführen. Bei der Implementierung mancher Programmpakete der Compu-
teralgebra macht man sich dies tatsächlich zu Nutze.
erhalten. Das ist nur möglich, wenn jede der Ungleichungen |Gd | ≤ ϕ(d) eine
Gleichung ist. Insbesondere muss |Gm | = ϕ(m) ≥ 1 sein, das heißt, in der
multiplikativen Gruppe F∗p gibt es ein Element der Ordnung m = p − 1. ⊓ ⊔
Bemerkung 1.4.28. Der gleiche Beweis zeigt, dass für jeden endlichen
Körper K die multiplikative Gruppe K ∗ zyklisch ist.
Beispiel 1.4.29. F∗5 ist eine zyklische Gruppe der Ordnung 4. Da ϕ(4) = 2
ist, gibt es zwei Erzeuger. Dies sind [2] und [3], denn
Dagegen sind [1] und [4] keine Erzeuger. Es gilt ord([1]) = 1 und ord([4]) = 2.
Folgerung 1.4.30. Für jede ganze Zahl e ≥ 1 und jede Primzahl p > 2 ist
∗
(Z/pe Z) eine zyklische Gruppe.
Beweis. Der Fall e = 1 wurde in Satz 1.4.27 behandelt. Sei nun e ≥ 2 und
w ∈ Z eine ganze Zahl, so dass [w]p ein Erzeuger der zyklischen Gruppe
∗
(Z/pZ) ist. Wir werden zeigen, dass
e−1
z := wp · (1 + p) mod pe
62 1 Zahlen
ein Element der Ordnung (p − 1)pe−1 in (Z/pe Z)∗ ist. Daraus folgt die Be-
∗
hauptung, denn ord (Z/pe Z) = (p − 1)pe−1 . Nach Satz 1.3.23 (2) kommen
j
nur Zahlen der Gestalt k · p mit k | p − 1 und 0 ≤ j ≤ e − 1 als Ordnung
von z in Frage.
Nach dem kleinen Satz von Fermat (Satz 1.3.24) gilt wp ≡ w mod p, woraus
j j+e−1
z kp ≡ wp k
≡ wk mod p folgt. Weil [w]p die Ordnung p hat, ist somit
j j
z kp 6≡ 1 mod p für 0 < k < p − 1. Daher gilt auch z kp 6≡ 1 mod pe und es
folgt ord(z) = (p − 1)pj für ein 0 ≤ j ≤ e − 1.
e−1 j
Wegen Satz 1.3.23 (3) gilt wp (p−1) ≡ 1 mod pe , woraus wir z (p−1)p ≡
j
(1 + p)(p−1)p mod pe erhalten. Die Behauptung der Folgerung folgt daher,
wenn wir per Induktion über e ≥ 2 gezeigt haben, dass
e−2
(1 + p)(p−1)p 6≡ 1 mod pe (1.36)
gilt. Dabei werden wir benutzen, dass wegen Satz 1.3.23 (3) für alle e ≥ 1
gilt:
e−1
(1 + p)(p−1)p ≡ 1 mod pe . (1.37)
Für den Induktionsanfang bei e = 2 verwenden wir die Binomische Formel
(vgl. Aufgabe 1.5) und erhalten
p−1 2
(1 + p)p−1 = 1 + (p − 1)p + p + . . . + pp−1 ≡ 1 − p 6≡ 1 mod p2 .
2
Die Voraussetzung für den Induktionsschritt ist die Gültigkeit von (1.36) für
e−1
ein festes e ≥ 2. Wir haben zu zeigen, dass (1 + p)(p−1)p 6≡ 1 mod pe+1
gilt. Nach (1.37) besagt die Voraussetzung gerade, dass es eine ganze Zahl c
e−2
mit c 6≡ 0 mod p gibt, so dass (1 + p)(p−1)p = 1 + cpe−1 gilt.
Die Binomische Formel ergibt hier
p
X
e−1 p p k k(e−1)
(1 + p)(p−1)p = 1 + cpe−1 = c p
k
k=0
p 2 2(e−1)
= 1 + cpe + c p + . . . + cp pp(e−1) .
2
Da kp für 1 ≤ k ≤ p − 1 durch p teilbar ist (vgl. Aufgabe 1.6), und für
e≥ 2 die Ungleichungen 1 + k(e − e+1
1) ≥ e + 1 und p(e − 1) ≥ e + 1 gelten, ist
p k k(e−1)
k c p für 1 ≤ k ≤ p durch p teilbar. Daraus folgt
e−1
(1 + p)(p−1)p ≡ 1 + cpe 6≡ 1 mod pe+1 ,
Aufgaben
Übung 1.27. Bestimmen Sie den größten gemeinsamen Teiler der Polynome
f = X 5 − X 3 − X 2 + 1 ∈ Q[X] und g = X 3 + 2X − 3 ∈ Q[X].
Übung 1.28. Dividieren Sie f = X 5 + X 3 + X 2 + 1 durch g = X + 2 mit
Rest in F3 [X].
Übung 1.29. Beweisen Sie, dass die Menge I = {f ∈ Z[X] | f (1) = 0}, aller
Polynome f ∈ Z[X], die 1 ∈ Z als Nullstelle haben, ein Ideal ist. Ist I ein
Hauptideal?
Übung 1.30. Sei K ein Körper und f ∈ K[X] ein irreduzibles Polynom
(vgl. 1.4.13). Beweisen Sie, dass der Ring K[X]/hf i ein Körper ist.
Übung 1.31. Beweisen Sie, dass F2 [X]/hX 2 +X +1i ein Körper ist. Wie viel
Elemente enthält dieser Körper? Beschreiben Sie die multiplikative Gruppe
dieses Körpers. Ist sie zyklisch?
Übung 1.32. Beweisen Sie für jede ganze Zahl n > 1, dass jedes Element
des Ringes Z/nZ entweder eine Einheit oder ein Nullteiler ist.
Übung 1.33. Bestimmen sie die kleinste positive ganze Zahl x, welche das
folgende System simultaner Kongruenzen erfüllt:
Zusatz: Denken Sie sich eine möglichst realistische Textaufgabe (aus dem
Alltagsleben oder aus Wissenschaft und Technik) aus, die auf ein System
simultaner Kongruenzen führt.
Übung 1.34. Bestimmen Sie alle ganzen Zahlen x, welche das folgende Sys-
tem simultaner Kongruenzen erfüllen:
Übung 1.35. Finden Sie für jede Primzahl p ein Polynom 0 6= f ∈ Fp [X],
welches jedes Element des Körpers Fp als Nullstelle hat.
Finden Sie ein Polynom vom Grad 2 in F5 [X], welches in F5 keine Nullstelle
besitzt. Versuchen Sie das auch für alle anderen Körper Fp !
Übung 1.36. Sei K ein Körper und N+ := {n ∈ Z | n > 0}. Auf der Menge
I(K) := {f | f : N+ → K ist eine Abbildung} definieren wir eine Addition
und eine Multiplikation wie folgt:
X n
(f + g)(n) := f (n) + g(n) und (f · g)(n) := f (d)g .
d
d|n
Dabei erstreckt sich die Summe über alle positiven Teiler von n. Das Element
e ∈ I(K) sei durch e(1) = 1 und e(n) = 0 für n > 1 gegeben. Zeigen Sie:
64 1 Zahlen
Übung 1.37. Geben Sie alle Erzeuger der multiplikativen Gruppe F∗17 an
und berechnen Sie die Ordnung jedes Elements dieser Gruppe.
2X 2 − 2X + 5
a
und berechnen Sie die komplexen Zahlen a + b, a · b, a − b und .
b
1.5 Kryptographie
E F G
D H
C
A B C D E
B
Z
I
Y
F
X Y Z A
J
G
U VWX
K L M N
H I J K O
•
T
W
L
S
R M
V
N O
P Q P
Q R S T U
le, mit der man chiffrieren und dechiffrieren kann. Mit dem heutigen Wissen
bietet eine solche Chiffrierung keinerlei Sicherheit mehr. Weitere Verfahren
dieser Art findet man zum Beispiel im Buch von A. Beutelspacher [Beu]. Ein
sehr schönes Beispiel einer Kryptoanalyse eines chiffrierten Textes, bei der die
Buchstaben des Alphabets durch andere Zeichen ersetzt wurden, kann man
in der Kurzgeschichte Der Goldkäfer“ des amerikanischen Autors E.A. Poe
”
(1809–1849) nachlesen.
Die Sicherheit der bisher beschriebenen Verfahren ist nach heutigen Maß-
stäben sehr gering. Ein bekanntes Verfahren, welches perfekte Sicherheit
bietet, geht auf Vigenère16 zurück. Anstelle einer festen Regel benutzt es
für die Ersetzung der Klartextbuchstaben eine zufällige und beliebig lange
Buchstabenfolge, einen sogenannten Buchstabenwurm. Die Sicherheit die-
ses Verfahrens hängt davon ab, dass Sender und Empfänger irgendwann
16 Blaise de Vigenère (1523–1596), französischer Diplomat.
66 1 Zahlen
über einen sicheren Kanal den Schlüssel und damit die Details für den Al-
gorithmus, ausgetauscht haben. Dies kann beispielsweise durch persönliche
Übergabe erfolgen. Für die Anwendung in Computernetzwerken ist dies je-
doch nur unter besonderen Umständen praktikabel. Für den Alltagsgebrauch,
wie zum Beispiel beim online-Buchkauf, benötigt man andere Methoden für
den Schlüsselaustausch.
Moderne Methoden beruhen auf einer bahnbrechenden Idee, die erstmals
1976 von Diffie und Hellman [DH] veröffentlicht wurde. Sie besteht darin,
sogenannte Einwegfunktionen zu benutzen. Das sind Funktionen, die leicht
berechenbar sind, deren inverse Abbildung aber nur für den Besitzer von
Zusatzinformationen leicht zu berechnen ist. Ohne Zusatzinformation ist die
Berechnung des Inversen so aufwändig und langwierig, dass praktisch Sicher-
heit gegeben ist, zumindest für eine begrenzte Zeit.
Beispiele solcher Einwegfunktionen sind das Produkt zweier Primzahlen und
∗
die diskrete Exponentialabbildung Z/ϕ(n)Z → (Z/nZ) , die bei vorgegebener
Basis s durch x 7→ sx definiert ist. Für sehr große ganze Zahlen ist die Be-
rechnung der Inversen – die Faktorisierung in Primzahlen bzw. der diskrete
Logarithmus – sehr zeitaufwändig.
Der Schlüsselaustausch nach Diffie-Hellman geschieht wie folgt: Die Personen
A und B wollen einen Schlüssel in Form eines Elements von Z/pZ vereinba-
ren, ohne dass ein Dritter dies in Erfahrung bringen kann. Dazu wird eine
große Primzahl p und eine ganze Zahl 0 < s < p öffentlich ausgetauscht.
Nun wählt A eine ganze Zahl a ∈ Z und B eine ganze Zahl b ∈ Z, so dass
0 < a, b < p − 1. Diese Information wird von beiden geheim gehalten. Dann
berechnet A den Wert sa mod p in Z/pZ und übermittelt ihn B. Ebenso
sendet B den Wert sb mod p an A. Schließlich berechnen beide den gleichen
Wert (sb )a ≡ sa·b ≡ (sa )b mod p. Auf diese Weise ist beiden Personen (und
keinem Dritten) der gemeinsame Schlüssel sa·b mod p in Z/pZ bekannt.
Zur praktischen Anwendung würde die Online-Buchhandlung eine Primzahl
p, eine ganze Zahl 0 < s < p und sb mod p veröffentlichen. Es ist günstig,
wenn s ein Erzeuger der multiplikativen Gruppe F∗p ist. Die Zahl b bleibt
geheim und ist nur dem Buchhändler bekannt. Für die Sicherheit der Daten
ist die Einweg-Eigenschaft des diskreten Logarithmus entscheidend.
Der Kunde wählt nun zufällig eine Zahl a und berechnet (sb )a mod p in
Z/pZ, das ist der Schlüssel für seine Transaktion. Diesen benutzt er, um mit
Hilfe eines vom Buchhändler bekanntgegebenen Verfahrens seine Daten zu
chiffrieren. In der von Taher ElGamal im Jahre 1985 veröffentlichten Ar-
beit [EG] wurde als Chiffrierverfahren einfach die Multiplikation mit dem
Schlüssel in Z/pZ vorgeschlagen, dies wird heute als ElGamal-Verfahren be-
zeichnet. Die Chiffrierung kann jedoch auch auf jede andere, vorher verein-
barte Art erfolgen. Zusätzlich zum chiffrierten Text übermittelt er auch sa
mod p, woraus der Buchhändler den Schlüssel (sa )b mod p berechnen kann.
Die Vorgehensweise beim RSA-Verfahren ist eine völlig andere. Es beruht
darauf, dass die Produktabbildung {Primzahl} × {Primzahl} → Z eine Ein-
wegfunktion ist. Es ist nach seinen Entdeckern R. Rivest, A. Shamir, L. Adle-
1.5 Kryptographie 67
man [RSA] benannt. Das Grundprinzip ist das Folgende: Zu einer natürlichen
Zahl n wird ein öffentlicher Schlüssel e ∈ Z mit ggT(e, ϕ(n)) = 1 gewählt.
Durch das Lösen der Gleichung [e] · [d] = 1 in Z/ϕ(n)Z wird der geheime
Schlüssel d ∈ Z bestimmt.
Jeder, der das Paar (n, e) kennt, kann eine Nachricht chiffrieren. Dies ge-
schieht, indem eine Kongruenzklasse m ∈ Z/nZ zu me ∈ Z/nZ verschlüsselt
wird. Um dies zu dechiffrieren benutzt man den Satz 1.3.24. Er liefert
(me )d = me·d = m in Z/nZ. Dazu ist die Kenntnis der Zahl d nötig. Daher
muss man d geheim halten, wogegen die Zahlen n und e öffentlich bekannt-
gegeben werden.
Die Sicherheit dieses Verfahrens beruht darauf, dass die Berechnung von d bei
Kenntnis von n und e ohne weitere Zusatzinformationen ein sehr aufwändiges
Problem ist. Die Methoden von Abschnitt 1.2 erlauben uns, den geheimen
Schlüssel d mit Hilfe des Euklidischen Algorithmus zu berechnen. Dazu muss
allerdings auch die Zahl ϕ(n) bekannt sein. Wenn die Faktorisierung von n
in ein Produkt von Primzahlen bekannt ist, dann ist die Berechnung von
ϕ(n) mit Hilfe von Satz 1.3.34 oder Folgerung 1.4.24 sehr leicht. Für große n
(das heißt momentan mit 200 bis 400 Dezimalstellen) ist das Auffinden der
Zerlegung in Primfaktoren ein sehr aufwändiges Problem.
Zur praktischen Durchführung beschafft man sich zunächst zwei verschiedene,
relativ große Primzahlen p und q. Dann berechnet man n = pq und ϕ(n) =
(p − 1)(q − 1). Letzteres ist die Geheiminformation, die man nicht preisgeben
darf und die nach der Berechnung von d nicht mehr benötigt wird.
Vor einigen Jahren galten dabei 100-stellige Primzahlen als hinreichend si-
cher. Man muss allerdings mit der Entwicklung von Technik und Algorithmen
ständig Schritt halten. Heute ist es kein Problem, eine 430-Bit Zahl inner-
halb einiger Monate mit einem einzigen PC zu faktorisieren. Durch die Ent-
wicklung der Hardware und durch die Entdeckung besserer Algorithmen zur
Faktorisierung großer Zahlen wird die Größe der Zahlen, die in erträglicher
Zeit faktorisierbar sind, in naher Zukunft wachsen. Wer Verantwortung für
Datensicherheit übernimmt, sollte sich daher regelmäßig über den aktuellen
Stand der Entwicklung informieren.
Die Firma RSA-Security hatte im Jahre 1991 eine Liste von Zahlen veröffent-
licht, für deren Faktorisierung Preisgelder in unterschiedlicher Höhe ausge-
setzt wurden ( Factoring Challenge“). Im Jahre 2001 wurde diese Liste wegen
”
der rasanten Erfolge durch eine neue ersetzt. Die größte Zahl auf dieser Liste
heißt RSA-2048. Sie hat 2048 Ziffern in Binärdarstellung und 617 Dezimalzif-
fern. Es war ein Preisgeld in Höhe von 200 000 US$ auf ihre Faktorisierung
ausgesetzt. Sämtliche Zahlen dieser Liste sind Produkt zweier Primzahlen.
Die Faktorisierung der 129-stelligen Zahl RSA-129 im April 1994 hatte damals
das öffentliche Interesse auf diese sogenannten RSA-Zahlen gelenkt. Diese
Zahl wurde im Jahre 1977 von R. Rivest, A. Shamir, und L. Adleman zur
Verschlüsselung einer der ersten Nachrichten mit dem RSA-Verfahren be-
nutzt. Zur Zeit der Veröffentlichung der verschlüsselten Nachricht glaubte
man, dass es Millionen von Jahren dauern wird, bis diese Nachricht ent-
68 1 Zahlen
schlüsselt sein wird. Die 1994 gefundene Entschlüsselung lautete: The magic
”
words are squeamish ossifrage“ [Fr].
Die Faktorisierung dieser 129-stelligen Zahl gelang unter anderem durch Par-
allelisierung der Rechnung, einer Idee, der wir bereits in Bemerkung 1.4.26
begegnet sind.
Anfang Dezember 2003 wurde bekanntgegeben, dass eine weitere Zahl aus
der erwähnten Liste faktorisiert wurde. Es handelte sich dabei um RSA-576,
deren Faktorisierung mit 10 000 US$ dotiert war. Die Binärdarstellung dieser
Zahl besitzt 576 Ziffern. In Dezimaldarstellung handelt es sich um die 174-
ziffrige Zahl
1881988129206079638386972394616504398071635633794173827007
6335642298885971523466548531906060650474304531738801130339
6716199692321205734031879550656996221305168759307650257059
Die Faktorisierung wurde von einem von Prof. Jens Franke (Mathemati-
sches Institut der Universität Bonn) geleiteten Team durchgeführt. Diese Zahl
konnte unter Benutzung eines Algorithmus aus der algebraischen Zahlentheo-
rie, den man das Zahlkörpersieb nennt, in zwei Primzahlen mit je 87 Ziffern
zerlegt werden. Dadurch wurde deutlich, dass nunmehr keine Hochleistungs-
rechner mehr nötig sind, um solch eine Aufgabe zu lösen: Die wesentlichen
Rechnungen wurden auf gewöhnlichen PC’s, die in besonderer Weise vernetzt
waren, durchgeführt und dauerten etwa 3 Monate.
Die Bonner Gruppe um J. Franke hat dann im Mai 2005 die Zahl RSA-200
(200 Ziffern im Dezimalsystem, siehe Abb. 1.6) und im November 2005 auch
die 193-ziffrige Zahl RSA-640 faktorisiert. Auf die letztere war ein Preisgeld
von 20 000 US$ ausgesetzt. Obwohl damit noch nicht das Ende der Liste der
Firma RSA-Security erreicht war, wurde der Wettbewerb um die Faktorisie-
rung dieser Zahlen im Frühjahr 2007 für beendet erklärt.
27997833911221327870829467638722601621070446786955
42853756000992932612840010760934567105295536085606
18223519109513657886371059544820065767750985805576
13579098734950144178863178946295187237869221823983
=
35324619344027701212726049781984643686711974001976
25023649303468776121253679423200058547956528088349
×
79258699544783330333470858414800596877379758573642
19960734330341455767872818152135381409304740185467
Die Electronic Frontier Foundation17 hat einen Preis von 100 000 US$ für die-
jenigen ausgesetzt, die eine Primzahl mit mehr als 10 000 000 Ziffern finden.
Solche Zahlen wurden im Sommer 2008 gefunden. Wer eine Primzahl mit min-
destens 108 Ziffern findet, auf den warten nun 150 000 US$. Die größte bisher
gefundene Primzahl hat 12 978 189 Ziffern. Das ist die Zahl 243112609 − 1. Es
handelt sich dabei um eine sogenannte Mersenne-Primzahl18, d.h. eine Prim-
zahl der Form Mn := 2n − 1. Es ist leicht zu sehen, dass 2n − 1 nur Primzahl
sein kann, wenn n selbst eine Primzahl ist. Mersenne behauptete, dass für
n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 die Zahl Mn eine Primzahl ist. Für
M67 und M257 erwies sich das später als falsch. So fand F. Cole19 die Fak-
toren von M67 . Bis heute sind 46 Mersenne-Primzahlen bekannt. Es ist auch
nicht klar, ob es unendlich viele gibt. Die Mersenne-Zahlen kann man verall-
n
gemeinern und Zahlen vom Typ bb−1 −1
betrachten. Diese Zahlen zeichnen sich
dadurch aus, dass sie in der b-adischen Darstellung (vgl. Kapitel 3.4) genau n
Einsen haben. Insbesondere hat 2n − 1 im Dualsystem genau n Einsen. Wenn
n
b = 10 ist, erhält man eine sogenannte Repunit 20 Rn := 10 9−1 . Die Zahl
R1031 wurde im Jahre 1986 von H. Williams und H. Dubner als Primzahl
identifiziert. Sie besteht aus 1031 Ziffern, die alle gleich 1 sind, siehe [WD].
Mancher Leser mag sich fragen, wie man die bisher besprochene Ver-
schlüsselung von Elementen aus Z/nZ auf die Verschlüsselung realer Texte
anwenden kann. Eine mögliche Antwort ist die Folgende.
Der aus Schriftzeichen bestehende Klartext wird zunächst in eine Zahl
umgewandelt. Dazu kann man den ASCII-Code benutzen. ASCII ist eine
Abkürzung für American Standard Code for Information Interchange. Die-
ser Code, der zu Beginn der 1960-er Jahre entwickelt wurde, ordnet jedem
Buchstaben des englischen Alphabets und einigen Sonderzeichen eine 7-Bit
Zahl zu. In der heutigen Zeit stehen normalerweise 8 Bits zur Speicherung
und Verarbeitung von 7-Bit ASCII-Zeichen zur Verfügung. Das zusätzliche
Bit könnte als Paritätsbit zur Fehlererkennung genutzt werden (vgl. Beispiel
2.5.6), es wird jedoch heute meist mit Null belegt.
Auf den ASCII-Code bauen viele andere Codierungen auf, die zur Digitalisie-
rung anderer Zeichen in nicht-englischen Sprachräumen entwickelt wurden.
Das gilt auch für den in den 1990-er Jahren entwickelten Unicode-Standard,
der die Codierungsvielfalt abgelöst hat. Der Unicode-Standard erlaubt die
Codierung tausender Symbole und Schriftzeichen aus verschiedensten Kultu-
ren der Welt.
Die 26 Großbuchstaben entsprechen im ASCII-Code den in Tabelle 1.3 an-
gegebenen Dezimal- bzw. Hexadezimalzahlen. Durch Addition von 32 (bzw.
20 hexadezimal) ergibt sich der Wert des entsprechenden Kleinbuchstabens.
17 [Link]
18 Marin Mersenne (1588–1648), französischer Mathematiker und Theologe.
19 Frank Nelson Cole (1861–1926), US-amerikanischer Mathematiker.
20 aus dem Englischen von repeated unit.
70 1 Zahlen
Buchstabe A B C D E F G H I J K L M
ASCII (dezimal) 65 66 67 68 69 70 71 72 73 74 75 76 77
ASCII (hex) 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D
Buchstabe N O P Q R S T U V W X Y Z
ASCII (dezimal) 78 79 80 81 82 83 84 85 86 87 88 89 90
ASCII (hex) 4E 4F 50 51 52 53 54 55 56 57 58 59 5A
Tabelle 1.3 ASCII-Code für Großbuchstaben
Beispiel 1.5.1. Sei p = 1373 und q = 2281, dann ist n = pq = 3131813 und
ϕ(n) = 3128160. Da 221 = 2097152 < n können wir drei 7-Bit ASCII Sym-
bole am Stück verarbeiten. Zur Chiffrierung der drei Zeichen R S A können
wir deren Hexadezimalwerte 52 53 41 aus Tabelle 1.3 als Folge von 7-Bit
Zahlen schreiben: 1010010 1010011 1000001. Für die Rechnung per Hand
ist es jedoch einfacher mit den Dezimalwerten 82 83 65 zu rechnen. Die obige
21-Bit Zahl hat den Wert 82 ·214 + 83 ·27 + 65 = 1354177. Wird der öffentliche
Schlüssel e = 491 benutzt, dann ist 1354177491 mod 3131813 zu berechnen.
Dies ist kongruent 992993 modulo 3131813. Da 992993 = 60 ·214 + 77 ·27 + 97,
besteht der verschlüsselte Text aus den Zeichen der ASCII-Tabelle mit den
Nummern 60 77 97, das sind: < M a. Wir hatten Glück, dass die Chiffrie-
rung auf druckbare Zeichen geführt hat. Die Zeichen mit den Nummern 0–
31 und 127 in der ASCII-Tabelle sind nicht-druckbare Sonderzeichen, daher
wird man auf dem hier begangenen Weg nicht immer zu einem druckba-
ren verschlüsselten Text gelangen. Das ist kein Mangel, denn allein aus den
Zahlenwerten lässt sich der Originaltext mit Hilfe des geheimen Schlüssels
rekonstruieren. Eine Betrachtung des Textes in verschlüsselter Form ist in
der Regel wenig informativ.
Da wir die Zerlegung von n in Primfaktoren und daher auch ϕ(n) kennen,
können wir Hilfe des Euklidischen Algorithmus den geheimen Schlüssel d =
1.5 Kryptographie 71
6371 bestimmen. Es ist eine nützliche Übung, die Dechiffrierung von < M a
mit dieser Zahl d konkret durchzuführen.
Mit Hilfe des RSA-Verfahrens kann man auch eine sogenannte digitale Unter-
schrift erzeugen. Zu diesem Zweck muss der Absender A der Nachricht einen
öffentlichen Schlüssel bekanntgegeben haben. Wenn (nA , eA ) der öffentliche
Schlüssel und dA der geheime Schlüssel von A sind, dann wird eine un-
verschlüsselte Nachricht m durch Anhängen von mdA mod nA unterschrie-
eA
ben. Jeder kann jetzt durch Berechnung von mdA mod nA feststellen,
ob der angehängte chiffrierte Teil tatsächlich mit dem gesendeten Klartext
übereinstimmt. In der Realität wird nicht die gesamte Nachricht, sondern nur
der Wert einer Hashfunktion chiffriert (vgl. Seite 312).
Wenn auch der Empfänger E einen öffentlichen Schlüssel (nE , eE ) bekanntge-
geben hat, dann kann A ihm eine elektronisch unterschriebene und chiffrierte
Nachricht senden. Dies geschieht, indem zuerst der Klartext wie beschrieben
signiert und anschließend mit dem öffentlichen Schlüssel von E chiffriert wird.
Der Empfänger geht nun umgekehrt vor. Zuerst dechiffriert er die Nachricht
mit Hilfe seines geheimen Schlüssels dE , dann prüft er die Unterschrift durch
Anwendung des öffentlichen Schlüssels von A.
In der modernen Kryptographie werden heute algebraische Strukturen ver-
wendet, die weit über den Rahmen dieses einführenden Kapitels hinausgehen.
Zum Beispiel basiert die Verwendung von elliptischen Kurven auf Methoden
der algebraischen Geometrie. Wer interessiert ist, findet in [Bau], [Beu], [Ko1],
[Ko2], [BSW] und [We] Material unterschiedlichen Schwierigkeitsgrades für
das weitere Studium.
Zum Abschluss dieses Abschnittes möchten wir nochmals die Warnung aus-
sprechen, dass wir uns hier auf die Darlegung der mathematischen Grundide-
en der modernen Kryptographie beschränkt haben. In der angegebenen Form
weisen die beschriebenen Verfahren beträchtliche Sicherheitslücken auf. Um
wirkliche Datensicherheit zu erreichen, ist eine genaue Analyse der bekannten
Angriffe auf die benutzten Kryptosysteme notwendig.
Aufgaben
Übung 1.39. Bestimmen Sie den geheimen Schüssel d für jedes der folgenden
Paare (n, d) von öffentlichen RSA-Schlüsseln:
(i) (493, 45) (ii) (10201, 137) (iii) (13081, 701) (iv) (253723, 1759)
Übung 1.41. Mit dem öffentlichen RSA-Schlüssel (n, e) = (9119, 17) sollen
Nachrichten chiffriert werden. In diesen Texten werden nur solche Zeichen
zugelassen, deren ASCII-Code einen Dezimalwert zwischen 32 und 90 hat.
Der Nachrichtentext wird in Paare von Zeichen zerlegt. Die zweiziffrigen De-
zimaldarstellungen dieser beiden Zeichen werden jeweils zu einer vierstelligen
Dezimalzahl nebeneinandergestellt. Auf diese Weise wird aus dem Buchsta-
benpaar BK die Dezimalzahl m = 6675.
Die Chiffrierung erfolgt nach dem RSA-Verfahren durch die Berechnung von
me mod n. Für m = 6675 erhält man 4492 mod 9119. An den Empfänger
der verschlüsselten Nachricht wird nicht diese Zahl, sondern die entsprechen-
de ASCII-Zeichenkette übermittelt. Im Fall von 4492 finden wir in der ASCII-
Tabelle zu den Dezimalzahlen 44 und 92 die Symbole ,\
Finden Sie den aus 6 Buchstaben bestehenden Klartext, der mit diesem Ver-
fahren zu dem Geheimtext +TT&@/ wurde.
Kapitel 2
Lineare Algebra
Die Begriffe und Verfahren der linearen Algebra gehören zu den wichtigsten
Werkzeugen eines jeden Mathematikers, Naturwissenschaftlers und Informa-
tikers. Ohne Grundkenntnisse aus diesem Gebiet ist es oft nicht möglich,
mathematische Probleme aus anderen Wissensbereichen zu lösen.
Die lineare Algebra beschäftigt sich mit Systemen linearer Gleichungen. Da-
bei geht es auf der einen Seite um Verfahren zur Bestimmung der Lösungen
solcher Gleichungssysteme und auf der anderen Seite um eine Strukturtheorie
dieser Lösungsmengen: die Theorie der Vektorräume und linearen Abbildun-
gen.
Zur Motivation der abstrakten Begriffsbildungen beginnen wir mit der Dar-
stellung des Gaußschen Algorithmus als wichtigstem Verfahren zur Lösung li-
nearer Gleichungssysteme. Eine Analyse der erhaltenen Lösungsmengen führt
dann in natürlicher Weise auf die Begriffe Vektorraum und lineare Abbildung.
Im Hauptteil dieses Kapitels werden die wichtigsten Resultate und Methoden
der linearen Algebra entwickelt. Zum Abschluss sehen wir anhand des Bei-
spiels der Codierungstheorie, wie die zuvor entwickelte Theorie unmittelbare
Anwendung in der Informatik findet.
73
74 2 Lineare Algebra
waren bereits im 17. Jahrhundert bekannt. Die Idee besteht darin, den Punk-
ten unserer Anschauungsräume Paare bzw. Tripel von Zahlen zuzuordnen,
mit denen dann algebraische Operationen ausgeführt werden können.
Zur Erleichterung des Einstiegs beschäftigen wir uns in diesem einführenden
Abschnitt ausschließlich mit reellen Vektorräumen, da diese unserer Anschau-
ung am nächsten liegen. Im Abschnitt 2.5, bei der Beschäftigung mit fehler-
korrigierenden Codes, müssen wir jedoch auch andere Zahlen“ als nur reelle
”
Zahlen zulassen. Dazu zählen insbesondere die im Abschnitt 1.4 eingeführten
endlichen Körper Fp . Daher ist es wichtig, die Theorie in den Abschnitten
2.2 und 2.3 für beliebige Körper zu formulieren.
Unter einem Vektor wollen wir ein Element aus dem Raum
Rn = {(x1 , x2 , . . . , xn ) | xi ∈ R, 1 ≤ i ≤ n}
−4 −3 −2 −1 0 1 2 3 4 5
In unserer Vorstellung sollte diese Gerade jedoch kein Ende besitzen und
alle reellen Zahlen (d.h. alle Punkte), nicht nur die benannten, beinhalten.
Die genaue Bedeutung dieser Aussage wird im Abschnitt 3.1 mathematisch
präzisiert.
Im Fall n = 2 spricht man von der reellen Ebene R2 , siehe Abb. 2.1.
(−1, 3)
b
3
(4, 2)
2 b
−1 1 2 3 4 5
−1 b
(3, −1)
begrenzt. Wir müssen uns dann auf die Algebra einlassen, können aber noch
bedingt auf unsere niederdimensionale Anschauung zurückgreifen.2
Bisher haben wir Paare oder Tripel von Zahlen als Punkt in der Ebene oder im
Raum interpretiert. Die korrekte geometrische Anschauung für ein n-Tupel
reeller Zahlen x = (x1 , . . . , xn ) ∈ Rn im Rahmen der Linearen Algebra ist
jedoch die des Vektors. Man stellt sich einen Vektor als Pfeil vor, der durch
seine Richtung und Länge bestimmt ist. Bei dieser Interpretation ist zu be-
achten, dass nur Richtung und Länge, nicht aber der Anfangspunkt des Pfeils
von Bedeutung sind. Statt eines einzelnen Pfeils gibt es unendlich viele Pfeile,
die den gleichen Vektor darstellen. Jeder der Pfeile in Abb. 2.2 repräsentiert
den Vektor (2, 1) ∈ R2 . Wem diese Erklärung Schwierigkeiten bereitet, der
kann sich einen Vektor auch als Verschiebung der Ebene, bzw. des Raumes
vorstellen. Dies ist in der Tat die beste Interpretation. Der mathematisch in-
teressierte Leser findet den Hintergrund dazu im Kapitel über affine Räume
in [Kow].
−1 1 2 3 4 5
−1
Die Menge der Vektoren erhält eine algebraische Struktur, indem wir die
Addition zweier Vektoren durch
meinen Publikum nahezubringen, wurde bereits im Jahre 1884 von Edwin A. Abbott unter
dem Titel Flatland [Abb] unternommen. Inzwischen gibt es einen auf diesem sozialsatiri-
schen Roman basierenden Animationsfilm, siehe [Link] Auf der
DVD wird auch über Möglichkeiten der Darstellung einer vierten Dimension gesprochen.
76 2 Lineare Algebra
−u
u+v
v
u
u+v 2u u
v
− 12 u
u
u
mehrbändigen Werk sind die damaligen geometrischen Ergebnisse und Anschauungen auf
streng logische Weise dargestellt, vgl. auch Fußnote auf Seite 6.
2.1 Lineare Gleichungssysteme 77
gibt dann die Richtung der Geraden L an, die durch die Punkte x und y
verläuft. Wenn wir alle Punkt der Gestalt x + λw, λ ∈ R betrachten, dann
erhalten wir die gesamte Gerade L (Abb.2.4), d.h.
L = {x + λw | λ ∈ R} ⊂ R2 .
x + λw L
x + 2w
y = x+w
x − 0.8w w
Außer durch eine Parametrisierung lässt sich eine Gerade in der Ebene auch
durch eine lineare Gleichung a1 x1 + a2 x2 = b beschreiben. Bei einer solchen
Beschreibung stimmt die Gerade mit der Lösungsmenge
Lös(a1 , a2 | b) := {(x1 , x2 ) ∈ R2 | a1 x1 + a2 x2 = b}
überein. Die Koeffizienten a1 , a2 und die Zahl b sind dabei als feste, gegebene
Größen zu betrachten.
Unter dem Lösen der Gleichung a1 x1 + a2 x2 = b verstehen wir das Auffinden
einer Parametrisierung f : R → R2 der Lösungsmenge Lös(a1 , a2 | b). Die
Parametrisierung soll die Gestalt f (λ) = v +λw haben, sie ist also vollständig
bekannt, wenn die Vektoren v und w bestimmt sind.
Dies wird nicht in jedem Fall gelingen. Wenn zum Beispiel a1 = a2 = 0 und
b 6= 0 ist, dann gibt es kein (x1 , x2 ) ∈ R2 , welches a1 x1 + a2 x2 = b erfüllt.
Die Lösungsmenge Lös(0, 0| b) = ∅ ist dann leer, vorausgesetzt b 6= 0. Ein
weiteres Beispiel ist die Lösungsmenge Lös(0, 0| 0) = R2 , auch dies ist keine
Gerade. In allen anderen Fällen ist Lös(a1 , a2 | b) eine Gerade. Um dies zu
sehen, nehmen wir zunächst a1 6= 0 an. Unter dieser Voraussetzung erhalten
wir aus der gegebenen Gleichung x1 = ab1 − aa21 · x2 und wir können für x2
jedes beliebige λ ∈ R einsetzen. Es ergibt sich
b a2 b a2
(x1 , x2 ) = − λ, λ = , 0 + λ − , 1 ∈ Lös(a1 , a2 | b) .
a1 a1 a1 a1
78 2 Lineare Algebra
b
Dies ist die gewünschte Parametrisierung f (λ) = v + λw mit v = ,0
a1
a2
und w = − , 1 . Falls a1 = 0 und a2 6= 0, geht alles analog.
a1
Um die geometrische Anschauung weiter zu fördern, erhöhen wir jetzt die
Dimension. Auch im dreidimensionalen Raum R3 ist eine Gerade durch zwei
ihrer Punkte festgelegt und wir können sie durch eine Parametrisierung f :
R → R3 der Gestalt f (λ) := v + λw beschreiben. Hierbei ist w 6= 0 und
v, w ∈ R3 . Jede Menge der Gestalt L = {v + λw | λ ∈ R} ⊂ R3 mit v, w ∈ R3
und w 6= 0 ist eine Gerade.
Zur Beschreibung einer Geraden im R3 reicht es jedoch nicht aus, eine einzige
lineare Gleichung anzugeben. Schauen wir dazu eine lineare Gleichung
a1 x1 + a2 x2 + a3 x3 = b
an, in der a3 6= 0 ist. Dann ergibt sich x3 = ab3 − aa31 x1 − aa32 x2 und wir können
für x1 und x2 beliebige Werte λ1 ∈ R und λ2 ∈ R einsetzen. Wir erhalten
dann (λ1 , λ2 , ab3 − aa31 λ1 − aa23 λ2 ) = (0, 0, ab3 )+λ1 ·(1, 0, − aa31 )+λ2 ·(0, 1, − aa32 ) als
Element in Lös(a1 , a2 , a3 | b) := {(x1 , x2 , x3 ) ∈ R3 | a1 x1 + a2 x2 + a3 x3 = b}.
In diesem Fall gibt es zwei freie Parameter λ1 , λ2 ∈ R in den Lösungen,
die Parametrisierung ist daher eine Abbildung f : R2 → R3 der Gestalt
f (λ1 , λ2 ) = u + λ1 v + λ2 w. Wie zuvor ist f (R2 ) = Lös(a1 , a2 , a3 | b). Die
Lösungsmenge einer linearen Gleichung ist also eine Ebene im R3 . Um eine
Gerade zu beschreiben, benötigen wir zwei lineare Gleichungen, die beide
gleichzeitig zu erfüllen sind. Die Gerade ist dann der Durchschnitt der beiden
Ebenen, die durch diese Gleichungen definiert werden.
Es folgt ein konkretes Beispiel:
2x1 − x2 + x3 = 2 (I)
−x1 − 4x2 + x3 = 2 . (II)
2x1 − x2 + x3 = 2 (I)
x1 + x2 = 0 . (II′ )
Die Ebenen (I), (II′ ) und ihr Durchschnitt L sind in Abb. 2.5 dargestellt.
Da man durch Addition der Gleichung (I) zum (−3)-fachen von (II′ ) die
Gleichung (II) zurückerhält, hat sich beim Übergang von (I) und (II) zu
(I) und (II′ ) die Lösungsmenge nicht verändert. Geometrisch entspricht die
Ersetzung von (II) durch (II′ ) einer Drehung der Ebene (II) um die Achse L,
wie in Abb. 2.6 angedeutet.
2.1 Lineare Gleichungssysteme 79
x3
x2
Ebene I
2x1 − x2 + x3 = 2
x1
Ebene II′
x1 + x2 = 0
Ebene II
−x1 − 4x2 + x3 = 2
Ebene II′
x3 = 2 − 2x1 + x2 = 2 − 3x1 .
x1 + x2 + x3 = 2 (I)
2x1 + 3x2 + x3 = 4 (II)
x1 + 3x2 =3 (III)
Wie zuvor bilden wir Gleichungen (II′ ) = (II) − 2 · (I) und (III′ ) = (III) − (I)
x1 + x2 + x3 = 2 (I)
x2 − x3 = 0 (II′ )
2x2 − x3 = 1 (III′ )
Nun eliminieren wir x2 aus der Gleichung (III′ ), indem wir (III′′ ) = (III′ ) −
2(II′ ) bilden:
x1 + x2 + x3 = 2 (I)
x2 − x3 = 0 (II′ )
x3 = 1 (III′′ )
Indem wir von unten nach oben einsetzen, erhalten wir x2 = x3 = 1 und
x1 = 2 − x2 − x3 = 0. Damit hat das gegebene lineare Gleichungssystem
genau eine Lösung, nämlich (x1 , x2 , x3 ) = (0, 1, 1).
Die Lösungsmenge eines Systems mit drei Gleichungen und drei Variablen
kann leer, oder ein einzelner Punkt, eine Gerade, eine Ebene oder gar der
gesamte R3 sein.
Um auch bei einer größeren Zahl von Variablen oder Gleichungen eine
übersichtliche Beschreibung zu ermöglichen, hat es sich eingebürgert, die Ko-
2.1 Lineare Gleichungssysteme 81
wenn wir die rechten Seiten der Gleichungen noch hinzufügen, um die erwei-
terte Koeffizientenmatrix zu erhalten.
Eine Matrix mit m Zeilen und n Spalten nennt man auch m × n-Matrix. Um
das Gleichungssystem (2.1) platzsparend notieren zu können, vereinbaren
wir, die Koeffizienten bi und die Unbestimmten xj jeweils als Spaltenvektor
zu schreiben ! !
b1 x1
b := .. und x := .. .
. .
bm xn
Das Produkt einer Matrix A = (aij )i,j mit einem Spaltenvektor, dessen Länge
gleich der Zahl der Spalten der Matrix ist, ist durch folgende Formel definiert:
82 2 Lineare Algebra
a11 x1 + a12 x2 + . . . + a1n xn
a21 x1 + a22 x2 + . . . + a2n xn
A · x := . .. .. .
.. . .
am1 x1 + am2 x2 + . . . + amn xn
Das Ergebnis ist ein Vektor, der soviel Einträge hat, wie die Matrix A Zeilen
besitzt. Zur Bestimmung der i-ten Komponente dieses Vektors genügt es, die
i-te ZeilePder Matrix A und den Vektor x zu kennen, denn sie ist gleich der
n
Summe j=1 aij xj . Unter Benutzung dieses Produktes ist A · x = b eine
Abkürzung für das System (2.1) und dessen Lösungsmenge wird mit
Lös(A| b) := {x ∈ Rn | A · x = b}
j1 j2 j3 ....... jr n
⋆ 1
⋆ 2
⋆ 3
.. ..
. .
Hier alles gleich 0 ⋆ r
neten Stellen eine von Null verschiedene reelle Zahl und der untere Bereich
ist völlig mit Nullen ausgefüllt.
Etwas formaler – und somit genauer – heißt dies, dass A = (aij )i,j genau
dann Zeilenstufenform besitzt, wenn die folgenden Bedingungen erfüllt sind:
(i) Es gibt eine ganze Zahl r mit 0 ≤ r ≤ m, so dass die Zeilen mit Nummer
i > r nur Nullen enthalten.
2.1 Lineare Gleichungssysteme 83
1 2 3 ....... r n
⋆ 1
⋆ 2
⋆ 3
.. ..
. .
⋆ r
Sei nun A = (aij )i,j eine Matrix vom Rang r in spezieller Zeilenstufenform.
Wenn es ein j > r gibt mit bj 6= 0, dann hat A · x = b offenbar keine Lösung,
d.h. Lös(A| b) = ∅. Für die Existenz einer Lösung des linearen Gleichungs-
systems A · x = b ist somit
notwendig. Diese Bedingung ist auch hinreichend, denn wenn sie erfüllt ist,
können wir die Variablen xr+1 , . . . , xn mit beliebigen Werten λ1 , λ2 , . . . , λn−r
belegen. Man nennt sie daher freie Variablen. Durch sukzessives Einsetzen
von unten nach oben erhält man aus den Gleichungen dann die Werte der
gebundenen Variablen x1 , . . . , xr . Dazu startet man mit der letzten nichttri-
vialen Gleichung ar,r xr + ar,r+1 xr+1 + . . . + ar,n xn = br . Nach Einsetzen der
λi ergibt sich daraus der Wert von xr
84 2 Lineare Algebra
br 1
xr = − · (ar,r+1 λ1 + . . . + ar,n λn−r )
arr arr
n−r
br 1 X
= − · ar,r+k λk .
arr arr
k=1
Wenn bereits xj+1 , . . . , xr berechnet wurden, dann ergibt sich aus der j-ten
Gleichung
1
xj = (bj − aj,j+1 xj+1 − . . . − aj,n xn ) .
ajj
Nach Einsetzen der bereits berechneten Werte enthält der Ausdruck auf der
rechten Seite keine Unbekannten mehr, sondern nur die gegebenen Koeffizi-
enten und die Parameter λk .
In dem wichtigen Spezialfall r = n gibt es keine freien Variablen. Wenn die
Lösbarkeitsbedingung (2.2) erfüllt ist, dann gibt es genau eine Lösung für
das lineare Gleichungssystem Ax = b.
Wenn sogar r = n = m, dann ist jede Zeilenstufenform auch eine spezielle
Zeilenstufenform und die Lösbarkeitsbedingung ist stets erfüllt. Das Glei-
chungssystem besitzt dann genau eine Lösung.
Wenn r = n und b = 0, dann ist die Lösbarkeitsbedingung ebenfalls erfüllt
und x = 0 ist die eindeutig bestimmte Lösung von Ax = b.
Wenn allgemeiner A eine Matrix in (nicht spezieller) Zeilenstufenform ist,
dann sind lediglich die Formeln für die gebundenen Variablen anzupassen,
alles andere bleibt unverändert richtig.
Beispiel 2.1.2.
02 0 −1 −2 0 3 13
0 0 1 2 3 6 0 7
(A | b) =
0 0 0 0 0 3 1 3
00 0 0 0 00 0
Die freien Variablen sind hier x1 = λ1 , x4 = λ2 , x5 = λ3 und x7 = λ4 . Die
dritte Gleichung ergibt 3x6 = 3 − λ4 . Daraus erhalten wir x6 = 1 − 13 λ4 . Aus
der zweiten Gleichung ergibt sich x3 = 7−2x2 −3x5 −6x6 = 1−2λ2 −3λ3 +2λ4
und aus der ersten x2 = 13 1 3
2 + 2 λ2 + λ3 − 2 λ4 . Der Lösungsvektor x hat somit
die Gestalt
λ1
0 0
13 1 3
0 1 0
+ λ 2 +λ3 − λ4 13 1
1 −3
1−2λ
2 2 2
2 −3λ3 +2λ4
2 0 2
−2 22
1 0 −3
λ2 = 0 +λ1 0 +λ2
10 +λ3 01 +λ4 00
λ3 0 0
0
1− 31 λ4 1 0 0 1
−3
0 0 0 0
λ4 1
Die Idee für den allgemeinen Fall, wenn die Matrix nicht in Zeilenstufenform
gegeben ist, besteht darin, die gegebene Matrix A schrittweise in Zeilenstu-
2.1 Lineare Gleichungssysteme 85
Satz 2.1.3 Wenn A e eb aus (A| b) durch endlich viele elementare Zeilen-
e eb .
umformungen hervorgeht, dann ist Lös (A| b) = Lös A
Beweis. Mittels vollständiger Induktion über die Anzahl der elementaren Zei-
lenumformungen können wir das Problem darauf reduzieren, den Satz für
den Fall einer einzigen elementaren Zeilenumformung zu beweisen. Da die
Lösungsmenge durch die Reihenfolge der Gleichungen nicht beeinflusst wird,
ändert sich durch eine Zeilenvertauschung nichts. Bei einer Umformung vom
Typ (Z2) bleiben alle Zeilen außer der i-ten Zeile unverändert. Daher genügt
es zu zeigen, dass die Lösungsmenge des aus zwei Gleichungen bestehenden
Systems
ai1 x1 + ai2 x2 + . . . + ain xn = bi
(2.3)
ak1 x1 + ak2 x2 + . . . + akn xn = bk
mit der Lösungsmenge des Systems
(ai1 + λak1 )x1 + (ai2 + λak2 )x2 + . . . + (ain + λakn )xn = bi + λbk
(2.4)
ak1 x1 + ak2 x2 + . . . + akn xn = bk
übereinstimmt. Man erhält (2.4), wenn man zur ersten Gleichung von (2.3)
das λ-fache der zweiten Gleichung hinzufügt. Daher ist jede Lösung von (2.3)
auch Lösung von (2.4). Umgekehrt entsteht das System (2.3) dadurch, dass
man zur ersten Gleichung von (2.4) das (−λ)-fache der zweiten Gleichung
addiert, also ist jede Lösung von (2.4) auch Lösung von (2.3). ⊓
⊔
4 Carl Friedrich Gauß (1777–1855), deutscher Mathematiker.
Das Gaußsche Eliminationsverfahren findet man in einem alten Chinesischen Mathemati-
klehrbuch, welches vermutlich bereits 200 v.u.Z. vorlag. Das Verfahren wurde von Gauß
in seinem Studium der Bahn des Asteroiden Pallas verwendet. Seine zwischen 1803 und
1809 gemachten Beobachtungen führten ihn auf ein System von sechs linearen Gleichungen
mit ebenso vielen Unbekannten, welches er mit dem beschriebenen Eliminationsverfahren
systematisch löste.
86 2 Lineare Algebra
Der Nutzen von Satz 2.1.3 wird durch den folgenden Satz offensichtlich, des-
sen Beweis uns überdies einen Algorithmus zur Konstruktion einer Para-
metrisierung der Lösungsmenge eines beliebigen linearen Gleichungssystems
liefert.
Satz 2.1.4 Jede Matrix A lässt sich durch endlich viele elementare Zeilen-
umformungen in Zeilenstufenform bringen.
Beweis. Wenn A = 0 die Nullmatrix ist, dann ist nichts zu zeigen. Sei also
A 6= 0. Wir nehmen an, dass A eine m × n-Matrix ist und führen den Beweis
per Induktion über n ≥ 1, die Zahl der Spalten. Wenn n = 1 ist, können
wir durch Permutation der Zeilen erreichen, dass der oberste Eintrag a11
ai1
nicht gleich 0 ist. Wenn wir dann für jedes 2 ≤ i ≤ m das − a11 -fache
dieser ersten Zeile zur Zeile i addieren, dann erhalten wir die gewünschte
Zeilenstufenform. Das beweist den Induktionsanfang.
Für den Induktionsschritt nehmen wir an, dass die Behauptung des Satzes
bereits für Matrizen mit bis zu n−1 Spalten bewiesen ist. Sei nun j die kleins-
te Nummer einer nichttrivialen Spalte von A, also einer Spalte die nicht nur
Nullen enthält. Da wir A 6= 0 angenommen haben, gibt es ein solches j mit
1 ≤ j ≤ n. In dieser Spalte gibt es einen Eintrag aij 6= 0. Wenn es mehrere
gibt, wählen wir eines davon aus. Man nennt es das Pivotelement . Für die
numerische Stabilität des Verfahrens ist die Auswahl des betragsgrößten Ein-
trags als Pivotelement am günstigsten. Durch Vertauschung derZeilen 1 und
a
i erreichen wir a1j 6= 0. Nun addieren wir für jedes k > 1 das − akj 1j
-fache
der ersten Zeile zur k-ten Zeile. Wir erhalten dadurch eine Matrix der Gestalt
0 . . . 0 a1j . . . . . . . .
0 ... 0 0
.. .. .. .
. . . B
0 ... 0 0
Da die Zahl der Spalten von B gleich n − j < n ist, können wir nach Induk-
tionsvoraussetzung die Matrix B durch endlich viele elementare Zeilenopera-
tionen in Zeilenstufenform bringen. Da in den Zeilen 2 bis m links von B in
der großen Matrix nur Nullen auftreten, ändert sich nichts an der Struktur
von A außerhalb des Bereiches von B, wenn elementare Zeilenumformungen
auf die Zeilen 2 bis m angewendet werden. Das ergibt dann insgesamt eine
Zeilenstufenform für die gesamte Matrix, womit der Satz bewiesen ist. ⊓
⊔
Damit erhalten wir folgende Beschreibung des Gaußschen Algorithmus:
(G1) Erweiterte Koeffizientenmatrix (A| b) aufschreiben.
(G2) Erzeugung einer Zeilenstufenform für A, wie im Beweis von Satz 2.1.4.
Die elementaren Zeilenoperationen werden auf (A| b) angewendet, es
wird jedoch kein Pivotelement in der Spalte b gesucht.
2.1 Lineare Gleichungssysteme 87
(G2) Das Pivotelement wurde bereits gekennzeichnet, es ist der Eintrag a11 .
Nun führen wir zwei elementare Zeilenumformungen vom Typ (Z2) durch,
nämlich (Zeile II)−3·(Zeile I) und (Zeile III)−(Zeile I). Dabei wird immer die
zuerst genannte Zeile durch das erhaltene Ergebnis ersetzt. Es ergibt sich
1 2 1 −1
0 −2 1 −1 .
0 −2 1 −1
Das neue Pivotelement ist wieder gekennzeichnet. Durch die elementare Zei-
lenoperation (Zeile III)−(Zeile II) erhalten wir Zeilenstufenform:
1 2 1 −1
0 −2 1 −1 .
0 0 0 0
(G3) Jetzt könnte man in der zuvor beschriebenen Weise vorgehen. Statt
dessen werden wir mit Hilfe von elementaren Zeilenumformungen auch noch
oberhalb der Pivotelemente Nullen erzeugen. Danach ist das Ablesen der
Lösungen wesentlich weniger aufwändig. In unserem Beispiel ist dazu nur
noch die elementare Zeilenoperation (Zeile I)+(Zeile II) durchzuführen. Das
ergibt:
1 0 2 −2
0 −2 1 −1 .
0 0 0 0
Die Lösbarkeitsbedingung (2.2) ist erfüllt. Die einzige freie Variable ist x3 , sie
wird durch den Parameter λ ersetzt. Aus der ersten Gleichung erhalten wir
x1 = −2 − 2x3 = −2 − 2λ und aus der zweiten Gleichung −2x2 = −1 − x3 =
−1 − λ. Das liefert schließlich die folgende Lösung des Gleichungssystems,
wobei λ ∈ R beliebig ist:
x1 −2 − 2λ −2 −2
x2 = 1/2 + λ/2 = 1/2 + λ · 1/2 .
x3 λ 0 1
88 2 Lineare Algebra
Nachdem wir nun ein Verfahren kennengelernt haben, welches uns zu jedem
linearen Gleichungssystem A · x = b eine Parametrisierung f : Rr → Rn der
Lösungsmenge Lös(A| b) ⊂ Rn liefert, kehren wir nochmals zur analytischen
Geometrie zurück.
Wenn dim U = 0, dann besteht U nur aus einem Punkt. Wenn dim U = 1,
dann heißt U Gerade, und falls dim U = 2, so nennt man U eine Ebene. Dies
stimmt mit der zu Beginn des Kapitels eingeführten Begriffsbildung im Fall
r = 2 und r = 3 überein.
Mit Hilfe des Gaußschen Algorithmus sehen wir, dass die Lösungsmenge
Lös(A| b) ⊂ Rn jedes linearen Gleichungssystems A · x = b ein affiner Raum
ist. Die Zahl r, also die Anzahl der von 0 verschiedenen Zeilen in der Zei-
lenstufenform von A, hat die geometrische Bedeutung n − r = dim Lös(A| b),
denn n − r ist gerade die Anzahl der freien Variablen. Um zu sehen, dass
diese Definition der Dimension korrekt ist, zeigen wir später, wenn etwas
mehr von der allgemeinen Theorie entwickelt wurde, dass jede beliebige Zei-
lenstufenform, die wir mit endlich vielen elementaren Zeilenoperationen aus
A erhalten, denselben Rang r besitzt.
In vielen Bereichen der Mathematik, vor allem in der Algebra einschließlich
der linearen Algebra, erzielt man wesentliche Fortschritte und tiefe Einsichten
durch das strukturelle Studium der Untersuchungsgegenstände. Das gilt auch
für das Studium der Lösungsmenge Lös(A| b) eines linearen Gleichungssys-
tems Ax = b. Die folgenden drei Beobachtungen dienen als Grundlage für die
im nächsten Abschnitt durchgeführte Abstraktion – sie sollen den Übergang
dorthin vorbereiten.
Beobachtung 1: Wenn u, v ∈ Lös(A| b), dann u − v ∈ Lös(A| 0), s. Abb. 2.9.
x2
u−v
Lös(A| b)
u
v
x3
Lös(A| 0)
u−v
x1
Die affinen Unterräume der Gestalt Lös(A| 0) ⊂ Rn sind genau die, welche
den Nullvektor 0 enthalten. Diese nennt man auch lineare Unterräume des
Rn . Da man die Addition eines Vektors auch als Parallelverschiebung inter-
pretieren kann, besagt diese Beobachtung, dass alle affinen Unterräume durch
Parallelverschiebung aus linearen Unterräumen hervorgehen.
x2
Lös(A| b′ ) = u′ + Lös(A| 0)
Lös(A| b) = u + Lös(A| 0)
x3
u′
Lös(A| 0)
x1
Dies ist in gewissem Sinne die Umkehrung der Beobachtung 1, denn aus dieser
erhalten wir die Inklusion Lös(A| b) ⊂ u+Lös(A| 0). Um auch die umgekehrte
Inklusion und damit die behauptete Gleichheit einzusehen, betrachten wir
u ∈ Lös(A| b) und v ∈ Lös(A| 0). Dann ist Au = b und Av = 0 und durch
Addition ergibt sich A(u + v) = b, wie gewünscht.
Beobachtung 3: Für u, v ∈ Lös(A| 0) und λ ∈ R gilt, siehe Abb. 2.11,
2.1 Lineare Gleichungssysteme 91
x2
x3
u
−v
2 u+v
x1
v
Lös (A| 0)
Wer bereits das Kapitel 1 studiert hat, mag sich beim Lesen dieses Abschnit-
tes gefragt haben, ob es möglich wäre, den Gaußschen Algorithmus durch-
92 2 Lineare Algebra
zuführen, wenn wir die reellen Zahlen R durch eine der im Kapitel 1 studierten
algebraischen Strukturen ersetzen würden.
Da in einer linearen Gleichung Ausdrücke der Gestalt aij · xj summiert wer-
den, benötigen wir zwei Verknüpfungsoperationen, um lineare Gleichungs-
systeme überhaupt formulieren zu können. Unter den in Kapitel 1 studierten
algebraischen Strukturen waren Ringe und Körper mit zwei Verknüpfungen
ausgestattet. Da jeder Körper auch Ring ist, gehen wir zunächst der Frage
nach, wie weit wir alles in diesem Abschnitt Gesagte wiederholen können,
wenn die reellen Zahlen R durch einen beliebigen Ring R ersetzt werden.
Unter dieser Annahme kann man lineare Gleichungssysteme weiterhin mit
Hilfe von Matrizen in der Gestalt A · x = b beschreiben. Die Einträge aij
der Matrix A und die Komponenten bi des Vektors b sind dann Elemente des
Ringes R. Die beiden elementaren Zeilenoperationen (Z1) und (Z2) lassen
sich für einen beliebigen Ring R formulieren. Der Beweis, dass sich Lös(A| b)
unter (Z1) und (Z2) nicht ändert, bleibt richtig.
Die erste Stelle, an der wir nicht weiterkommen, befindet sich im Beweis
von Satz 2.1.4. Dort mussten wir durch das Pivotelement teilen, um die
nötigen Nullen zu erzeugen. Das ist in allgemeinen Ringen jedoch nicht im-
mer möglich. Das gleiche Problem hindert uns daran, aus einer Zeilenstufen-
form eine Parametrisierung der Lösung hinzuschreiben. Um alles unverändert
übernehmen zu können, müssen wir durch beliebige, von Null verschiedene
Elemente des Ringes R dividieren können. Dies ist genau dann der Fall,
wenn der Koeffizientenbereich ein Körper ist. Wenn wir an einer Parame-
trisierung von Lös(A| b) interessiert sind, dann sollten die Koeffizienten aus
einem Körper K sein. Alles was in diesem Abschnitt gesagt wurde, bleibt
dann richtig.
Aufgaben
x2 + 2x3 + 3x4 = 4
x1 + 2x2 + 3x3 + 4x4 = 5
2x1 + 3x2 + 4x3 + 5x4 = 6
3x1 + 4x2 + 5x3 + 6x4 = 7
x1 + x2 = 10
x1 + x2 + x3 = 17
x2 + x3 + x4 = 20
x3 + x4 = 12
2.2 Vektorräume und lineare Abbildungen 93
Übung 2.3. Ermitteln Sie alle t ∈ R, für die das durch die folgende erwei-
terte Koeffizientenmatrix gegebene lineare Gleichungssystem lösbar ist und
bestimmen Sie im Fall der Lösbarkeit die Lösungsmenge:
2 4 2 12t
2 12 7 12t + 7
1 10 6 7t + 8
Übung 2.4. Zeichnen Sie in der reellen Ebene R2 mit den Koordinaten x1 , x2
für jede der folgenden Gleichungen die Lösungsmenge.
(I) 3x2 = 6.
(II) 2x1 = 6.
(III) 2x1 + 4x2 = b für zwei verschiedene Werte von b ∈ R.
(IV) Die durch II − a · I“ definierte Menge für zwei verschiedene Werte
”
a ∈ R mit a 6= 1, a 6= 0.
Übung 2.5. In dieser Aufgabe sind alle Zahlen als Elemente des Körpers F2
zu interpretieren, insbesondere auch xi ∈ F2 . Lösen Sie das folgende lineare
Gleichungssystem und geben Sie eine vollständige Liste aller Lösungen (ohne
Benutzung von Parametern) an.
x3 + x4 =0
x1 + x2 + x3 + x4 + x5 + x6 =0
x2 + x3 + x5 =1
x1 + x3 + x6 =1
x2 + x4 + x5 =1
x1 + x6 =1
x + 2y ≡4 mod 7
x+ y + z ≡4 mod 7
3y + 2z ≡ 6 mod 7
aus einem beliebigen Körper zur Multiplikation mit Vektoren zulassen. Zur
Formulierung der allgemeinen Theorie fixieren wir einen Körper K. Als kon-
kretes Beispiel können wir dafür die im Kapitel 1 studierten Körper Q, R, C,
und Fp einsetzen.
(λµ) · v = λ · (µ · v) (2.6)
(λ + µ) · v = λ · v + µ · v (2.7)
λ · (v + w) = λ · v + λ · w (2.8)
1·v = v . (2.9)
Das neutrale Element 0 der additiven abelschen Gruppe (V, +) nennt man
den Nullvektor. Das additive Inverse eines Vektors v ∈ V wird wie üblich mit
−v bezeichnet. Dieser Vektor ist durch die Gleichung v + (−v) = 0 festge-
legt. Unter ausschließlicher Benutzung der in Definition 2.2.1 aufgeführten
Eigenschaften können wir
(−1) · v = −v
zeigen. Dazu nutzen wir zunächst (2.5) und (2.7), um zu erkennen, dass
0 · v = (0 + 0) · v = 0 · v + 0 · v
gilt. Mit Hilfe von (2.5) ergibt sich daraus 0 · v = 0. Daher ist
Wegen der Eindeutigkeit des additiven Inversen folgt daraus die gewünschte
Gleichung (−1) · v = −v. Auf ähnliche Weise erhält man λ · 0 = 0 für alle
λ ∈ K. So kann man auch zeigen, dass nur dann λ · v = 0 gelten kann, wenn
λ = 0 oder v = 0.
2.2 Vektorräume und lineare Abbildungen 95
Wenn U ⊂ V ein Unterraum ist, dann ist U mit der von V geerbten Addition
und skalaren Multiplikation ein K-Vektorraum.
Beispiel 2.2.3. (i) Für jede ganze Zahl n ≥ 1 ist die Menge der n-Tupel
K n := {(x1 , . . . , xn ) | xi ∈ K} ein K-Vektorraum, wenn wir die Additi-
on und skalare Multiplikation durch die folgenden Formeln definieren:
schreiben und B = (bij ) von derselben Größe wie A ist, dann ist die
Summe A + B = (aij + bij ) und das skalare Vielfache λ · A = (λaij ).
Die Bezeichnung ist immer so gewählt, dass aij in Zeile i und Spalte j
steht.
(v) Wenn K = R und A ∈ Mat(m × n, R), dann ist Lös(A| 0) ⊂ Rn ein
Unterraum des R-Vektorraumes Rn .
Für 0 6= b ∈ Rm ist jedoch Lös(A| b) ⊂ Rn kein Untervektorraum, zum
Beispiel weil dann 0 6∈ Lös(A| b).
(vi) Die Menge I := {f ∈ K[X] | f (1) = 0} ⊂ K[X] ist ein Untervektor-
raum. Allgemeiner gilt, dass jedes Ideal in K[X] ein Unterraum ist.
96 2 Lineare Algebra
(vii) Die Menge K[X]≤d ⊂ K[X] aller Polynome, deren Grad höchstens gleich
d ist, ist ein K-Unterraum.
Definition 2.2.4. Ein Vektor v ∈ V in einem K-Vektorraum V heißt Line-
arkombination der Vektoren v1 , v2 , . . . , vr ∈ V , wenn es λ1 , . . . , λr ∈ K gibt,
so dass
X r
v= λi vi
i=1
Pr
gilt. Die Menge Lin(v1 , . . . , vr ) := { i=1 λi vi | λi ∈ K} aller Linearkombina-
tionen der Vektoren v1 , . . . , vr heißt lineare Hülle dieser Menge von Vektoren.
Bemerkung 2.2.5. Die Menge Lin(v1 , . . . , vr ) ⊂ V ist der kleinste Unter-
raum, der die Vektoren v1 , . . . , vr enthält, denn für jeden Unterraum W ⊂ V ,
der v1 , v2 , . . . , vr enthält, ist nach Definition 2.2.2 sicher Lin(v1 , . . . , vr ) ⊂ W .
Dass Lin(v1 , . . . , vr ) ⊂ V selbst ein Unterraum ist, folgt ebenso leicht aus De-
finition 2.2.2. Diese Eigenschaft rechtfertigt, dass man Lin(∅) := {0} setzt.
Beispiel 2.2.6. (i) Sei ei = (0, . . . , 0, 1, 0, . . . , 0) ∈ K n der Vektor mit ei-
ner 1 an der Stelle i und Nullen an allen anderen Pn Stellen. Dann ist
Lin(e1 , e2 , . . . , en ) = K n , denn (x1 , . . . , xn ) = i=1 xi ei .
(ii) Für den R-Vektorraum C gilt Lin(1) = R ⊂ C und Lin(1, i) = C, denn
jede komplexe Zahl hat die Form a + bi = a · 1 + b · i, wobei a, b ∈ R.
Wenn wir C als C-Vektorraum auffassen, dann gilt jedoch Lin(1) = C.
Daher wäre es angebracht, hier LinC (1) = C und zuvor LinR (1) = R ⊂ C
zu schreiben. Wenn derartige Verwechslungsmöglichkeiten bestehen, dann
werden wir LinK (v1 , . . . , vr ) statt Lin(v1 , . . . , vr ) schreiben.
Im Abschnitt 2.1 hat sich gezeigt, dass man Lösungsmengen linearer Glei-
chungssysteme sehr bequem mit Hilfe von Linearkombinationen von Vektoren
beschreiben kann. Das legt nahe, im Kontext dieses Abschnittes ganz allge-
mein der Frage nachzugehen, wann jeder Vektor eines Vektorraumes V als
Linearkombination gegebener Vektoren v1 , . . . , vr dargestellt werden kann,
und wann eine solche Darstellung eindeutig ist. Dazu sind die folgenden Be-
griffsbildungen nützlich.
Definition 2.2.7. Sei V ein K-Vektorraum und v1 , . . . , vr ∈ V Vektoren,
die nicht notwendigerweise paarweise verschieden sind. Die aus r Vektoren
bestehende Liste (v1 , . . . , vr ) heißt:
der Nullvektor nur mit λ1 = λ2 = · · · = λr = 0
(1) linear unabhängig, fallsP
r
als Linearkombination i=1 λi vi dargestellt werden kann. Mit anderen
Worten:
r
X
∀ λ1 , . . . , λr ∈ K : λi vi = 0 =⇒ λ1 = λ2 = · · · = λr = 0 .
i=1
Bemerkung 2.2.8. Wir sprechen in Definition 2.2.7 von einer Liste von Vek-
toren und nicht von einer Menge, um hervorzuheben, dass zum Beispiel die
Listen (v) und (v, v) voneinander verschieden sind. Wenn v 6= 0, dann ist
die erste linear unabhängig, die zweite jedoch nicht. Es wäre falsch von einer
Menge statt einer Liste von Vektoren zu sprechen, denn {v} = {v, v} und so-
mit wäre der Unterschied zwischen den Listen (v) und (v, v) verschwunden.
Bei der Definition des Begriffes Erzeugendensystem spielt diese Unterschei-
dung jedoch keine Rolle. Außerdem beeinflusst eine Permutation der Elemen-
te in einer Liste nicht die Eigenschaft, linear unabhängig zu sein. Schließlich
wird die Definition dadurch ergänzt, dass wir auch die leere Liste als linear
unabhängig betrachten.
Definition 2.2.9. Eine Liste (v1 , . . . , vr ) von Vektoren aus V heißt Basis des
K-Vektorraumes V , falls es sich um ein linear unabhängiges Erzeugendensys-
tem von V handelt.
Beispiel 2.2.10. (i) Falls v ∈ V , dann ist die einelementige Liste (v) genau
dann linear unabhängig, wenn v 6= 0 gilt.
(ii) Sobald in einer Liste (v1 , . . . , vr ) ein Element vi = 0 ist, ist sie linear
abhängig. Das gleiche gilt, wenn für ein Paar von verschiedenen Indizes
i 6= j die entsprechenden Vektoren vi = vj gleich sind.
(iii) (e1 , . . . , en ) ist Basis von K n .
(iv) (1, x, x2 , . . . , xd ) ist Basis von K[X]≤d .
(v) (1, i) ist Basis von C als R-Vektorraum.
(vi) Für jeden Körper K, betrachtet als K-Vektorraum, ist (1) eine Basis.
Das ist Beispiel (iii) für n = 1.
Wir nennen eine linear unabhängige Liste von Vektoren (v1 , . . . , vr ) nicht ver-
längerbar oder maximal, falls für jeden Vektor v ∈ V die Liste (v1 , . . . , vr , v)
linear abhängig ist. Ein Erzeugendensystem (v1 , . . . , vr ) wollen wir un-
verkürzbar oder minimal nennen, wenn nach Weglassen eines der Vektoren
vi aus dieser Liste kein Erzeugendensystem mehr vorliegt.
98 2 Lineare Algebra
Satz 2.2.11 Sei V ein K-Vektorraum und (v1 , . . . , vr ) eine Liste von Vek-
toren aus V . Folgende Aussagen sind äquivalent:
(a) (v1 , . . . , vr ) ist Basis von V ,
(b) (v1 , . . . , vr ) ist eine nicht verlängerbare linear unabhängige Liste,
(c) (v1 , . . . , vr ) ist ein unverkürzbares Erzeugendensystem.
Beweis. Wir beweisen die Implikationen (a) ⇒ (b) ⇒ (c) ⇒ (a), woraus
dann schließlich die Äquivalenz der drei Aussagen folgt. Dieser bequemen
Beweismethode werden wir noch mehrmals begegnen.
(a) ⇒ (b): Sei (v1 , . . . , vr ) eine Basis von V . Dann ist diese Liste auch linear
unabhängig und wir müssen nur noch zeigen, dass sie nicht verlängerbar ist.
Sei dazuP v ∈ V beliebig. Da die gegebene Liste eine Basis ist, gibt es λi ∈ K
r
mit v = i=1 λi vi und das liefert 0 = (−1) · v + λ1 v1 + · · · + λr vr . Somit ist
(v1 , . . . , vr , v) linear abhängig, was zu beweisen war.
(b) ⇒ (c): Sei (v1 , . . . , vr ) eine linear unabhängige Liste, die nicht verlänger-
bar ist. Das heißt, dass für jedes v ∈ V Skalare λi ∈ K und λ ∈ K mit
λv + λ1 v1 + · · · + λr vr = 0 existieren, die nicht sämtlich gleich 0 sind. Wäre
λ = 0, so müssten auch alle λi = 0 sein, da (v1 , . . . , vr ) linear unabhängig ist.
Daher ist λ 6= 0 und v = − λλ1 v1 − . . . − λλr vr . Also ist (v1 , . . . , vr ) ein Erzeu-
gendensystem. Wäre es verkürzbar, so könnte man einen der Vektoren vi als
Linearkombination der restlichen darstellen, was der linearen Unabhängigkeit
von (v1 , . . . , vr ) widerspräche. Das zeigt, dass (v1 , . . . , vr ) ein unverkürzbares
Erzeugendensystem ist.
(c) ⇒ (a): Sei (v1 , . . . , vr ) ein unverkürzbares Erzeugendensystem. Wäre die-
se Liste linear abhängig, so gäbe es λi ∈ K, die nicht sämtlich 0 sind, mit
P r
i=1 λi vi = 0. Nach geeigneter Umnummerierung können wir annehmen,
dass λr 6= 0 ist. Dann wäre vr = − λλ1r v1 − . . . − λλr−1 r
vr−1 , woraus sich
ergäbe, dass bereits (v1 , . . . , vr−1 ) ein Erzeugendensystem ist. Dies wider-
spräche jedoch der angenommenen Unverkürzbarkeit des Erzeugendensys-
tems (v1 , . . . , vr ). Somit ist (v1 , . . . , vr ) linear unabhängig, also eine Basis.
⊓
⊔
Der Begriff der Basis eines Vektorraumes ist das entscheidende Bindeglied
zwischen der allgemeinen Theorie der Vektorräume und konkreten Rechnun-
gen und damit auch zu unserer geometrischen Anschauung. Um eine Ver-
bindung der allgemeinen Theorie zu konkreten Rechnungen zu ermöglichen,
benötigen wir die grundlegende Tatsache, dass alle Basen eines Vektorraumes
dieselbe Anzahl von Elementen besitzen. Der folgende Satz dient zur Vorbe-
reitung des Beweises dieser wichtigen und nicht offensichtlichen Tatsache.
Satz 2.2.12 Wenn (v1 , . . . , vr ) eine Basis und (w1 , . . . , ws ) eine linear un-
abhängige Liste von Vektoren eines K-Vektorraumes V ist, dann gilt r ≥ s.
2.2 Vektorräume und lineare Abbildungen 99
Bemerkung 2.2.15. Mit Hilfe von Satz 2.2.11 lässt sich zeigen, dass ein K-
Vektorraum V genau dann unendlichdimensional ist, wenn für jede natürliche
Zahl n ≥ 0 eine linear unabhängige Liste existiert, die genau n Elemente aus
V enthält.
Der aufmerksame Leser wird bemerkt haben, dass die Beobachtungen, die wir
am Ende von Abschnitt 2.1 gemacht hatten, besagen, dass die Lösungsmenge
eines linearen Gleichungssystems der Gestalt Ax = 0 ein Vektorraum ist.
Um nicht nur die Lösungsmenge, sondern auch das Gleichungssystem selbst
in einem allgemeinen Begriff zu fassen, befassen wir uns nun mit struktur-
erhaltenden Abbildungen zwischen Vektorräumen. Das ist analog zu den im
Kapitel 1 studierten Begriffen der Homomorphismen von Gruppen, Ringen
und Körpern. Zur Vermeidung von Schwierigkeiten, die von einem ersten
Verständnis der Grundbegriffe ablenken würden, betrachten wir ab jetzt nur
noch solche Vektorräume, die ein endliches Erzeugendensystem besitzen und
somit von endlicher Dimension sind.
im(f ) := {f (v) | v ∈ V } ⊂ W
f −1 (w) = {v ∈ V | f (v) = w} ⊂ V
⊓
⊔
Definition 2.2.19. Eine bijektive lineare Abbildung nennt man Isomorphis-
mus von Vektorräumen. Wenn es einen Isomorphismus V → W gibt, dann
sagen wir V und W sind isomorph und schreiben V ∼ = W . Um hervorzuhe-
ben, dass eine lineare Abbildung f : V → W ein Isomorphismus ist, schreiben
∼
wir oft f : V −
→ W.
Beispiel 2.2.20. (i) Die durch pri (x1 , . . . , xn ) := xi definierte Abbildung
pri : K n → K ist für jedes 1 ≤ i ≤ n linear. Die Abbildung pri heißt
Projektion auf die i-te Komponente.
(ii) Wenn U ⊂ V ein Unterraum ist, dann definiert die Inklusion von U in
V eine lineare Abbildung U → V . Im Fall U = V bezeichnen wir diese
Abbildung mit 1V : V → V und nennen sie identische Abbildung, weil
1V (v) = v für alle v ∈ V .
6 Siehe Definition 6.3.3.
102 2 Lineare Algebra
Das ist nichts anderes als die Multiplikation einer Matrix mit einem Vek-
tor fA (x) = A · x, siehe Seite 82. Da fA (ej ) = fA (0, . . . , 0, 1, 0, . . . , 0) =
(a1j , a2j , . . . , amj ) die j-te Spalte von A ist, können wir die Matrix
A aus der linearen Abbildung fA rekonstruieren. Einer beliebigen li-
nearen Abbildung f : K n → K m kann man auf diese Weise eine
Matrix A zuordnen. Pn Sie hat den Vektor f (ej ) als j-te Spalte. Weil
f (x1 , . . . , xn ) = j=1 xj f (ej ), ist dann f = fA und somit ist die Zu-
ordnung A 7→ fA eine Bijektion
Mat(m × n, K) → HomK (K n , K m ) .
∼
Zu jedem Koordinatensystem S : V − → K r gehört genau eine Basis B, so dass
S = SB gilt. Die Basisvektoren vi sind durch S(vi ) = ei eindeutig festgelegt.
Die Wahl einer Basis ist daher gleichwertig mit der Angabe eines Koordina-
tensystems. Etwas mathematischer ausgedrückt: Die Abbildung B 7→ SB ist
eine Bijektion zwischen der Menge aller Basen von V und der Menge aller
Koordinatensysteme von V . Wegen Satz 2.2.13 gilt genau dann dimK V = n,
wenn V ∼ = K n . Die Angabe eines solchen Isomorphismus entspricht der Aus-
wahl einer Basis von V .
In Verallgemeinerung des Beispiels 2.2.20 (iii) können wir jeder linearen Ab-
bildung f : V → W eine Matrix zuordnen. Diese Matrix hängt jedoch von der
Wahl einer Basis A = (v1 , . . . , vn ) von V und einer Basis B = (w1 , . . . , wm )
von W ab. Die Einträge aij der Matrix MBA (f ) ∈ Mat(m × n, K), die wir
Matrixdarstellung von f bezüglich der Basen A und B nennen, definieren wir
durch
m
X
f (vj ) = aij wi .
i=1
Wenn wir mit Koordinatensystemen statt mit Basen arbeiten, wird al-
les noch übersichtlicher: Seien S : V → K n und T : W → K m die
zu A und B gehörigen Koordinatensysteme. Dann ist die lineare Abbil-
dung T ◦ f ◦ S −1 : K n → K m genau die, die unter dem Isomorphismus
∼
Mat(m × n, K) − → HomK (K n , K m ) aus Beispiel 2.2.20 (iii) der Matrix
A
MB (f ) entspricht. Das kann man sich sehr einprägsam durch ein kommutati-
ves Diagramm veranschaulichen, in dem wir MBA (f ) statt fMBA (f ) schreiben:
f
V −−−−→ W
Sy yT (2.12)
n m
K −−−−→ K .
A (f )
MB
ist. Die j-te Spalte von B ◦ A ist das Produkt der Matrix B mit dem j-ten
Spaltenvektor von A (siehe Seite 82).
f g
Wenn U − → V − → W lineare Abbildungen und A = (u1 , . . . , ur ), B =
(v1 , . . . , vn ), C = (w1 , . . . , wm ) Basen von U, V bzw. W sind, dann gilt
Satz 2.2.26 Die Menge GL(n, K) ist mit dem Matrizenprodukt eine Gruppe.
(A ◦ B) ◦ (B ′ ◦ A′ ) = A ◦ (B ◦ B ′ ) ◦ A′ = A ◦ 1n ◦ A′ = A ◦ A′ = 1n und
(B ′ ◦ A′ ) ◦ (A ◦ B) = B ′ ◦ (A′ ◦ A) ◦ B = B ′ ◦ 1n ◦ B = B ′ ◦ B = 1n .
Somit gilt für beliebige A, B ∈ GL(n, K) stets A ◦ B ∈ GL(n, K). Die Grup-
penaxiome folgen nun sehr leicht aus Satz 2.2.24 und der Definition. ⊓
⊔
Wie für Gruppen üblich, schreiben wir A−1 statt A′ und sprechen von der
inversen Matrix. Aus den vorangegangenen Betrachtungen ist nun klar, dass
eine Matrix A ∈ Mat(n × n, K) genau dann in GL(n, K) liegt, wenn fA ein
Isomorphismus ist.
Definition 2.2.27. (1) Sei f : V → W eine lineare Abbildung, dann ist der
Rang der Abbildung f die Zahl rk(f ) := dimK im(f ).
(2) Sei A ∈ Mat(m × n, K), dann ist der Rang rk(A) der Matrix A die
maximale Anzahl linear unabhängiger Spalten von A.
Beweis. Zunächst beweisen wir die Aussage für lineare Abbildungen f . Sei
r = rk(f ) = dimK im(f ) und (w1 , . . . , wr ) eine Basis von im(f ) ⊂ W . Sei
außerdem s := dimK ker(f ) und (v1 , . . . , vs ) eine Basis von ker(f ) ⊂ V . Wir
wählen beliebige Vektoren vs+1 , . . . , vs+r ∈ V , für die f (vs+i ) = wi gilt.
Dann ist (v1 , . . . , vs+r ) eine Basis von V . Um dies zu beweisen, zeigen wir,
dass diese Liste linear unabhängig und ein Erzeugendensystem ist.
106 2 Lineare Algebra
Ps+r
Zum Beweis der linearen Unabhängigkeit nehmen wir an j=1 λj vj = 0.
Ps+r
Daraus folgt j=s+1 λj f (vj ) = 0, da f (vj ) = 0 für 1 ≤ j ≤ s. Da für 1 ≤ i ≤
r die Vektoren f (vi+s ) = wi nach Voraussetzung linear unabhängig sind, folgt
λ
Ps+1 = . . . = λs+r = 0. Aus der ursprünglichen Gleichung erhalten wir daher
s
j=1 λj vj = 0. Da v1 , . . . , vs linear unabhängig sind, folgt λ1 = . . . = λs = 0.
Um zu zeigen, dass (v1 , . . . , vs+r ) ein Erzeugendensystem von V ist, wählen
Pbeliebigen Vektor v ∈ V . Dann
wir einen P∈ K, so dass
P gibt es λs+1 , . . . , λs+r
f (v) = ri=1 λs+i wi gilt. Da f (v − ri=1 λs+i vs+i ) = f (v) − ri=1 λs+i wi =
Ps+r
0, ist v − j=s+1 λj vj ∈ ker(f ). Da (v1 , . . . , vs ) eine Basis von ker(f ) ist,
P Ps
gibt es λ1 , . . . , λs ∈ K, so dass v − s+r j=s+1 λj vj = j=1 λj vj gilt, d.h.
Pr+s
v = j=1 λj vj .
Die Aussage für Matrizen A folgt aus dem bereits Gezeigten, da rk(A) =
rk(fA ) und Lös(A| 0) = ker(fA ). ⊓
⊔
Beweis. Für den ersten Teil genügt es zu zeigen, dass f genau dann injek-
tiv ist, wenn f surjektiv ist. Mit Hilfe der Dimensionsformel (Satz 2.2.28)
erhalten wir:
Die Äquivalenz (i) ⇐⇒ (ii) im zweiten Teil folgt aus dem bereits Gezeigten.
Zum Beweis von (ii) ⇒ (iii) sei A ∈ GL(n, K). Dann gilt A ◦ A−1 = 1n und
t
A−1 ◦ A = 1n . Da 1n t = 1n , erhalten wir aus Satz 2.2.24 (5) (A−1 ) ◦ At = 1n
t t
und At ◦ (A−1 ) = 1n , daher gilt At ∈ GL(n, K). Da (At ) = A, ergibt sich
auch die umgekehrte Implikation (iii) ⇒ (ii). ⊓
⊔
t
Bemerkung 2.2.30. Aus dem Beweis sehen wir (At )−1 = (A−1 ) .
2.2 Vektorräume und lineare Abbildungen 107
Folgerung 2.2.32. (1) Jeder Unterraum U ⊂ V ist der Kern der kanoni-
schen Abbildung V → V /U und es gilt dimK V /U = dimK V − dimK U .
(2) (Homomorphiesatz) Wenn f : V → W eine lineare Abbildung ist,
∼
dann ist durch f¯([v]) := f (v) ein Isomorphismus f¯ : V / ker(f ) −
→ im(f )
definiert.
Beweis. Die Aussage (1) ist wegen der Surjektivität der kanonischen Abbil-
dung und Satz 2.2.28 klar. Zum Beweis von (2) können wir Satz 1.3.32 anwen-
den und erhalten, dass f¯ ein Isomorphismus der zugrunde liegenden additiven
Gruppen ist. Da außerdem f¯(λ[v]) = f¯([λv]) = f (λv) = λf (v) = λf¯([v]), ist
f¯ linear und somit ein Isomorphismus von Vektorräumen. ⊓
⊔
rk(f ) = rk(ψ ◦ f ◦ ϕ) .
(2) Sei A ∈ Mat(m × n, K), P ∈ GL(m, K), Q ∈ GL(n, K). Dann gilt
Für jede Matrix stimmt die maximale Zahl linear unabhängiger Zeilen
mit der maximalen Zahl linear unabhängiger Spalten überein.
⊓
⊔
Aufgaben
gegebene lineare Abbildung. Berechnen Sie die Matrix MBA (f ) bezüglich der
Basen A = (a1 , a2 , a3 ) von R3 und B = (b1 , b2 , b3 , b4 ) von R4 , wobei
Übung 2.13. Finden Sie Beispiele für Matrizen A, B ∈ Mat(n × n, K), für
die A ◦ B = 0, jedoch A 6= 0 und B 6= 0 ist. Können Sie auch ein Beispiel
angeben, in dem kein Eintrag von A oder von B gleich 0 ist? Wählen Sie
mindestens n ≥ 3.
Übung 2.14. Finden Sie Beispiele für Matrizen A, B ∈ Mat(n × n, K), für
die A ◦ B 6= B ◦ A gilt.
Übung 2.16. Für die Faschingsfeier soll ein leicht alkoholhaltiges Mischge-
tränk hergestellt werden. Findige Studenten haben bei einem Großhändler
extrem preisgünstige Angebote für drei verschiedene No-Name-Produkte aus-
findig gemacht. Obwohl die Namen der Getränke nicht bekannt sind, ist durch
eine Analyse deren Zusammensetzung ermittelt worden. Der prozentuale An-
teil von Alkohol, Wasser und sonstiger Bestandteile kann der folgenden Ta-
belle entnommen werden:
Alkohol Wasser Sonstiges
Getränk 1 20 20 60
Getränk 2 20 70 10
Getränk 3 0 50 50
110 2 Lineare Algebra
Ist es möglich, daraus ein Getränk (wie auch immer es dann schmecken mag)
zu mischen, in dem 10% Alkohol und 40% Wasser enthalten sind? Falls ja,
bestimmen Sie die Menge jeder Getränkesorte, die man benötigt, um 100
Liter dieser Mischung herzustellen.
Das Ziel dieses Abschnittes ist es, die Rechenverfahren von Abschnitt 2.1 im
Kontext der allgemeinen Theorie von Vektorräumen und linearen Abbildun-
gen zu benutzen. Wir werden mit Hilfe elementarer Zeilenoperationen die
folgenden Aufgaben lösen:
• Bestimmung einer maximalen linear unabhängigen Liste als Teil einer ge-
gebenen Liste von Vektoren.
• Ergänzung einer gegebenen linear unabhängigen Liste zu einer Basis.
• Berechnung der Inversen A−1 einer Matrix A.
• Bestimmung eines Gleichungssystems zu vorgegebener Lösungsmenge.
• Berechnung des Durchschnittes zweier Unterräume.
• Berechnung der Summe zweier Unterräume.
Zur Vorbereitung übersetzen wir die Zeilenumformungen des Gaußschen Al-
gorithmus in die Sprache der Matrizen. Dazu erinnern wir uns daran, dass
dieser Algorithmus auf zwei Typen elementarer Zeilenumformungen beruht:
(Z1) Vertauschung von Zeile i mit Zeile j.
(Z2) Addition des λ-fachen von Zeile k zu Zeile i.
Diese Umformungen lassen sich mit Hilfe der folgenden Elementarmatrizen
P (i, j) ∈ Mat(m × m, K) und Qλ (i, k) ∈ Mat(m × m, K) beschreiben.
Die einzigen von Null verschiedenen Einträge der Matrix P (i, j) sind akk = 1
wenn k 6= i oder k 6= j und aij = aji = 1. Die Matrix Qλ (i, k) unterscheidet
sich von der Einheitsmatrix nur dadurch, dass sie in der i-ten Zeile und k-ten
Spalte den Eintrag λ hat. So ist zum Beispiel im Fall m = 5
10000 10000
0 0 0 1 0 0 0 0 0 1
0 0 1 0 0
P (2, 4) = P (4, 2) = , P (5, 2) = P (2, 5) = 0 0 1 0 0
0 1 0 0 0 0 0 0 1 0
00001 01000
und
2.3 Anwendungen des Gaußschen Algorithmus 111
1 00 0 0 100 00
0 1 0 −1 0 0 1 0 0 0
Q−1 (2, 4) =
0 0 1 0 0 , Qλ (4, 2)
0 0 1 0 0
.
0 0 0 1 0 0 λ 0 1 0
0 00 0 1 000 01
Wenn A ∈ Mat(m × n, K), dann ist P (i, j) ◦ A genau die Matrix, die man
aus A durch Anwendung von (Z1) erhält, und Qλ (i, k) ◦ A ist die Matrix, die
durch Anwendung von (Z2) aus A entsteht. Interessant ist nun:
Daher gilt sogar P (i, j) ∈ GL(m, K) und Qλ (i, k) ∈ GL(m, K). Aus Satz
2.2.33 (2) erhalten wir damit, dass die elementaren Zeilenumformungen (Z1)
und (Z2) den Rang einer Matrix nicht verändern und dass dieser Rang gleich
der Zahl der von Null verschiedenen Zeilen einer Zeilenstufenform ist.
Unter Benutzung des bisher Gesagten liefert der Gaußsche Algorithmus den
folgenden Satz.
Bemerkung 2.3.2. Wie in Bemerkung 2.1.6 erwähnt, kann man durch ele-
mentare Zeilenumformungen auch oberhalb der Pivotelemente Nullen erzeu-
gen. Wenn wir zusätzlich noch die Multiplikation einer Zeile mit einem Fak-
tor λ 6= 0 zulassen, dann können wir sogar die sogenannte reduzierte Zei-
lenstufenform herstellen, bei der alle Pivotelemente gleich 1 sind. Da auch
die Multiplikation einer Zeile mit einem Faktor λ 6= 0 durch die Multipli-
kation mit einer invertierbaren Matrix von links beschrieben werden kann,
bleibt Satz 2.3.1 wahr, wenn wir darin Zeilenstufenform durch reduzierte
Zeilenstufenform ersetzen und zusätzlich zu den Elementarmatrizen auch
noch solche invertierbare Matrizen zulassen, die aus der Einheitsmatrix durch
Multiplikation einer Zeile mit einem von Null verschiedenen λ ∈ K her-
vorgehen. Der Vorteil der reduzierten Zeilenstufenform besteht darin, dass
man eine Parametrisierung der Lösungsmenge des zugehörigen linearen Glei-
chungssystems unmittelbar ablesen kann. In der Sprache von Abschnitt 2.2
heißt das, dass wir aus der reduzierten Zeilenstufenform leicht eine Basis von
ker(fA ) = ker(fP ◦A ) = Lös(P ◦ A| 0) = Lös(A| 0) ablesen können.
112 2 Lineare Algebra
Häufig ist man mit der Aufgabe konfrontiert, aus einer Liste (u1 , u2 , . . . , un )
von Vektoren uj ∈ K m eine maximale Liste linear unabhängiger Vekto-
ren auszuwählen. Zur Lösung dieser Aufgabe betrachtet man die Matrix
A ∈ Mat(m×n, K), deren Spalten die gegebenen Vektoren uj sind. Da für je-
de Matrix P ∈ GL(m, K) die Gleichung (P ◦A)·x = 0 dieselbe Lösungsmenge
wie die Gleichung A · x = 0 hat, ist eine Teilliste der ursprünglich gegebenen
Vektoren genau dann linear unabhängig, wenn dies für die entsprechenden
Spalten von P ◦ A gilt. Wenn P ◦ A Zeilenstufenform hat, was wir wegen Satz
2.3.1 immer erreichen können, dann bilden die Spalten, in denen die Pivot-
elemente stehen, offenbar eine maximale Liste linear unabhängiger Spalten.
Das zeigt, dass die erste, zweite, dritte und fünfte Spalte von A eine maximale
linear unabhängige Liste bilden. Die ersten vier Spalten bilden dagegen keine
solche Liste.
Basisergänzung
Beispiel 2.3.4. Die beiden Vektoren (1, 0, 0, 1) und (0, 1, 1, 0) sind linear un-
abhängig. Um eine Basis von K 4 zu finden, in der diese beiden Vektoren
auftreten, überführen wir die Matrix
101000
0 1 0 1 0 0
0 1 0 0 1 0
100001
Daraus sehen wir, dass die beiden gegebenen Vektoren zusammen mit e1 und
e2 eine Basis bilden. Zusammen mit e2 und e3 bilden sie dagegen keine Basis.
(0 0 . . . 0 | Li (x)) ,
Pm
wobei Li (x) eine Linearkombination j=1 aij xj der Variablen xj ist. Falls
U 6= K m , dann gibt es mindestens eine solche Zeile. Wenn n ≥ 1 solche Zeilen
in der Zeilenstufenform auftreten, dann lautet die Lösbarkeitsbedingung für
das obige Gleichungssystem
m
X
aij xj = 0 für 1 ≤ i ≤ n .
j=1
−x2 +x4 =0
−2x2 +x3 +x5 = 0 ,
Als Übungsaufgabe empfehlen wir dem Leser, mit Hilfe des Gaußschen Al-
gorithmus eine Basis der Lösungsmenge dieses Gleichungssystems zu be-
stimmen und dann festzustellen, ob diese Lösungsmenge tatsächlich mit U
übereinstimmt.
im R5 . Wir haben in Beispiel 2.3.6 eine Matrix A bestimmt, deren Kern gleich
U ist. Unter Benutzung der zuvor eingeführten Bezeichnung ist somit
21 4
3 2 0
0 −1 0 1 0
A= und B = 1 0 −1
.
0 −2 1 0 1 3 2 0
32 3
118 2 Lineare Algebra
0 0 0
Wir erhalten A ◦ B = . Die reduzierte Zeilenstufenform dieser
−2 −2 2
1 1 −1
Matrix hat die Gestalt , woraus wir als Basis des zugehörigen
00 0
Lösungsraumes die beiden Vektoren (−1, 1, 0) und (1, 0, 1) erhalten. Dies sind
noch nicht die gesuchten Basisvektoren, sondern deren Koordinaten bezüglich
(v1 , v2 , v3 ). Als Basis für den Durchschnitt U ∩ V ergeben sich daraus die bei-
den Vektoren
−1
B 1 = −v1 + v2 = (−1, −1, −1, −1, −1) und
0
1
B 0 = v1 + v3 = (6, 3, 0, 3, 6) .
1
U + V := {u + v | u ∈ U, v ∈ V } ⊂ W
ein Unterraum. Dies ist der kleinste Unterraum, der U und V enthält.
Wenn (u1 , . . . , ur ) Basis von U und (v1 , . . . , vs ) Basis von V ist, dann ist
offenbar (u1 , . . . , ur , v1 , . . . , vs ) ein Erzeugendensystem von U + V . Im Allge-
meinen wird dies jedoch keine Basis sein.
Nach der Wahl von Koordinatensystemen können wir annehmen W = K n .
Aus der Zeilenstufenform der Matrix, deren Spalten die Koordinaten der ge-
gebenen Vektoren sind, kann man auf zuvor beschriebene Weise eine Basis von
U + V ablesen. Alternativ kann man eine (r + s)× n-Matrix bilden, deren Zei-
len die Koordinaten der Vektoren u1 , . . . , ur , v1 , . . . , vs sind. Durch elemen-
tare Zeilenumformungen können wir auch diese Matrix in Zeilenstufenform
überführen. Die von 0 verschiedenen Zeilen dieser Zeilenstufenform bilden
dann eine Basis von U + V . Der Rang dieser Matrix ist gleich der Dimension
von U + V . Daraus sehen wir, dass im Allgemeinen nur dimK (U + V ) ≤ r + s
gilt. Die Situation wird durch den folgenden Satz vollständig geklärt.
Beweis. Sei (w1 , . . . , wt ) eine Basis von U ∩ V . Diese können wir zu einer
nicht verlängerbaren linear unabhängigen Liste (w1 , . . . , wt , ut+1 , . . . , ur ) von
2.3 Anwendungen des Gaußschen Algorithmus 119
U ergänzen. Nach Satz 2.2.11 ist das eine Basis von U . Ebenso finden wir
eine Basis der Gestalt (w1 , . . . , wt , vt+1 , . . . , vs ) von V .
Wir behaupten nun, dass (w1 , . . . , wt , ut+1 , . . . , ur , vt+1 , . . . , vs ) eine Basis
von U + V ist, woraus die gewünschte Gleichung
Aufgaben
Übung 2.17. Bestimmen Sie eine Basis des durch die Spalten der Matrix
1 2 2 8 3 3
1 2 1 5 1 3
−1 −2 0 −2 2 −4
2 4 3 13 6 4
Übung 2.19. Berechnen Sie die Inverse A−1 ∈ GL(4, R) der Matrix
1100
1 1 1 0
A=
0 1 1 1 ∈ GL(4, R) .
0011
Übung 2.20. Berechnen Sie die Inverse B −1 ∈ GL(3, F13 ) der Matrix
12 1
B = 0 1 0 ∈ GL(3, F13 ) .
1 0 −1
Übung 2.23. Sei U ⊂ Q3 die durch die beiden Vektoren (1, 2, 1), (27, 0, 3)
aufgespannte Ebene und sei V ⊂ Q3 die Ebene, die durch die beiden Vek-
toren (2, 1, 2), (41, 28, 1) aufgespannt wird. Bestimmen Sie eine Basis für den
Durchschnitt U ∩ V .
Man nennt eine Matrix quadratisch, wenn sie ebenso viele Zeilen wie Spalten
besitzt. Solche Matrizen treten vor allem beim Studium von Symmetrien und
inneren Strukturen von Vektorräumen auf. Es gibt mindestens zwei Gründe,
weshalb ihnen ein eigener Abschnitt gewidmet ist. Auf der einen Seite sind
2.4 Quadratische Matrizen 121
Determinanten
Beispiel 2.4.2. Für n = 2 und n = 3 ergibt sich aus dieser Definition explizit
ab
det = ad − bc und
cd
a11 a12 a13
a a a a a a
deta21 a22 a23 = a11 det 22 23 −a21 det 12 13 +a31 det 12 13
a32 a33 a32 a33 a22 a23
a31 a32 a33
= a11 a22 a33 + a12 a23 a31 + a13 a21 a32 − a31 a22 a13 − a32 a23 a11 − a33 a21 a12 .
Der letzte Ausdruck lässt sich mittels folgender Graphiken leichter einprägen:
Wir werden auf den folgenden Seiten ein Verfahren zur Berechnung von De-
terminanten kennenlernen, welches weitaus effizienter ist als die rekursive
Anwendung der Definition. Es beruht darauf, dass die Determinante einer
oberen Dreiecksmatrix gleich dem Produkt ihrer Diagonalelemente ist. Dies
ergibt sich aus Definition 2.4.1 wie folgt:
a11 a12 . . . . . . a1n
0 a22 . . . . . . a2n a22 . . . . . . a2n
0 a33 . . . a3n
det 0 0 a33 . . . a3n = a11 · det . . . =
.. . . . .. . . . . ...
. . . . . ..
0 . . . 0 ann
0 . . . . . . . 0 ann
a33 . . . . . . a3n
..
0 a44 .
= a11 · a22 · det . = . . . = a11 · a22 · a33 · . . . · ann .
. .
.. . . ..
0 . . . 0 ann
Wir empfehlen unseren Lesern, einen formal korrekten Beweis mittels Induk-
tion über n selbständig zu formulieren.
Beweis. Die Aussagen (1) und (2) ergeben sich per Induktion über n unmit-
telbar aus Definition 2.4.1.
Wenn Aussage (3) für ein festes n gezeigt ist, dann ergibt sich daraus die
Aussage (5) für denselben Wert von n. Dazu bemerken wir, dass nach (1)
det(A) = det(A′ )+det(A′′ ) gilt, wenn wir A′′ durch zi′′ = λzj′ für das gegebene
Paar von Indizes i 6= j und zk′′ = zk′ für alle k 6= i definieren. Da aus (2) und
(3) det(A′′ ) = 0 folgt, ist (5) gezeigt.
Aus der Gültigkeit von (2) und (5) für ein festes n ergibt sich die Aussage
(4), da sich die Vertauschung zweier Zeilen durch eine Folge von Additionen
eines Vielfachen einer Zeile zu einer anderen – was nach (5) die Determinante
nicht ändert – gefolgt von der Multiplikation einer Zeile mit dem Faktor −1
2.4 Quadratische Matrizen 123
beschreiben lässt:
zi zi + zj zi + zj zj zj
7→ 7→ 7→ 7→ .
zj zj −zi −zi zi
Somit bleibt noch die Gültigkeit der Aussage (3) zu beweisen. Das geschieht
per Induktion über n. Für n = 2 ist das aus der expliziten Formel in Beispiel
2.4.2 sofort einzusehen. Für den Induktionsschritt nehmen wir an, (3) gilt für
quadratische Matrizen der Größe n − 1 ≥ 2. Wir haben bereits gezeigt, dass
dann auch alle anderen Aussagen des Satzes für Matrizen der Größe n − 1
gültig sind. Für eine Matrix A ∈ Mat(n × n, K), deren Zeile i mit Zeile j
übereinstimmt, haben auch die Matrizen Ak1 für k 6= i, j zwei gleiche Zeilen.
Da die Matrizen Ak1 die Größe n−1 haben, verschwindet deren Determinante
nach Induktionsvoraussetzung und wir erhalten
Die Matrix Aj1 geht aus Ai1 durch ±(j − i) − 1 Zeilenvertauschungen hervor.
Wegen (4) ist daher det(Aj1 ) = (−1)i−j−1 det(Ai1 ). Mit aj1 = ai1 folgt nun
die Behauptung det(A) = 0. ⊓
⊔
Mit λ = 0 in (2) erhält man, dass die Determinante einer Matrix, die eine nur
aus Nullen bestehende Zeile enthält, gleich Null ist. Aus den Aussagen (4)
und (5) des Satzes 2.4.3 ergibt sich det(P (i, j)) = −1 und det(Qλ (i, k)) = 1
für i 6= j, i 6= k und λ ∈ K. Es folgt außerdem für jedes A ∈ Mat(n × n, K)
Das bedeutet, dass die elementare Zeilenumformung (Z1) das Vorzeichen der
Determinante einer Matrix ändert, die elementare Zeilenumformung (Z2) da-
gegen die Determinante unverändert lässt. Dadurch ist es möglich, mit Hilfe
des Gaußschen Algorithmus die Determinante einer quadratischen Matrix zu
berechnen. Dazu erzeugt man Zeilenstufenform und merkt sich die Zahl v
der Zeilenvertauschungen. Das Produkt der Diagonalelemente der Zeilenstu-
fenform ist dann bis auf das Vorzeichen (−1)v gleich der Determinante der
ursprünglichen Matrix. Durch Anwendung der Regel (2) aus Satz 2.4.3 lässt
sich die Rechnung oft noch vereinfachen. Diese Überlegungen und Folgerung
2.2.29 zeigen, dass eine quadratische Matrix genau dann invertierbar ist, wenn
ihre Determinante nicht verschwindet. Für jedes A ∈ Mat(n × n, K) gilt
A ∈ GL(n, K) ⇐⇒ det(A) 6= 0 .
124 2 Lineare Algebra
Beispiel 2.4.4.
3 3 9 1 1 3 1 1 3
det 2 5 13 = 3 det 2 5 13 = 3 det 0 3 7
8 21 34 8 21 34 0 13 10
3 7
= 3 det = 3(30 − 91) = −183 .
13 10
Beweis. Wenn P das Produkt von Elementarmatrizen und T eine obere Drei-
ecksmatrix ist, dann gilt wegen (2.13) und (2.14) det(P ◦ T ) = det(P ) det(T ).
Aus Satz 2.4.3 (2) folgt auf analoge Weise für jede Matrix B ∈ Mat(n × n, K)
und jede Diagonalmatrix D die Gleichung det(D ◦ B) = det(D) det(B).
Sei T die wie beim Gauß-Jordan-Verfahren aus der quadratischen Matrix A
erzeugte Zeilenstufenform, in der auch oberhalb der Pivotelemente Nullen
stehen. Dann gibt es eine Matrix P , die ein Produkt von Elementarmatrizen
ist, so dass A = P ◦ T . Wenn T eine Diagonalmatrix ist, dann folgt
Wenn T keine Diagonalmatrix ist, muss ein Zeilenvektor von T gleich Null
sein. Dies ist dann auch für die Matrix T ◦ B der Fall. Daraus folgt einer-
seits det(A ◦ B) = det(P ) det(T ◦ B) = 0 und andererseits det(A) det(B) =
det(P ) det(T ) det(B) = 0, woraus sich die Behauptung ergibt. ⊓
⊔
Bemerkung 2.4.6. In der Sprache von Abschnitt 1.3 besagt Satz 2.4.5, dass
det : GL(n, K) −→ K ∗ ein Gruppenhomomorphismus ist. Sein Kern
SL(n, K) = A | det(A) = 1
tritt unter dem Namen spezielle lineare Gruppe in der Literatur auf.
Beweis. Wenn T die Zeilenstufenform von A mit Nullen oberhalb der Pivot-
elemente ist, dann gibt es wieder ein Produkt von Elementarmatrizen P , so
2.4 Quadratische Matrizen 125
Satz 2.4.9 Sei A ∈ Mat(n × n, K) und B = (bij ) die Matrix mit den
Einträgen bij = (−1)i+j det(Aji ). Dann gilt A ◦ B = det(A)1n . Wenn
1
A ∈ GL(n, K), dann ist A−1 = B.
det(A)
Beweis. Der j-te Spaltenvektor vj von B hat als k-ten Eintrag bkj =
(−1)k+j det(Ajk ). Der i-te Eintrag des Vektors Avj ist daher gleich
n
X n
X
aik bkj = (−1)k+j aik det(Ajk ) .
k=1 k=1
Wenn i = j, dann ist dies wegen Folgerung 2.4.7 (iii) gleich det(A). Wenn
i 6= j, dann ist dieser Ausdruck gleich der Determinante der Matrix, die aus
A durch Ersetzung der j-ten Zeile durch ihre i-te Zeile entsteht. Da diese
Matrix zwei gleiche Zeilen besitzt, ist ihre Determinante gleich Null. ⊓
⊔
n
1 X 1
(−1)i+k bk det(Aki ) = det(Ai ) .
det(A) det(A)
k=1
⊓
⊔
Orthogonalität
Zum Einstieg in die lineare Algebra hatten wir uns im Abschnitt 2.1 mit geo-
metrischen Objekten wie Geraden und Ebenen im dreidimensionalen Raum
beschäftigt. Für unsere geometrische Anschauung verwenden wir normaler-
weise ein Koordinatensystem, in dem die Koordinatenachsen senkrecht auf-
einander stehen. Diesen Aspekt hatten wir bisher völlig ignoriert. Begriffe
wie Länge, Winkel oder senkrecht zueinander sind im abstrakten Konzept
eines Vektorraumes nicht widergespiegelt. Im Rahmen der linearen Algebra
lassen sich diese grundlegenden geometrischen Konzepte aus dem Begriff des
Skalarproduktes ableiten. Erst nach dieser Erweiterung verfügen wir über ein
adäquates Konzept zur Beschreibung von ebenen oder räumlichen Bewegun-
gen, ein Grundbedürfnis der Computergraphik.
Das Standardskalarprodukt auf dem Vektorraum Rn ist durch
n
X
hx, yi = xi yi = xt · y
i=1
Wenn K ein Körper und V ein K-Vektorraum ist, dann heißt eine Abbildung
V × V −→ K symmetrische Bilinearform, wenn sie die Bedingungen (2.15),
(2.16) und (2.17) erfüllt. Die Eigenschaft (2.18) ist eine Spezialität für K = Q
oder K = R. Eine Bilinearform mit dieser Eigenschaft heißt positiv definit .
Jede positiv definite, symmetrische Bilinearform h·, ·i : Rn × Rn −→ R nennt
man Skalarprodukt.
Aus (2.15) und (2.16) folgt für beliebige v1 , . . . , vn ∈ V und ai , bi ∈ K
* n n
+ n X n
X X X
ai vi , bj vj = ai bj hvi , vj i .
i=1 j=1 i=1 j=1
Ob eine solche Matrix ein positiv definites Skalarprodukt definiert, kann man
leicht mit dem Hauptminorenkriterium (Satz 2.4.29) entscheiden.
Die geometrischen Grundbegriffe Länge, Orthogonalität und Winkel erhält
man auf folgende Weise aus einem Skalarprodukt h·, ·i auf V = Rn .
p
Definition 2.4.12. (1) kxk = hx, xi heißt Länge von x ∈ Rn .
(2) x ∈ Rn heißt senkrecht (oder orthogonal ) zu y ∈ Rn , falls hx, yi = 0.
(3) Der Winkel zwischen x 6= 0 und y 6= 0 ist die eindeutig bestimmte Zahl
hx, yi
0 ≤ α ≤ π, für die cos(α) = gilt.
kxk · kyk
Da −1 ≤ cos(α) ≤ 1 für jede reelle Zahl α, benötigen wir den folgenden Satz
zur Rechtfertigung der Definition des Winkels zwischen zwei Vektoren.
Beweis. Für jede reelle Zahl t gilt htx + y, tx + yi ≥ 0 wegen (2.18). Daher
hat das quadratische Polynom htx + y, tx + yi = t2 kxk2 + 2thx, yi + kyk2
in der Variablen t höchstens eine reelle Nullstelle. Der Ausdruck unter der
Wurzel in der Lösungsformel dieser quadratischen Gleichung kann damit nicht
2
positiv sein, das heißt (hx, yi) − kxk2 · kyk2 ≤ 0. Daraus folgt die behauptete
Ungleichung. ⊓
⊔
Als Folgerung ergibt sich daraus die sogenannte Dreiecksungleichung, der
wir beim Studium fehlerkorrigierender Codes wiederbegegnen werden, siehe
Definition 2.5.3.
kx + yk kyk
kxk
Abb. 2.12 Dreiecksungleichung
kx + yk ≤ kxk + kyk .
ein Unterraum von Rn ist. Wenn (v1 , v2 , . . . , vm ) eine Basis von U ⊂ Rn und
A ∈ Mat(m × n, R) die Matrix ist, deren Zeilen die Vektoren vi sind, dann ist
die i-te Komponente des Vektors Ax gleich hvi , xi. Somit ist U ⊥ = Lös(A| 0).
Hier haben wir das Standardskalarprodukt des Rn benutzt.
9 Augustin Louis Cauchy (1789–1857), französischer Mathematiker.
Rechnungen mit Vektoren des Raumes Rn sind unter Verwendung der kano-
nischen Basis (e1 , . . . , en ) besonders bequem. Das liegt unter anderem daran,
dass die Gramsche Matrix des Standardskalarproduktes bezüglich dieser Ba-
sis die Einheitsmatrix 1n ist. Basen mit dieser Eigenschaft, auch bezüglich
anderer symmetrischer Bilinearformen, sind daher von besonderem Interesse.
Definition 2.4.16. Eine Basis (v1 , v2 , . . . , vn ) eines K-Vektorraumes, auf
dem eine symmetrische Bilinearform h·, ·i gegeben ist, heißt Orthonormal-
basis (kurz: ON-Basis), falls
(
0 falls i 6= j
hvi , vj i =
1 falls i = j.
Eine ON-Basis zeichnet sich dadurch aus, dass jeder ihrer Vektoren die Länge
eins hat und orthogonal zu allen anderen Basisvektoren ist.
Die Bestimmung einer ON-Basis eines Unterraumes V ⊂ Rn bezüglich des
Standardskalarproduktes auf Rn ist bereits ein interessantes Problem. Dieses
wird durch den folgenden Algorithmus gelöst.
Gram-Schmidt10 Orthonormalisierungsverfahren
Als Eingabedaten seien die Vektoren einer Basis (w1 , w2 , . . . , wm ) eines mit
einer symmetrischen Bilinearform ausgestatteten Vektorraumes V gegeben.
Ausgegeben wird eine ON-Basis (v1 , v2 , . . . , vm ) von V .
1
Schritt 1: v1 := w1
kw1 k
1 Pk−1
Schritt k ≥ 2: vk := zk mit zk := wk − i=1 hwk , vi ivi .
kzk k
Für die Vektoren vk gilt offenbar kvk k = 1. Außerdem ist für j < k
* k−1
+ k−1
X X
hzk , vj i = wk − hwk , vi ivi , vj = hwk , vj i − hwk , vi ihvi , vj i .
i=1 i=1
Wenn wir Induktion über k ≥ 2 führen, dann können wir an dieser Stelle
voraussetzen, dass v1 , . . . , vk−1 bereits eine ON-Basis des von diesen Vektoren
aufgespannten Unterraumes ist. Daher ist hvi , vj i = 0 für i 6= j < k und
Obiges vereinfacht sich zu hzk , vj i = hwk , vj i − hwk , vj i = 0, daher auch
hvk , vj i = 0.
Damit ist gezeigt, dass dieses Verfahren tatsächlich eine ON-Basis produziert.
10Jørgen Pedersen Gram (1850–1916), dänischer Mathematiker.
Erhard Schmidt (1876–1959), deutscher Mathematiker.
130 2 Lineare Algebra
5 9 2
Die Vektoren in V sind genau diejenigen, die zu v4 orthogonal sind, das heißt,
V ist die Lösungsmenge der Gleichung
Das ist eine Alternative zu dem auf Seite 114 beschriebenen Verfahren, wel-
ches ein Gleichungssystem mit vorgegebener Lösungsmenge produziert.
Wenn f : Rn → Rm durch eine Matrix A gegeben ist, dann haben die Einträge
bezüglich der neuen Basen die Gestalt hwi , Avj i.
Das sind genau die Matrizen, deren Spalten bezüglich des Standardskalar-
t
produktes eine ON-Basis des Rn bilden. Aus hx, P yi = xt P y = (P t x) y =
t
hP x, yi ergibt sich, wenn wir x durch P x ersetzen, dass für jede orthogonale
Matrix P und alle x, y ∈ Rn die Gleichung
132 2 Lineare Algebra
hP x, P yi = hx, yi
gilt. Aus Definition 2.4.12 folgt damit, dass die durch eine Matrix P definierte
lineare Abbildung fP : Rn → Rn , vgl. Beispiel 2.2.20, genau dann Winkel
und Längen nicht verändert, wenn P orthogonal ist.
Das Produkt zweier orthogonaler Matrizen ist stets wieder orthogonal. Das
folgt aus der Gleichung (P ◦ Q)t ◦ P ◦ Q = Qt ◦ P t ◦ P ◦ Q. Die Menge aller
orthogonalen Matrizen gleicher Größe
O(n) := {P ∈ GL(n, R) | P ◦ P t = 1n }
ist daher eine Gruppe. Sie heißt orthogonale Gruppe. Sie spielt beim Studium
der Geometrie des Raumes Rn eine wesentliche Rolle. Da det(P ) = det(P t ),
2
gilt für jede orthogonale Matrix (det(P )) = 1. Die orthogonalen Matrizen,
deren Determinante gleich eins ist, bilden eine Untergruppe von O(n), die
spezielle orthogonale Gruppe
q = a1 1 + a2 i + a3 j + a4 k mit a1 , a2 , a3 , a4 ∈ R (2.19)
schreiben, wobei (1, i, j, k) eine Basis des reellen Vektorraumes H ist. Die
quaternionische Multiplikation erfüllt
i2 = j2 = k2 = −1, i· j = −j· i = k .
Sie ist nicht kommutativ ! Alle anderen Körperaxiome, vgl. Def. 1.4.1, sind
erfüllt. Statt a1 1 schreibt man abkürzend a1 . Dadurch werden, genau wie im
Fall der komplexen Zahlen, die reellen Zahlen eine Teilmenge von H. Einer
komplexen Zahl a1 + a2 i ordnet man die gleichnamige Quaternion zu und
erhält Inklusionen R ⊂ C ⊂ H. Das ist möglich, da 1 ∈ H das neutrale
Element bezüglich der Multiplikation ist und da die Multiplikation von Qua-
ternionen mit der gewöhnlichen Multiplikation reeller bzw. komplexer Zahlen
verträglich ist. Explizit ergibt sich mit Hilfe des Distributivgesetzes
(a1 + a2 i + a3 j + a4 k) · (b1 + b2 i + b3 j + b4 k) =
= a1 b1 − a2 b2 − a3 b3 − a4 b4 + (a1 b2 + a2 b1 + a3 b4 − a4 b3 ) i
+(a1 b3 − a2 b4 + a3 b1 + a4 b2 ) j + (a1 b4 + a2 b3 − a3 b2 + a4 b1 ) k .
q = a1 − a2 i − a3 j − a4 k .
Der Vorteil der Darstellung von SO(3) mit Hilfe von Quaternionen gegenüber
der Beschreibung durch Matrizen besteht darin, dass statt der neun Einträge
der Matrix nur noch die vier Komponenten der Quaternion gespeichert wer-
den müssen. Hamiltons Entdeckung ermöglicht somit eine signifikante Ver-
ringerung des Speicherplatzbedarfs bei der Beschreibung von Bewegungen im
dreidimensionalen Raum.
Eine ausführliche Darstellung mit Beweisen findet der Leser in [EbZ].
Eigenwerte
Eigenwerte sind vor allem deshalb von Interesse, weil sie eine einfache Be-
schreibung der durch A definierten linearen Abbildung fA : K n → K n
ermöglichen. Wenn es nämlich eine Basis (v1 , v2 , . . . , vn ) von K n gibt, die
sämtlich aus Eigenvektoren der Matrix A besteht, dann ist die Matrixdar-
stellung (siehe Seite 103) der Abbildung fA bezüglich dieser Basis besonders
einfach. Wenn der Eigenwert zu vi gleich λi ist, also fA (vi ) = Avi = λi vi ,
dann wird fA bezüglich dieser Basis durch die Diagonalmatrix mit Einträgen
λ1 , λ2 , . . . , λn entlang der Diagonalen dargestellt. Rechnungen mit Diagonal-
matrizen sind besonders bei sehr großen Matrizen viel ökonomischer als solche
mit Matrizen, in denen nicht so viele Einträge gleich Null sind.
Leider ist es nicht möglich, für jede Matrix eine Basis aus Eigenvektoren zu
finden. Das ist der Fall, wenn der zugrunde liegende Körper K zu klein in dem
Sinne ist, dass nicht jedes Polynom mit Koeffizienten aus K in Linearfaktoren
mit Koeffizienten
aus K zerlegt werden kann. So hat zum Beispiel die Matrix
0 −1 1
1 0 ∈ Mat(2×2, C) die komplexen Eigenwerte i und −i, da 10 −10 −i =
1
1
i −i und 10 −1 0 ( i ) = −i ( 1 ). Über dem Körper K = R hat diese Matrix
i
jedoch keinen Eigenwert.
Außerdem kann es bei Vorliegen mehrfacher Eigenwerte, wie zum Beispiel
bei der Matrix ( 10 11 ) ∈ Mat(2 × 2, R), vorkommen, dass es nicht genügend
2.4 Quadratische Matrizen 135
ker(λ1n − A) = {v ∈ K n | A · v = λv}
Beispiel 2.4.21. Zur Bestimmung der Eigenwerte und Eigenräume der Ma-
trix A = ( 12 21 ) gehen wir folgendermaßen vor. Zunächst bestimmen wir das
charakteristische Polynom
λ0 12 λ − 1 −2
χA (λ) = det (λ12 − A) = det − = det
0λ 21 −2 λ − 1
= (λ − 1)2 − 4 = λ2 − 2λ − 3 .
a1 λk v1 + a2 λk v2 + . . . + ak−1 λk vk−1 + ak λk vk = 0 .
In der Differenz beider Ausdrücke tritt der Vektor vk nicht mehr auf:
2.4.23 linear unabhängig, bilden daher wegen der Sätze 2.2.11 und 2.2.12 eine
Basis von K n . ⊓
⊔
Der Übergang von der Standardbasis zu einer Basis aus Eigenvektoren ge-
schieht durch eine sogenannte Basiswechselmatrix P ∈ GL(n, K). Ihre Spal-
ten werden von den Eigenvektoren v1 , v2 , . . . , vn gebildet. Die i-te Spalte von
A ◦ P ist der Vektor A · vi = λi vi . Wenn D(λ1 , . . . , λn ) die Diagonalma-
trix mit den Eigenwerten λi entlang der Diagonalen (und Nullen überall
sonst) bezeichnet, dann ist λi vi gerade der i-te Spaltenvektor der Matrix
P ◦ D(λ1 , . . . , λn ). Das beweist
Eine solche Darstellung ist für konkrete Rechnungen sehr nützlich, zum Bei-
spiel zur Berechnung sehr hoher Potenzen der Matrix A. Das liegt daran,
dass hohe Potenzen von Diagonalmatrizen mit geringem Aufwand berechnet
werden:
D(λ1 , . . . , λn )k = D(λk1 , . . . , λkn ) ∀k > 0.
Das ergibt
Ak = (P ◦ D(λ1 , . . . , λn ) ◦ P −1 )k
= (P ◦ D ◦ P −1 ) ◦ (P ◦ D ◦ P −1 ) ◦ . . . ◦ (P ◦ D ◦ P −1 )
= P ◦ D(λ1 , . . . , λn )k ◦ P −1
= P ◦ D(λk1 , . . . , λkn ) ◦ P −1 .
3 −1
Beispiel 2.4.25. A =
−1 3
λ−3 1
χA (λ) = det = (λ − 2)(λ − 4)
1 λ−3
1 −1
P =
1 1
k
1 1 −1 2 0 1 1
Ak = P ◦ D(2, 4)k ◦ P −1 =
2 1 1 0 4k −1 1
k
1 2 + 4k 2k − 4k k
k−1 1 + 2 1 − 2
k
= = 2
2 2k − 4k 2k + 4k 1 − 2k 1 + 2k
9444732965808009904128 −9444732965670570950656
A37 =
−9444732965670570950656 9444732965808009904128
38685626227672531637108736 −38685626227663735544086528
A43 =
−38685626227663735544086528 38685626227672531637108736
138 2 Lineare Algebra
Beispiel
2.4.26. Eine interessante Anwendung ergibt sich mit der Matrix
11
A= . Ihr charakteristisches Polynom ist χA (λ) = λ2 − λ − 1 und die
10
Eigenwerte sind
√ √
1+ 5 1− 5
ϕ= und 1 − ϕ = .
2 2
Als Eigenvektor zu ϕ findet man (ϕ, 1) und ein Eigenvektor zu 1 − ϕ ist
(1 − ϕ, 1). Damit ergibt sich
11 ϕ 0 −1 ϕ 1−ϕ
A= =P P mit P = .
10 0 1−ϕ 1 1
√ 1 ϕ−1
Da det(P ) = 2ϕ − 1 = 5, erhalten wir P −1 = √1 und damit
5 −1 ϕ
n
1 ϕ 1−ϕ ϕ 0 1 ϕ−1
An = √ .
5 1 1 0 (1 − ϕ)n −1 ϕ
Die Fibonacci-Folge (vgl. Kapitel 3, Beispiel 3.2.3) ist rekursiv definiert durch
f0 = 0, f1 = 1 und fn+1 = fn + fn−1 für n > 0. Daher gilt
f1 1 fn+1 11 fn fn+1 n 1
= , = , also =A .
f0 0 fn 10 fn−1 fn 0
Somit haben wir durch obige Rechnung die Formel von Binet12 bewiesen
√ !n √ !n !
1 1+ 5 1− 5
fn = √ − .
5 2 2
Wie bereits eingangs erwähnt, existiert nicht in jedem Fall eine Basis aus
Eigenvektoren. Typische Matrizen, für die dies der Fall ist, sind
1000 2100 1100 0100
0 2 1 0 0 2 0 0 0 1 1 0 0 0 1 0
0 0 2 0 0 0 3 1 0 0 1 0 0 0 0 1 .
0003 0003 0002 0000
Der von den Eigenvektoren aufgespannte Unterraum von Q4 hat für die-
se Matrizen jeweils nur die Dimension 3, 2, 2 bzw. 1. Für jede quadratische
Matrix, deren charakteristisches Polynom in Linearfaktoren zerfällt, gibt es
eine sogenannte Jordansche13 Normalform. Die angegebenen Beispiele ha-
ben diese Normalform, die sich dadurch auszeichnet, dass alle Einträge gleich
Null sind außer den auf der Diagonalen eingetragenen Eigenwerten dieser
Matrix und einigen Einträgen direkt über der Diagonalen, die gleich Eins
sind. Sobald diese Normalform außerhalb der Diagonale von Null verschiede-
ne Einträge besitzt, gibt es keine Basis, die aus Eigenvektoren besteht. Auch
diese Normalformen lassen sich als P −1 ◦ A ◦ P mit einer geeigneten Matrix
P ∈ GL(n, K) ausdrücken.
Wir erläutern hier weder die theoretischen Grundlagen zum Beweis der Exis-
tenz der Jordanschen Normalform, noch geben wir eine Beschreibung, wie sie
bestimmt werden kann. Das findet der interessierte Leser in der Standardli-
teratur zur linearen Algebra für Mathematiker, zum Beispiel [Br], [Fi] oder
[Kow].
Statt dessen beschäftigen wir uns mit dem wesentlich einfacheren Spezialfall
der symmetrischen Matrizen.
Beweis. Da die Einträge von A reell sind, hat das charakteristische Polynom
χA (λ) ∈ R[λ] reelle Koeffizienten. Nach dem Fundamentalsatz der Algebra
(Satz 1.4.21) zerfällt es in C[λ] in Linearfaktoren, es ist jedoch möglich, dass
13 Camille Jordan (1838–1922), französischer Mathematiker.
140 2 Lineare Algebra
Da h(v, v) wegen v 6= 0 eine positive reelle Zahl ist, folgt daraus λ = λ und
somit λ ∈ R wie behauptet.
Zum Beweis von (ii) nutzen wir Induktion über n ≥ 1. Für den Induktions-
anfang bei n = 1 ist nichts zu beweisen. Für den Induktionsschritt nehmen
wir an, die Behauptung sei für Matrizen der Größe n − 1 ≥ 1 bereits be-
wiesen. Aus Teil (i) wissen wir, dass A einen reellen Eigenwert λ besitzt. Sei
vn ∈ Rn ein zugehöriger Eigenvektor. Da auch jedes von Null verschiedene
reelle Vielfache dieses Vektors ein Eigenvektor zum Eigenwert λ ist, können
wir annehmen, kvn k = 1. Die Länge von vn wird hier mit dem Standards-
kalarprodukt des Rn berechnet. Das orthogonale Komplement von vn (siehe
Beispiel 2.4.15)
U = {w ∈ Rn | hvn , wi = 0}
ist ein Unterraum der Dimension n − 1. Dort wollen wir nun die Induktions-
voraussetzung anwenden. Dazu bemerken wir zuerst, dass
Dieser Satz hat vielfältige Anwendungen. Eine dieser Anwendungen ist als
Hauptachsentransformation bekannt. Dabei geht es darum, die Gestalt einer
durch eine quadratische Gleichung gegebenen Menge zu bestimmen.
Beispiel 2.4.28. Die quadratische Gleichung
y2 4
2 y1
1
x1
−4 −3 −2 −1 1 2 3 4 5
−1
−2
−3
−4
Eine zweite Anwendung beschäftigt sich mit der positiven Definitheit sym-
metrischer Matrizen. Eine symmetrische Matrix A = At ∈ Mat(n × n, R)
heißt positiv definit , wenn die Bilinearform hv, wiA = hAv, wi, deren Gram-
sche Matrix gerade A ist, positiv definit ist. Explizit heißt das: v t · A · v > 0
für alle 0 6= v ∈ Rn .
Als unmittelbare Konsequenz des Satzes 2.4.27 erhalten wir, dass eine sym-
metrische Matrix A = At ∈ Mat(n×n, R) genau dann positiv definit ist, wenn
ihre Eigenwerte sämtlich positiv sind. Um das einzusehen, schreiben wir die
aus den Eigenwerten gebildete Diagonalmatrix als D(λ1 , . . . , λn ) = P t ◦ A ◦ P
mit P ∈ O(n). Somit sind die Eigenwerte
λi = ei t · D(λ1 , . . . , λn ) · ei = (P ei )t · A · P ei
Beweis. Wir führen den Beweis per Induktion über n, die Größe der Matrix
A. Für den Start der Induktion bei n = 1 ist nichts zu beweisen. Für den
Induktionsschritt nehmen wir an, dass das Kriterium für Matrizen der Größe
n − 1 bereits bewiesen ist.
Sei nun A positiv definit. Wir haben zu zeigen, dass alle Hauptminoren
von A positiv sind. Die Teilmatrix Ann , die durch Streichung der letzten
Zeile und Spalte aus A hervorgeht, ist ebenfalls positiv definit. Dies folgt
aus der Gleichung y t Ann y = xt Ax, in der y ∈ Rn−1 und x = (y, 0) ∈ Rn
der in der letzten Komponente durch 0 ergänzte Vektor ist. Somit sind die
Hauptminoren von Ann nach Induktionsvoraussetzung positiv. Der einzi-
ge Hauptminor von A, der nicht unter den n − 1 Hauptminoren von Ann
vorkommt, ist det(A). Nach Satz 2.4.27 existiert eine invertierbare Ma-
trix P , so dass P −1 ◦ A ◦ P = D eine Diagonalmatrix ist, deren Einträge
die Eigenwerte von A sind. Daher ist, Q unter Benutzung von Satz 2.4.5,
det(A) = det(P −1 ◦ A ◦ P ) = det(D) = λi > 0. Damit ist gezeigt, dass alle
Hauptminoren von A positiv sind.
Zum Abschluss zeigen wir, dass A positiv definit ist, wenn alle ihre Haupt-
minoren positiv sind. Da die Hauptminoren von Ann unter denen von A
enthalten sind, ist Ann nach Induktionsvoraussetzung positiv definit. Damit
sind die Eigenwerte von Ann positiv. Nach Satz 2.4.27 gibt es eine Basis des
Rn−1 , die aus Eigenvektoren der Matrix Ann besteht. Indem man Rn−1 mit
dem von e1 , e2 , . . . , en−1 aufgespannten Unterraum U von Rn identifiziert,
kann man diese Eigenvektoren als Vektoren v1 , v2 , . . . , vn−1 im Rn auffassen.
Das werden im Allgemeinen keine Eigenvektoren von A sein, aber es gilt
(
0 falls i 6= j
hvi , Avj i = hAvi , vj i =
λi > 0 falls i = j ,
n−1
X
hvn , Avj i = hen , Avj i − xi hvi , Avj i = hAen , vj i − xj λj = 0 .
i=1
Das bedeutet, dass die Gramsche Matrix der durch A definierten symmetri-
schen Bilinearform h·, ·iA bezüglich der Basis (v1 , v2 , . . . , vn ) Diagonalgestalt
besitzt. Wenn P die – im Allgemeinen nicht orthogonale – Matrix bezeichnet,
deren Spalten die Vektoren vi sind, dann ist P t ◦ A ◦ P = D eine Diagonal-
matrix mit Einträgen λ1 , . . . , λn−1 , hvn , Avn i. Daher ist
2
λ1 · . . . · λn−1 · hvn , Avn i = det(P ) det(A) .
Da nach Voraussetzung det(A) > 0 und λi > 0, muss auch λn P := hvn , Avn i >
0 sein. Damit ist für 0 6= y = (y1 , . . . , yn ) ∈ Rn auch y t ·D·y = ni=1 λi yi2 > 0.
t
Weil P ∈ GL(n, R) und (P y) · A · P y = y t · D · y > 0, ist A positiv definit. ⊓ ⊔
Beispiel 2.4.30. Um festzustellen, ob die symmetrischen Matrizen
222 232
A = 2 3 2 bzw. B = 3 2 2
224 224
positiv definit sind, berechnen wir deren Hauptminoren. Im Fall der Matrix
A sind dies 2, det ( 22 23 ) = 2 und det(A) = 4. Die Matrix A ist positiv definit.
Da hingegen det ( 23 32 ) = −5 < 0, ist die Matrix B nicht positiv definit.
Aufgaben
Übung 2.27. Sei σ ∈ Sn eine Permutation (vgl. Beispiel 1.3.3) und P (σ) ∈
Mat(n × n, K) die Matrix deren Einträge aij alle gleich Null sind, außer
15 Alexandre Théophile Vandermonde (1735–1796), französischer Mathematiker.
2.4 Quadratische Matrizen 145
aσ(j)j . Die von Null verschiedenen Einträge sind gleich Eins. Diese Matrizen
nennt man Permutationsmatrizen, da sie aus der Einheitsmatrix 1n durch
Permutation der Zeilen mittels σ entstehen.
Zeigen Sie: P (σ)ek = eσ(k) und P (στ ) = P (σ)P (τ ).
Übung 2.29. Sei sgn(σ) := det(P (σ)), siehe Aufgabe 2.27, das Signum oder
die Parität der Permutation σ ∈ Sn (vgl. Beispiel 1.3.3). Beweisen Sie für
jede Matrix A = (aij ) ∈ Mat(n × n, K) die Formel
X
det(A) = sgn(σ)a1σ(1) a2σ(2) · · · anσ(n) .
σ∈Sn
Dies verallgemeinert die expliziten Formeln für die Determinante aus Beispiel
2.4.2.
Übung 2.30. Benutzen Sie die Cramersche Regel zum Lösen das Systems
2x1 + x2 = 1
−x1 + 2x2 + x3 = −26
x2 + 2x3 = 1 .
0 2 5
Übung 2.34. Bestimmen Sie für die folgenden Matrizen A alle Eigenwerte,
finden Sie jeweils eine Basis aus Eigenvektoren und eine invertierbare Matrix
P , so dass P −1 ◦ A ◦ P Diagonalgestalt besitzt:
2 −4 1 −2
3 −2 1 0 1 0
01 0 −2 0 0
, −1 2 −3 , 1 0 0 und 1 −1 2 −1 .
10
1 2 −5 1 −1 1
−1 1 1 1
200
32 −33
Übung 2.35. Berechnen Sie .
22 −23
Übung 2.41. Sei n > 0 eine positive ganze Zahl. Bestimmen Sie alle Elemen-
te der Ordnung n in der Gruppe SO(2). (Die Ordnung eines Gruppenelements
wurde in Definition 1.3.21 definiert.)
2.5 Fehlerkorrigierende Codes 147
Bei einem Wiederholungscode wird jedes Zeichen n-mal wiederholt. Statt des
Wortes F R E I T A G wird im Fall n = 3 der Text
F F F R B R E E E I I I T T T A A A G G G.
übermittelt. Falls bei der Übermittlung der elektronischen Version dieses Bu-
ches zur Druckerei einer der Buchstaben gestört wurde, können Sie den Fehler
leicht selbst beheben. Wenn von je drei aufeinanderfolgenden gleichen Zei-
chen höchstens eins gestört ist, kann der Text korrekt rekonstruiert werden.
Dieses Verfahren ist nicht besonders effizient, da die dreifache Datenmenge
übermittelt werden muss. Im Folgenden werden wir Verfahren kennenlernen,
die bei einer wesentlich geringeren Datenwiederholungsrate mindestens die
gleichen Korrekturmöglichkeiten bieten.
Für das systematische Studium der Situation und zur Beschreibung der
Codierungsverfahren legen wir zunächst eine klare Sprache fest. Wie be-
reits im Kapitel 1 bezeichnen wir als Alphabet die Menge, aus der die zu
übermittelnden Zeichen stammen. Zur mathematischen Behandlung ordnen
wir den Elementen des Alphabets sogenannte Codeworte zu. Diese Zuord-
nung soll injektiv sein. Anders als im Kapitel 1 ist ein Codewort hier nicht
aus Elementen des Alphabets zusammengesetzt, vgl. S. 39. Wir beschränken
uns hier auf die in der folgenden Definition eingeführten Codes, die auf dem
Körper F2 beruhen. Zum Aufbau der Theorie kann man F2 durch jeden be-
liebigen endlichen Körper ersetzen. Bei praktischen Anwendungen, wie zum
Beispiel beim CD-Spieler, ist das auch tatsächlich notwendig.
Definition 2.5.1. Unter einem Code verstehen wir eine Teilmenge C ⊂ Fn2 .
Die Elemente von C heißen Codeworte. Dabei ist Fn2 = (F2 )n der im Bei-
spiel 2.2.3 eingeführte Vektorraum über dem Körper F2 . Seine Elemente sind
n-Tupel von Nullen und Einsen. Er hat die Dimension n und enthält 2n
Elemente.
Ein einfaches Beispiel für einen solchen Code ist der 128 Zeichen umfassen-
de ASCII-Code. In diesem Fall ist n = 8 und C enthält 27 Elemente. Das
überzählige Bit könnte prinzipiell als Prüfbit verwendet werden, indem es
gleich der Summe der Informationsbits gesetzt wird, vgl. Beispiel 2.5.6. Das
Alphabet besteht aus den Buchstaben des englischen Alphabets und einigen
bei der Benutzung von Computern üblichen Sonderzeichen. Obwohl inzwi-
schen die Verwendung eines Alphabets mit nur 128 Elementen für viele Be-
lange als nicht mehr ausreichend gilt (Internationalisierung, Unicode), spielt
der reine ASCII-Code zum Beispiel innerhalb der Programmierung (ANSI C)
und im Internet (URL) noch immer eine wichtige Rolle. Das zusätzliche Bit
wird heutzutage allerdings für andere Funktionen genutzt.
Etwas abweichend von unserer Definition können wir auch die Menge aller
zulässigen EANs oder ISBNs als Code auffassen. Diese Codes wären, anders
als in der obigen Definition, Teilmengen von (Z/10Z)13 bzw. (Z/11Z)10 = F10 11
und nicht von Fn2 . Im Gegensatz zur Sprechweise in Kapitel 1 wäre hier ent-
sprechend der Definition 2.5.1 jede EAN bzw. ISBN ein Element des jeweili-
gen Alphabets.
2.5 Fehlerkorrigierende Codes 149
Mehr dazu findet der Leser im Abschnitt 2.4 im Zusammenhang mit dem
Begriff des Skalarproduktes. Die wesentlichen Eigenschaften eines derartigen
Abstandsbegriffes sind in der Definition des in der Mathematik etablierten
Begriffes der Metrik zusammengefasst.
Definition 2.5.3. Als Metrik auf einer Menge X bezeichnet man eine Ab-
bildung d : X × X → R, für die für beliebige x, y, z ∈ X gilt:
Br (x) := {y ∈ X | d(x, y) ≤ r} ⊂ X
bc bc bc bc bc bc bc
bc b bc b bc b bc
bc bc bc bc bc bc bc
r
bc b bc b bc b bc
bc bc bc bc bc bc bc
bc b bc b bc b bc
bc bc bc bc bc bc bc
Ein Code C ist genau dann r-fehlerkorrigierend, wenn es keinen Vektor in Fn2
gibt, der von zwei verschiedenen Codeworten höchstens Abstand r hat, das
heißt, wenn für alle u, v ∈ C mit u 6= v
Br (u) ∩ Br (v) = ∅
bc bc bc bc bc bc bc bc bc bc bc
bc bc b bc bc b bc bc b bc bc
bc bc bc bc bc bc bc bc bc bc bc
bc bc bc bc bc bc bc bc bc bc bc
bc bc b bc bc b
r bc bc b bc bc
bc bc bc bc bc bc bc bc bc bc bc
bc bc bc bc bc bc bc bc bc bc bc
Das heißt, bei einem r-perfekten Code wird der Vektorraum Fn2 wie bei ei-
ner Äquivalenzrelation durch die in Codeworten zentrierten Kugeln Br (v)
disjunkt überdeckt. Das ist anstrebenswert, da für einen solchen Code je-
dem empfangenen Wort x ∈ Fn2 ein eindeutig bestimmtes Codewort v ∈ C
zugeordnet werden kann, nämlich dasjenige für welches x ∈ Br (v) gilt.
Aus dieser Beschreibung ergeben sich für jeden Code C die folgenden Impli-
kationen:
r-perfekt =⇒
r-fehlerkorrigierend =⇒ r-fehlererkennend
⇓ ⇓
(r − 1)-perfekt =⇒ (r − 1)-fehlerkorrigierend =⇒ (r − 1)-fehlererkennend.
Lineare Codes
Definition 2.5.5. Ein Code C ⊂ Fn2 heißt linear, falls C ein F2 -Unterraum
von Fn2 ist. Wenn dimF2 C = k, nennen wir C einen linearen (n, k)-Code.
Da sich durch Addition des gleichen Vektors zu u und zu v die Anzahl der
Einträge, an denen sich die zwei Vektoren u und v unterscheiden, nicht ändert,
gilt d(u + w, v + w) = d(u, v). Insbesondere ist d(u, v) = d(u − v, 0). Statt mit
dem Hamming-Abstand zu arbeiten, können wir daher auch das Gewicht
w(v) := d(v, 0)
des Vektors v ∈ Fn2 verwenden. Das Gewicht w(v) ist gleich der Zahl der von
Null verschiedenen Einträge in v. Da jeder lineare Code C den Nullvektor
enthält und mit je zwei seiner Codeworte auch deren Differenz, ergibt sich
aus d(u, v) = w(u − v), dass
gilt. Diese Zahl nennt man das Minimalgewicht des linearen Codes C. Ein
linearer Code mit großem Minimalgewicht hat gute Eigenschaften bei der
Fehlerkorrektur.
Um das angestrebte Ziel zu erreichen, bei der Beschreibung und Decodierung
auf die Benutzung von Tabellen verzichten zu können, erinnern wir uns da-
ran, dass wir Unterräume des Vektorraumes Fn2 auf zwei Weisen beschreiben
können: als Lösungsmenge eines Gleichungssystems oder durch eine Basis.
Die 2k Vektoren eines linearen (n, k)-Codes sind durch die Angabe von k
Basisvektoren vollständig beschrieben. Eine Matrix G ∈ Mat(k×n, F2 ), deren
Zeilen eine Basis eines linearen (n, k)-Codes C bilden, heißt Generatormatrix
dieses Codes.
Wenn C = Lös(H| 0) eine Beschreibung des linearen (n, k)-Codes C als
Lösungsmenge eines Gleichungssystems mit n−k Gleichungen ist, dann heißt
H ∈ Mat((n − k) × n, F2 ) Kontrollmatrix des Codes C. Durch Berechnung
von H · w kann man kontrollieren, ob w ein Codewort ist: w ∈ C ⇐⇒
H · w = 0. Den Vektor H · w ∈ F2n−k nennt man das Syndrom von w, denn
er ist genau dann gleich 0, wenn w ∈ C. Das Syndrom zeigt dem Empfänger
Übertragungsfehler an.
Da die Zeilen einer Generatormatrix G Codeworte sind, gilt für jede Kon-
trollmatrix H stets H ◦ Gt = 0.
In der Sprache der linearen Algebra (Abschnitt 2.2) definiert die Transpo-
nierte der Matrix G eine lineare Abbildung fGt : Fk2 → Fn2 , deren Bildraum
der Code C = im(fGt ) ist. Der Lösungsraum einer Kontrollmatrix H ist der
Kern C = ker(fH ) der linearen Abbildung fH : Fn2 → F2n−k .
Beispiel 2.5.6. Die bereits erwähnte Codierung der 128 ASCII-Zeichen mit
einem zusätzlichen Prüfbit ist ein linearer Code. Da er aus 128 = 27 Co-
deworten in F82 besteht, handelt es sich um einen (8, 7)-Code. Eine Bitfolge
2.5 Fehlerkorrigierende Codes 153
H = (1, 1, 1, 1, 1, 1, 1, 1) ∈ Mat(1 × 8, F2 ) .
Da sowohl eine Basis als auch ein Gleichungssystem für einen linearen Un-
terraum C ⊂ Fn2 nicht eindeutig bestimmt sind, sind wir flexibel bei der
Wahl der Matrizen G und H. Wir nutzen diese Flexibilität, um eine beson-
ders ökonomische Beschreibung linearer Codes zu gewinnen. Wir starten dazu
mit einer beliebigen Kontrollmatrix H ∈ Mat((n − k) × n, F2 ) eines linearen
(n, k)-Codes. Diese Matrix hat Rang n − k, da ihr Kern die Dimension k
hat, vgl. Satz 2.2.28. Anwendung des Gauß-Jordan-Verfahrens auf H liefert
eine Matrix, die in jeder Zeile ein Pivotelement besitzt. Durch Vertauschung
der Spalten erhalten wir daraus eine Matrix, deren erste n − k Spalten die
Einheitsmatrix 1n−k bilden. Die Vertauschung von Spalten verändert nichts
Grundsätzliches an den Eigenschaften des Codes. Durch eine Veränderung
der Identifikation des Alphabets mit den Codeworten kann man eine Spal-
tenvertauschung wieder kompensieren.
Diese Überlegungen zeigen, dass es für jeden linearen (n, k)-Code (nach even-
tueller Spaltenvertauschung) eine Matrix M ∈ Mat((n − k) × k, F2 ) gibt, so
dass die Kontrollmatrix H = (1n−k | M ) ist.
Für solch eine Kontrollmatrix lässt sich die Generatormatrix G leicht berech-
nen. Das liegt daran, dass H bereits in reduzierter Zeilenstufenform vorliegt
und somit eine Basis der Lösungsmenge C = Lös(H| 0) unmittelbar abzulesen
ist. Es ergibt sich hier
G = (−M t | 1k ) = (M t | 1k ) ∈ Mat(k × n, F2 ) .
Beispiel 2.5.7. Der lineare (7, 4)-Code, der durch die Matrix
1101
M = 1 0 1 1 ∈ Mat(3 × 4, F2 )
0111
Da die Generatormatrix G dieses Codes Zeilen mit nur drei Einsen enthält,
ist wmin ≤ 3. Gäbe es ein Codewort v ∈ C, welches höchstens zwei von
Null verschiedene Komponenten hat, dann müsste H zwei linear abhängige
Spalten besitzen, da H · v = 0 für jedes Codewort v. Ein Blick auf H
verrät, dass dies nicht der Fall ist. Daher hat dieser Code das Minimalge-
wicht wmin = 3. Er ist also 1-fehlerkorrigierend und 2-fehlererkennend. Mit
ähnlichen Überlegungen kann man zeigen, dass für jeden linearen (n, k)-Code
stets wmin ≤ n − k + 1 gilt. Dieser Wert wird bei den sogenannten Reed-
Solomon-Codes auch tatsächlich erreicht.
Das zeigt, dass dieser Code wesentlich besser ist als der Wiederholungsco-
de. Es ist eine 3-fach Wiederholung nötig, um einen 1-fehlerkorrigierenden
Code zu erhalten. Bei einem solchen Wiederholungscode werden 4-Bit Zei-
chen durch Codeworte der Länge 3 × 4 = 12 Bits codiert. Mit dem angege-
benen linearen (7, 4)-Code sind zur Codierung von 4-Bit Zeichen nur 7 Bits
notwendig.
2.5 Fehlerkorrigierende Codes 155
Bevor wir uns mit den zyklischen Codes befassen, fragen wir nach linearen
Codes, bei denen sich die Fehlerkorrektur besonders ökonomisch durchführen
lässt. Das wird uns zu den Hamming-Codes führen, die bereits von eindrucks-
voller Qualität hinsichtlich der Vermeidung von Informationsverlust sind.
Jede Kontrollmatrix H eines linearen (n, k)-Codes ist vom Rang n − k. Das
übersetzt sich in die Aussage, dass fH : Fn2 → F2n−k surjektiv ist. Da C =
ker(fH ), besagt der Homomorphiesatz für lineare Abbildungen, Folgerung
2.2.32, dass das Syndrom H · v ∈ F2n−k eines Vektors v angibt, in welcher
Nebenklasse von C ⊂ Fn2 der Vektor v enthalten ist.
Der Fehlervektor e, um den sich das korrekte Codewort c ∈ C und das emp-
fangene Wort v = c + e unterscheiden, hat wegen H · c = 0 das gleiche
Syndrom wie v: Hv = He. Zur Fehlerkorrektur nehmen wir an, dass der
kleinstmögliche Fehler vorliegt. Somit müssen wir das Element kleinsten Ge-
wichts in jeder Nebenklasse bestimmen und dies in geeigneter Weise aus dem
Syndrom ablesen.
Wenn das Syndrom mit einer Spalte der Kontrollmatrix H übereinstimmt,
dann ist der zugehörige Fehlervektor kleinsten Gewichts einer der Standard-
basisvektoren ei . Eine besonders günstige Situation liegt vor, wenn jedes
mögliche Syndrom als Spalte der Kontrollmatrix H auftritt. Das ist bei dem
(7, 4)-Code aus Beispiel 2.5.7 der Fall. Da F32 acht Elemente enthält, gibt
es acht Nebenklassen von C in F72 . Um das Element kleinsten Gewichts in
jeder dieser Nebenklassen zu bestimmen, starten wir mit der Beobachtung,
dass keine zwei der acht Vektoren 0, e1 , e2 , . . . , e7 in der gleichen Nebenklasse
liegen können. Das liegt daran, dass die Differenz zweier Vektoren aus dieser
Liste höchstens vom Gewicht 2, das Minimalgewicht des Codes jedoch gleich
3 ist. Da w(0) = 0 und w(ei ) = 1, sind diese acht Vektoren die gesuchten
Elemente minimalen Gewichts in den jeweiligen Nebenklassen.
Die Fehlerkorrektur kann man deshalb bei dem (7, 4)-Code aus Beispiel
2.5.7 auf die folgende besonders ökonomische Weise durchführen: Wenn das
Syndrom eines Vektors v gleich 0 ist, dann nehmen wir an, es liegt kein
Übertragungsfehler vor. Wenn das Syndrom nicht gleich 0 ist, dann tritt
es als Spalte von H auf, denn die Spalten von H sind genau die von Null
verschiedenen Vektoren von F32 . Wenn das Syndrom die i-te Spalte von H
ist, dann ist der Fehlervektor gleich ei und v ist genau an der Stelle i zu
verändern. Bei einer praktischen Umsetzung wird man die Komponenten der
Codeworte so umsortieren, dass die Kontrollmatrix die Gestalt
1010101
H = 0 1 1 0 0 1 1 ∈ Mat(3 × 7, F2 )
0001111
hat. So geschrieben, stellen die Einträge einer Spalte die Nummer dieser Spal-
te als Binärzahl dar. Das Syndrom Hv ist in diesem Fall bereits gleich der
Nummer der Position, an der v geändert werden muss.
156 2 Lineare Algebra
Die Besonderheit dieses Beispiels besteht darin, dass jeder von Null verschie-
dene Vektor des Vektorraumes F32 als Spalte der Kontrollmatrix H auftritt.
Dies ist der Ausgangspunkt für die folgende Definition.
Dies ist der 3-fach Wiederholungscode. Mit r = 3 erhalten wir den (7, 4)-
Hamming-Code, der in Beispiel 2.5.7 betrachtet wurde. Dieser wurde etwa
1950 von R.W. Hamming entdeckt, siehe [Ha]. Für jedes r ≥ 2 ist der
zugehörige Hamming-Code 1-fehlerkorrigierend und sein Minimalgewicht ist
wmin = 3.
Bemerkung 2.5.9. Zur Quantifizierung der Güte eines Codes kann man die
Wahrscheinlichkeit berechnen, mit der eine bestimmte Datenmenge korrekt
decodiert wird. Dazu nimmt man an, dass ein einzelnes Bit bei der Nach-
richtenübertragung mit Wahrscheinlichkeit p gestört wird. Dann kommt ein
n-Bit Wort mit Wahrscheinlichkeit 1 − (1 − p)n gestört beim Empfänger an.
Wenn ein Hamming-Code benutzt wird, tritt erst dann Informationsverlust
ein, wenn mindestens zwei Bits eines Codewortes gestört sind. Die Wahr-
scheinlichkeit, dass dies bei einem Codewort der Länge n auftritt, beträgt17
Wir müssen jetzt noch berücksichtigen, dass bei einem Hamming-Code von
den übertragenen n = m + r Bits nur m Informationsbits sind. Da die
Wortlänge beim Hamming-Code gleich n = m + r = 2r − 1 ist, enthält jedes
Wort m = n − r = 2r − 1 − r Informationsbits. Die Wahrscheinlichkeit, dass
ein Codewort, welches m Informationsbits enthält, vom Empfänger korrekt
rekonstruiert werden kann, ist somit bei einem (n, m) = (2r − 1, 2r − r − 1)-
Hamming-Code gleich (1 − p)m+r + (m + r)p(1 − p)m+r−1 .
Da m + r = n und da jedes Codewort n − r Informationsbits enthält, ergibt
sich daraus, dass die Wahrscheinlichkeit, dass N Informationsbits mit Hilfe
eines (n, n − r)-Hamming-Codes vom Empfänger korrekt erkannt werden,
n−r
N
(1 − p)n−1 (1 + (n − 1)p)
17 Die mathematischen Grundlagen für diese Rechnungen findet man in Abschnitt 5.2,
insbesondere Beispiel 5.2.7 und Bemerkung 5.2.18.
2.5 Fehlerkorrigierende Codes 157
Zyklische Codes
Für praktische Anwendungen wie zum Beispiel beim Abspielen einer Musik-
CD sind die Hamming-Codes noch nicht ausreichend. Zur Verbesserung kann
man weitere algebraische Strukturen benutzen. Diese Vorgehensweise illus-
trieren wir hier am Beispiel der zyklischen Codes. Für ihr Studium kann die
Ringstruktur des Polynomringes F2 [X] genutzt werden. Die Hamming-Codes
erweisen sich bis auf Spaltenvertauschung als zyklische Codes. Die Beschrei-
bung der für Musik-CDs relevanten Codes würde den Rahmen dieses Buches
sprengen. Am Ende des Kapitels findet der interessierte Leser dazu Litera-
turhinweise.
Die zyklischen Codes sind spezielle lineare Codes. Die Zusatzstruktur erhält
man dadurch, dass der Vektorraum Fn2 durch den Ring
158 2 Lineare Algebra
F2 [X]/hX n − 1i
ersetzt wird. Die Wahl einer Basis des F2 -Vektorraumes F2 [X]/hX n − 1i legt
einen Isomorphismus Fn2 ∼ = F2 [X]/hX n −1i fest. Wir ordnen hier jedem Vektor
Pn−1
(a0 , a1 , . . . , an−1 ) ∈ Fn2 die Restklasse des Polynoms i=0 ai X i ∈ F2 [X] in
F2 [X]/hX n − 1i zu.
Definition 2.5.10. Ein zyklischer Code ist ein Ideal C ⊂ F2 [X]/hX n − 1i.
Diese Codes heißen zyklisch, weil mit jedem Codewort (a0 , . . . , an−1 ) ∈
Fn2 auch jede zyklische Vertauschung (ai , ai+1 , . . . , an−1 , a0 , a1 , . . . , ai−1 ) ein
Codewort ist. Das kommt daher, dass die Multiplikation mit der Restklasse
von X dem zyklischen Verschieben der Einträge um eine Position entspricht.
Dies ist die Grundlage für eine technisch günstige Codierung zyklischer Codes
mittels sogenannter Schieberegister. Mehr dazu erfährt der Leser zum Bei-
spiel in [Sch, S. 138–140].
Da F2 [X] ein Hauptidealring ist (Satz 1.4.17), ist auch jedes Ideal des Ringes
F2 [X]/hX n − 1i von einem Element erzeugt. Das bedeutet, dass zu jedem
zyklischen Code C ⊂ F2 [X]/hX n −1i ein Polynom g ∈ F2 [X] existiert, dessen
Restklasse modulo X n − 1 das Ideal C erzeugt. Wir nennen das Polynom
kleinsten Grades mit dieser Eigenschaft das Generatorpolynom des zyklischen
Codes C. Es ist eindeutig bestimmt, da zwei Polynome gleichen Grades aus
dem Ring F2 [X], von denen jedes ein Vielfaches des anderen ist, bis auf einen
von Null verschiedenen Faktor aus F2 übereinstimmen müssen.
Satz 2.5.11 Das Generatorpolynom g jedes zyklischen Codes ist ein Teiler
von X n − 1 in F2 [X].
Beweis. Da wir modulo X n − 1 rechnen, ist sicher deg(g) < n. Division mit
Rest in F2 [X] liefert eine Darstellung X n − 1 = g · h + r, wobei r, h ∈ F2 [X]
Polynome sind, so dass deg(r) < deg(g). Es folgt g·h = −r in F2 [X]/hX n −1i,
also r ∈ hgi = C. Da g minimalen Grad hat, ist dies nur möglich, wenn r = 0
gilt. Daher ist X n − 1 = g · h und g ist Teiler von X n − 1. ⊓
⊔
Das Generatorpolynom eines zyklischen Codes ersetzt die Generatormatrix
eines linearen Codes. Da in dem Ring F2 [X]/hX n − 1i die Gleichung X n = 1
gilt, können wir jedes Element dieses Ringes auf eindeutige Weise durch
ein Polynom aus F2 [X] vom Grad kleiner als n repräsentieren. Die Re-
präsentanten für die Codeworte aus C = hgi erhält man durch Multiplikation
des Generatorpolynoms g mit den 2k Elementen von F2 [X]≤k−1 , der Menge
aller Polynome, deren Grad kleiner als k = n− deg(g) ist. Dadurch sehen wir,
dass C ein (n, k)-Code ist. Eine Basis von C, betrachtet als F2 -Vektorraum,
wird durch die Codeworte g, Xg, X 2g, . . . , X k−1 g gebildet. Die zugehörige
Generatormatrix für den zyklischen Code mit Generatorpolynom
g = g0 + g1 X + g2 X 2 + . . . + gr X r
2.5 Fehlerkorrigierende Codes 159
F2 [X]/hX n − 1i −→ F2 [X]/hX n − 1i
übereinstimmt. Das heißt, dass f ∈ F2 [X] genau dann ein Codewort ist, wenn
f · h = 0 in F2 [X]/hX n − 1i. Wenn
h = h0 + h1 X + h2 X 2 + . . . + hn−r X n−r ,
X 7 − 1 = (X + 1)(X 3 + X + 1)(X 3 + X 2 + 1) .
Wenn wir
h = (X + 1)(X 3 + X + 1) = X 4 + X 3 + X 2 + 1 und
3 2
g =X +X +1
vom Grad kleiner als n. Die n − r Koeffizienten cn−1 , . . . , cr werden für die
Informationsbits genutzt. Aus ihnen ergibt sich der restliche Teil
p = cr−1 X r−1 + . . . + c1 X + c0
eine vollständige Liste aller Elemente von K ∗ . Insbesondere kommt die Rest-
klasse von X modulo hgi in dieser Liste vor, es gibt somit eine ganze Zahl
1 ≤ e ≤ 2r − 2, für die X = αe in K gilt.
Das Syndrom eines Codewortes f ∈ F2 [X] ist das Bild von f in K = F2 [X]/C.
Da die kanonische Abbildung F2 [X] −→ F2 [X]/C ein Ringhomomorphismus
ist, ist das Syndrom gleich f (αe ) ∈ K. Wenn sich f von einem Codewort
aus C an genau einer Position unterscheidet, sagen wir bei X t , dann ist
f (αe ) = αte . Im Fall e = 1 ist der Fehler besonders leicht zu korrigieren.
Das im Beispiel 2.5.12 betrachtete Polynom g = X 3 + X 2 + 1 für den (7, 4)-
Hamming-Code ist irreduzibel und es gilt e = 1. Das heißt, α ≡ X mod g ist
ein Erzeuger der multiplikativen Gruppe K ∗ . Das Syndrom ist somit gleich
f (α) ≡ f mod g. Die Elemente von K ∗ entsprechen dabei genau den sieben
erzeugenden Monomen 1, X, X 2, . . . , X 6 von F2 [X]/hX 7 − 1i.
Die Codierungstheorie ist ein aktuelles Gebiet, welches die Mathematik eng
mit der Informatik verbindet. Um die Darstellung möglichst einfach zu hal-
ten, haben wir unsere Betrachtungen auf den Körper F2 beschränkt. Ohne
Probleme lässt er sich durch den Körper Fp ersetzen. Außer den in Abschnitt
1.4 studierten Körpern Fp gibt es noch weitere endliche Körper. Bis auf Iso-
2.5 Fehlerkorrigierende Codes 161
Aufgaben
Übung 2.42. Beweisen Sie, dass der Hamming-Abstand (siehe 2.5.2) eine
Metrik auf der Menge Fn2 definiert, das heißt die Eigenschaften (2.20)–(2.23)
besitzt.
Übung 2.43. Zeigen Sie, dass für jeden linearen (n, k)-Code die Ungleichung
wmin ≤ n − k + 1 gilt.
Übung 2.45. Bestimmen Sie alle Erzeuger der multiplikativen Gruppe des
Körpers F2 [X]/hX 3 + X + 1i.
Wir setzen die reellen Zahlen als gegeben voraus. Statt über deren Existenz zu
philosophieren, werden wir zunächst die grundlegenden Eigenschaften der uns
allen wohlbekannten“ reellen Zahlen zusammentragen. Diese Eigenschaften
”
(auch als Axiome bezeichnet) sind so grundlegend, dass sich alles, was wir
über reelle Zahlen sagen werden, daraus ableiten lässt.
Für die Menge der reellen Zahlen hat sich das Symbol R eingebürgert. Die
von ihnen erfüllten Axiome lassen sich in drei Gruppen unterteilen:
• algebraische Eigenschaften,
• Ordnungseigenschaften,
• Vollständigkeitseigenschaft.
165
166 3 Reelle Zahlen und Folgen
Die erste Gruppe grundlegender Eigenschaften der reellen Zahlen besagt, dass
die Menge der reellen Zahlen R ein Körper1 ist. Das bedeutet, dass auf der
Menge R zwei Verknüpfungen definiert sind, die Addition + : R × R → R, die
jedem Zahlenpaar (a, b) ihre Summe a + b zuordnet und die Multiplikation
· : R × R → R, die jedem Zahlenpaar (a, b) ihr Produkt a · b zuordnet. Für
diese Verknüpfungen gelten die folgenden Axiome:
Assoziativgesetze: Für beliebige a, b, c ∈ R gilt
Neutrale Elemente: Es gibt eine Null“ 0 ∈ R und eine von Null verschie-
”
dene Eins“ 1 ∈ R , so dass für jedes a ∈ R gilt:
”
0+a=a und 1 · a = a. (3.2)
a · (b + c) = a · b + a · c. (3.5)
Die größte Schwierigkeit bei solchen Rechnungen, bei denen scheinbar selbst-
verständliche Dinge aneinandergereiht werden, ist, die Übersicht darüber zu
behalten, welche Aussagen benutzt werden dürfen (die Axiome) und welche
der selbstverständlichen“ Aussagen erst gezeigt werden sollen. Weshalb eine
”
derartige Exaktheit sowohl in der Mathematik als auch für die Informatik
von Bedeutung ist, ist im Kapitel 1 ausführlich erläutert.
Eine oft benutzte Folgerung aus den Körperaxiomen ist das allgemeine Distri-
butivgesetz, welches mittels vollständiger Induktion aus (3.5) folgt. Es besagt,
wenn für i = 1, 2, . . . n und j = 1, 2, . . . , m reelle Zahlen ai , bj gegeben sind,
dann gilt:
n
! m n X m
X X X
ai ·
bj = ai · b j . (3.7)
i=1 j=1 i=1 j=1
Im Verlauf dieses Kapitels (Abschnitt 3.3, Satz 3.3.16) werden wir auch
klären, unter welchen Umständen eine solche Aussage für unendlich große
”
n, m“ gilt, und wie dies zu interpretieren ist.
Als Nächstes möchten wir an die Potenzschreibweise erinnern. Für a ∈ R und
n ∈ Z wird die n-te Potenz von a, an , wie folgt erklärt:
a0 : = 1 (auch wenn a = 0)
a1 : = a
n+1
a := a · an für n ≥ 1
a−n : = (a−1 )n für alle a 6= 0 und n ≥ 1.
Die Potenz an ist damit für jede reelle Zahl a 6= 0 und alle n ∈ Z definiert.
Erneut mittels vollständiger Induktion ergeben sich aus dieser Definition die
Potenzgesetze, die für alle a, b ∈ R, a, b 6= 0 und m, n ∈ Z besagen:
an am = an+m
(an )m = an·m
an · bn = (a · b)n .
Jetzt wenden wir uns der zweiten Gruppe grundlegender Eigenschaften zu.
Sie befasst sich mit den Ordnungseigenschaften der reellen Zahlen. Es ist all-
gemein bekannt, dass gewisse reelle Zahlen positiv, andere negativ sind. Auch
dies wollen wir als gegeben voraussetzen. Wenn a ∈ R positiv ist, schreiben
wir a > 0. Wenn −a positiv ist, sagen wir a ist negativ und schreiben a < 0.
Die folgende Notation ist sehr praktisch:
Die grundlegenden Eigenschaften, die der Begriff der Positivität erfüllt, sind
die beiden Anordnungs-Axiome:
168 3 Reelle Zahlen und Folgen
Für jede reelle Zahl a ∈ R gilt genau eine der drei Bedingungen:
a>0 oder a=0 oder a < 0. (3.8)
Aus den Axiomen (3.8) und (3.9) lassen sich einige bekannte Eigenschaften
herleiten.
Beweis. Nach Voraussetzung ist a − b < 0 und b − c < 0, woraus mit (3.9) die
Ungleichung (a − b) + (b − c) < 0 folgt. Das ergibt a − c < 0, d.h. a < c. ⊓
⊔
Beweis. (1) Wir führen eine Fallunterscheidung durch, das heißt, wir unter-
suchen jede der vier Möglichkeiten der Vorzeichen von a und b einzeln. Wenn
a ≥ 0 und b ≥ 0 ist, dann gilt |a| = a, |b| = b und |ab| = ab und damit
3.1 Reelle und komplexe Zahlen 169
|a · b| = a · b = |a| · |b|. Wenn a ≥ 0 ist und b < 0, dann ist ab ≤ 0 und es gilt
|a| = a, |b| = −b, |ab| = −ab. Daraus folgt |ab| = −ab = a · (−b) = |a||b|. Die
anderen beiden Fälle, a < 0 und b ≥ 0 bzw. a < 0 und b < 0, gehen analog.
(2) Da a ≤ |a| und b ≤ |b| folgt mit Eigenschaft (3.10) a + b ≤ |a| + |b|.
Ebenso folgt aus |a| ≥ −a, |b| ≥ −b auch |a| + |b| ≥ −(a + b) und somit
|a + b| ≤ |a| + |b|.
(3) Nach eventueller Vertauschung von a und b können wir o.B.d.A. vorausset-
zen, dass |a| ≥ |b| gilt. Die Dreiecksungleichung für u := a + b, v := −b liefert
|a| = |u + v| ≤ |u| + |v| = |a − b| + |b| und somit |a − b| ≥ |a| − |b| = |a| − |b|.
⊓
⊔
Bemerkung 3.1.4. Ein Körper, in dem es einen Begriff der Positivität gibt,
für den (3.8) und (3.9) gelten, heißt geordneter Körper . Auch Q ist ein ge-
ordneter Körper, aber für C kann man keine solche Ordnung finden, denn,
im Widerspruch zu (3.13), gibt es i ∈ C mit i2 = −1 < 0. Der Begriff des
Betrages ist jedoch übertragbar auf C.
Eine wichtige Zusatzbedingung für die Ordnung auf R wurde bisher noch
nicht erwähnt: R ist ein archimedisch geordneter Körper. Das heißt, dass
zusätzlich zu den Axiomen (3.8) und (3.9) noch das Archimedische Axiom 4
gilt:
Beweis. Wir wenden hier das Prinzip der vollständigen Induktion an.
Induktionsanfang: Für n = 0 erhalten wir auf der linken Seite (1 +a)0 = 1
und 1 + 0 · a = 1 auf der rechten Seite der Ungleichung.
4 Archimedes von Syrakus (ca. 287–212 v.u.Z.), griechischer Mathematiker und Physiker.
5 Hier bezeichnet N = {0, 1, 2, . . . } die Menge der natürlichen Zahlen.
170 3 Reelle Zahlen und Folgen
Induktionsschritt: Wir nehmen an, die Behauptung gilt für ein festes
n ≥ 0 und wollen daraus die Gültigkeit für n + 1 zeigen.
Voraussetzung. (1 + a)n ≥ 1 + n · a für ein n ∈ N.
Behauptung. (1 + a)n+1 ≥ 1 + (n + 1) · a.
Beweis. Da a ≥ −1, ist a+1 ≥ 0 und somit folgt aus der Induktionsvorausset-
zung (1 + a)n+1 ≥ (1 + a)(1 + na) = 1 + a + na + na2 = 1 + (n + 1) · a + n · a2 ≥
1 + (n + 1) · a, da a2 ≥ 0 und n ≥ 0. ⊓
⊔
Beweis. (1) Da a > 1, ist x := a − 1 > 0 und nach Satz 3.1.6 ist daher
an = (1 + x)n ≥ 1 + n · x. Wegen des Archimedischen Axioms (3.16) gibt es
ein n ∈ N mit n · x > K − 1, d.h. an ≥ 1 + nx > K.
(2) Aus 0 < a < 1 folgt b = a1 > 1 und nach (1) gibt es n ∈ N mit bn > K :=
1 n
ε . Wegen