Skriptum Lineare Algebra und Diskrete

Mathematik für die Informatik

Wintersemester 2024/25

Prof. Dr. Thorsten Theobald

 Inhaltsverzeichnis

1. Einleitung 5
Kapitel 1. Lineare Algebra 7
1. Ausgangspunkt der linearen Algebra: Lineare Gleichungssysteme 8
2. Das Eliminationsverfahren von Gauß 15
3. Mathematische Grundbegriffe 24
4. Gruppen und Körper 31
5. Matrizen 35
6. Lineare Abbildungen 44
7. Vektorräume 47
8. Der Rang einer Matrix 54
9. Die Determinante 63
10. Das Skalarprodukt und Orthogonalität 73
11. Eigenwerte 80
12. Singulärwerte 91
Kapitel 2. Diskrete Mathematik 97
1. Zählen 98
2. Die Einschluss-Ausschluss-Formel 100
3. Grundlegendes zu den natürlichen und den ganzen Zahlen 102
4. Die Eulersche ϕ-Funktion 106
5. Der euklidische Algorithmus 110
6. Modulare Arithmetik 117
7. Endliche Gruppen 121
8. Die Ordnung von Gruppenelementen 125
9. Der Chinesische Restsatz 128
10. Das RSA-Kryptographieschema 130
11. Primalitätstests 134

3
4 INHALTSVERZEICHNIS

Vorläufige Version. Es ist vorgesehen, dass das Skript im Laufe des Semesters nach
Erfordernissen noch aktualisiert und ggf. erweitert wird.
Stand: 17. Januar 2025
 1. EINLEITUNG 5

1. Einleitung

Gegenstand dieser Mathematik-Vorlesung im Rahmen des Informatik- und Bioinforma-

tikstudiums sind die folgenden beiden Themenkreise:

Lineare Algebra. Motiviert durch die Strukturen, die sich bei der Behandlung linearer Glei-
chungen ergeben, werden in der linearen Algebra Vektorräume sowie damit in Beziehung
stehende Konzepte untersucht. Die in der linearen Algebra entwickelten Begriffsbildungen
und Strukturen sind zentral in vielen Bereichen der Mathematik.

Diskrete Mathematik. Gegenstand der diskreten Mathematik sind

• endliche Mengen;
• Strukturen, die „diskret“ (im Sinne von separat voneinander) im Raum liegen
(z.B. Z ⊆ R).

Aufgrund der engen Beziehung zu algorithmischen Fragen und zu Computeranwendungen

ist die diskrete Mathematik mit vielen Aspekten der Informatik verzahnt.

In der Vorlesung, die sich an Studierende der Informatik (Bachelor-Studiengang, Lehr-

amt L3) und Bioinformatik (Bachelor-Studiengang) richtet, werden Einführungen in diese
Gebiete gegeben. Gemeinsam mit den anderen Mathematik-Grundvorlesungen für die In-
formatik stellen sie zentrale mathematische Methoden vor, die sowohl in grundlegender
Hinsicht als auch in zahlreichen Teilrichtungen der Informatik von Bedeutung sind.

Ziel der Vorlesung ist es, Zugänge zu einer Reihe von Teilthemen zu geben. Hierbei liegt
in der Regel der Fokus auf zentralen Ideen und Konzepten. Die Darstellung zielt nicht
auf Vollständigkeit ab und es werden auch nicht immer alle Details bewiesen. Im ersten
Teil (Lineare Algebra) ist zudem auch die Behandlung einiger allgemeiner mathematischer
Grundbegriffe integriert.

Überblick:

I. Lineare Algebra

• Ausgangspunkt der linearen Algebra: Lineare Gleichungssysteme

• Das Eliminationsverfahren von Gauß
• Mathematische Grundbegriffe (Mengen, Beweistechniken, Abbildungen)
• Vektoren und Matrizen
• Reelle Vektorräume (Basis und Dimension)
• Determinante
• Lineare Abbildungen und der Dimensionssatz
6 INHALTSVERZEICHNIS

• Skalarprodukt, Normen und Orthogonalität

• Eigenwerte und Eigenvektoren, Diagonalisierbarkeit, Singulärwertzerlegung

II. Diskrete Mathematik

• Der euklidische Algorithmus

• Die Eulersche ϕ-Funktion
• Modulare Arithmetik und endliche Gruppen
• Der Chinesische Restsatz
• Das RSA-Kryptographieschema

Literatur:

• Einführende Lehrbücher zu den Themen Lineare Algebra und Diskrete Mathe-

matik bzw. zur Mathematik für die Informatik (jeweils neueste Auflagen)
– M. Aigner: Diskrete Mathematik (Vieweg)
– J. Liesen, V. Mehrmann: Lineare Algebra (Springer)
– D. Hachenberger: Mathematik für Informatiker (Pearson)
– S. Hetterich: Mathematik für die Informatik I: Lineare Algebra und Diskrete
Mathematik (Analogverlag)
– A. Hoffmann, B. Marx, W. Vogt: Mathematik für Ingenieure 1 (Pearson)
– B. Kreußler, G. Pfister: Mathematik für Informatiker (Springer)
– K. Meyberg, P. Vachenauer: Höhere Mathematik 1 (Springer)
– A. Steger: Diskrete Strukturen (Springer)
– G. Teschl, S. Teschl: Mathematik für Informatiker, Band 1 (Springer)
– ...

Einige dieser Bücher sind an der Goethe-Universität auch als elektronische Versionen
verfügbar.

Einige Teile des Skripts beruhen auf früheren Vorlesungsmaterialien zur „Lineare Alge-
bra und Diskrete Mathematik für die Informatik“ von Prof. Amin Coja-Oghlan. Einige
Bestandteile zu mathematischen Grundlagen sind dem Buch T. Theobald, S. Iliman: Ein-
führung in die computerorientierte Mathematik mit Sage (Springer) entnommen.
 KAPITEL 1

Lineare Algebra

7
8 1. LINEARE ALGEBRA

1. Ausgangspunkt der linearen Algebra: Lineare Gleichungssysteme

Beispiel. In einer Halbleiterfabrik laufen zwei Produktionsprozesse P1 und P2 , die jeweils

die Güter G1 , G2 erzeugen. Pro Zeiteinheit werden in P1
2 Einheiten G1 und 1 Einheit G2
produziert; bei P2 treten
-1 Einheit G1 und 1 Einheit G2
auf. Hierbei steht die negative Zahl dafür, dass in P2 das Gut G1 verbraucht (oder entsorgt)
wird. Wie sind die Produktionsprozesse zu steuern, wenn man genau eine Einheit G1 und
5 Einheiten G2 produzieren will?

In Kurzform können wir die Situation durch die Tabelle

P1 P2 Bedarf
G1 2 −1 1
G2 1 1 5
modellieren. Es ergibt sich das lineare Gleichungssystem
2 · x1 − 1 · x2 = 1 ,
1 · x1 + 1 · x2 = 5 .
Hierbei beschreiben x1 und x2 die Zeitdauern, die die Produktionsprozesse P1 und P2 zu
laufen haben.

Einige naheliegende Fragen zeigen auf, dass bereits verschiedene mathematische Teildis-
ziplinen eine Rolle spielen. Wir nennen hierzu einige Stichworte. Die Stichworte aus Sicht
der linearen Algebra werden im Verlauf der Vorlesung eingehend studiert.

1. Wie kann man lineare Gleichungssysteme lösen?

Lineare Algebra: Eliminationsverfahren von Gauß.

Numerik: → Rundungsfehler.

2. Wie kann man die Menge aller Lösungen charakterisieren?

Lineare Algebra: Vektoren, Vektorräume, lineare Unabhängigkeit.

Geometrie: Geraden, Ebenen, Hyperebenen.

3. Was passiert, wenn man Lösungen über den rellen Zahlen R, über den rationalen Zahlen
Q, über den ganzen Zahlen Z oder Lösungen über {0, 1} sucht?

Lineare Algebra: Körper R, Q (C komplexe Zahlen).

 1. AUSGANGSPUNKT DER LINEAREN ALGEBRA: LINEARE GLEICHUNGSSYSTEME 9

Zahlentheorie: Z .
Kombinatorik: {0, 1} .

Um die Lösung des gegebenenen Gleichungssystems und einige der genannten Aspekte zu
betrachten, formen wir das Gleichungssystem äquivalent um:

2 · x1 − 1 · x2 = 1 (I)
1 · x1 + 1 · x2 = 5 (II)

2 · x1 − 1 · x2 = 1 (I)
−2 · x1 − 2 · x2 = −10 −2 · (II) → (III)

2 · x1 − 1 · x2 = 1 (I)
− 3 · x2 = −9 (I) + (III) → (IV)

2 · x1 − 1 · x2 = 1 (I)
x2 = 3 (IV)/(−3) → (V)

Einsetzen in (I) ergibt dann

2 · x1 − 1 · 3 = 1,
woraus 2x1 = 4 und damit x1 = 2 folgt. Die Lösung (x1 , x2 ) = (2, 3) ist eindeutig.

Fragen: Warum darf man diese Operationen durchführen? Gilt das für R ? Für Q ? Für
Z?

Achtung: In Z darf man im Allgemeinen nicht dividieren, ohne die Menge der ganzen
Zahlen zu verlassen.

Funktioniert das Verfahren auch für allgemeine lineare Gleichungssysteme von m Glei-
chungen in n Variablen?

Geometrische Interpretation. Was für Mengen sind

L1 := {(x1 , x2 ) : x1 , x2 ∈ R und 2 · x1 − 1 · x2 = 1}
und L2 := {(x1 , x2 ) : x1 , x2 ∈ R und 1 · x1 + 1 · x2 = 5}
? Wir können wie folgt umschreiben:
2x1 − 1 · x2 = 1 ⇐⇒ x2 = 2x1 − 1
1 · x1 + 1 · x2 = 5 ⇐⇒ x2 = 5 − x1 .
10 1. LINEARE ALGEBRA

Die Gleichungen können also jeweils als Graph einer linearen Funktion (linearen Abbil-
dung) aufgefasst werden. Die Zuordnung von x1 zum jeweiligen Funktionswert schreiben
wir auch als
x1 7→ 2x1 − 1 ,
x1 7→ 5 − x1 ,
und die zugehörigen Graphen sehen wie folgt aus.

x2
5 L1

1 L2
x1
1 2 3 4 5

Wie wirken die Operationen zur Auflösung des Systems? Nachstehendes Bild zeigt die
Graphen der Gleichungen (VI) bis (V) sowie den mit (VI) bezeichneten Graphen der
Gleichung x1 = 2.

x2
5 (I)

(IV), (V)
3

1 (II), (III)
(VI) x1
1 2 3 4 5
 1. AUSGANGSPUNKT DER LINEAREN ALGEBRA: LINEARE GLEICHUNGSSYSTEME 11

Die Operationen verändern also die Geraden, lassen aber die Lösungsmenge unverändert.
Die Auflösung x1 = 2, x2 = 3 entspricht Geraden parallel zur x2 - und x1 -Achse.

Die Interpretation bezog sich auf die Zeilen eines 2 × 2-Gleichungssystems (2 Gleichungen
in 2 Variablen). Eine andere in der linearen Algebra fundamentale Interpretation bezieht
sich auf die Spalten. Dazu schreiben wir das System in der Form
     
2 −1 1
x1 + x2 = .
1 1 5
   
2 −1
und sind Vektoren des R2 .
1 1

Definition 1.1. Sei n ∈ N. Dann setzt man

  

 v 1 

 v2 
 

n
R :=  ..  : v1 , . . . , vn ∈ R .
 

  .  

 
vn
 

Die Elemente von Rn werden als n-Vektoren (kurz Vektoren) bezeichnet. Die Einträge von
Vektoren heißen Komponenten. Durch
         
u1 v1 u1 + v1 v1 λv1
 ..   ..  ..  .   . 
 . + .  =   und λ ·  ..  =  .. 
 
.
un vn un + vn vn λvn
   
u1 v1
sind für alle  ...  ,  ..  ∈ Rn , λ ∈ R eine Addition und eine Multiplikation mit
  
. 
un vn
einem Skalar definiert.

Geometrische Interpretation. Mit R1 bezeichnen wir die reelle Zahlengerade, mit R2

die reelle Zahlenebene, mit R3 den dreidimensionalen „Anschauungsraum“ usw. Die Vek-
toren
 
v1
 .. 
 . 
vn
können als Punkte dieser Räume interpretiert werden, wenn man ihre Komponenten als
kartesische Koordinaten auffasst.
12 1. LINEARE ALGEBRA

     
1 2 −1
5 =2 · +3
5 1 1

2  
2

−1
 1
1
1

−2 −1 1 2 3 4 5 6

Beispiel. Das Gleichungssystem

2x1 + x2 + x3 = 4 ,
x1 + x2 = 1
kann geometrisch als Durchschnitt zweier Ebenen im R3 interpretiert werden:

x3
 
0
 1 
 
1 3
 0 
2
1

  1 1
3
 −2 
x2
0
x1

Wie nachstehende Rechnungen zeigen, ist der Durchschnitt der Ebenen eine Gerade, die
die oben drei eingezeichneten Punkte enthält. Wir betrachten die rechnerische Auflösung
 1. AUSGANGSPUNKT DER LINEAREN ALGEBRA: LINEARE GLEICHUNGSSYSTEME 13

des Gleichungssystems:
2x1 + x2 + x3 = 4 (I)
x1 + x2 = 1 (II)

2x1 + x2 + x3 = 4 (I)
− x2 + x3 = 2 (−2) · (II) + (I) → (III)

2x1 + x2 + x3 = 4 (I)
x2 − x3 = −2 (−1) · (III) → (IV)
Die Lösung ist jetzt nicht mehr eindeutig bestimmt, sondern eine Gerade im R3 . Sie ist
durch die beiden Gleichungen (I), (IV) bestimmt – ebenso wie durch die ursprünglichen
Gleichungen (I), (II). Nach der Umformung is es aber einfach, eine parametrische Dar-
stellung als Funktion von R nach R3 anzugeben. Als Parameter wählen wir den Wert der
letzten Koordinate x3 und nennen ihn t. Dann ist x3 = t, aus (IV) ergibt sich x2 = −2 + t,
und durch Einsetzen in (I) erhalten wir
1 1
x1 = (4 − x2 − x3 ) = (4 + 2 − t − t)
2 2
= 3 − t.
Der Lösungsraum ist also gegeben durch
  
 3−t 
 −2 + t  : t ∈ R .
t
 

Natürlich können wir diese Gerade auch in der Form

    
 3 −1 
 −2  +  1 t : t ∈ R
0 1
 

schreiben. Wir stellen den Lösungsraum dann dar als Summe einer speziellen Lösung und
einer Geraden durch den Nullpunkt.

Interpretation mittels der Spalten des Systems. In diesem Fall schreiben wir das System
als        
2 1 1 4
x1 + x2 + x3 = .
1 1 0 1
 
4
Die Lösungen beschreiben, auf welche Weise wir den Vektor als Summe von (ggf.
1
     
2 1 1
negativen) Vielfachen der Vektoren , und darstellen können. Wie aus
1 1 0
den vorherigen Rechnungen ersichtlich gibt es viele Möglichkeiten für diese Darstellung.
14 1. LINEARE ALGEBRA

Die Darstellung kann auch als Funktion aufgefasst werden, die einen Vektor (x1 , x2 , x3 )
auf einen zweidimensionalen Vektor abbildet:
 
x1      
 x2  7→ 2 x1 + 1 x2 + 1 x3 .
1 1 0
x3
Interpretiert man dieses Beispiel als Fabrikation, die sich als Kombination von 3 Pro-
duktionsprozessen ergibt, so beschreibt die Abbildung die Paare von Quantitäten von
2 Gütern,
 die erzeugbar sind. Das Gleichungssystem fragt dann nach dem „Urbild“ von
4
. Offenbar ist alles Wesentliche dieser Abbildung ist in der „Tabelle“
1
 
2 1 1
1 1 0
zusammengefasst.
 2. DAS ELIMINATIONSVERFAHREN VON GAUß 15

2. Das Eliminationsverfahren von Gauß

Wir betrachten ein allgemeines m × n-Gleichungssystem

a11 x1 + ··· + a1n xn = b1
.. .. ..
. . .
am1 x1 + · · · + amn xn = bm
mit reellen Koeffizienten aij (1 ≤ i ≤ m, 1 ≤ j ≤ n) sowie bi (1 ≤ i ≤ m). In Summen-
schreibweise lautet das Gleichungssystem
Pn
j=1 a1j xj = b1 ,
.. .. ,
. .
Pn
j=1 amj xj = bm

in Kurzform geschrieben als

n
X
aij xj = bi (1 ≤ i ≤ m).
j=1

In Matrixschreibweise können wir das Gleichungssystem notieren als

Ax = b, wobei
 
a11 · · · a1n
A =  ... ..  (Koeffizientenmatrix),

. 
am1 · · · amn
 
b1
b =  ...  (rechte Seite).
 

bm
Ferner verwenden wir die Schreibweise
 
a11 · · · a1n b1
(A, b) :=  ... .. (erweiterte Koeffizientenmatrix),
 
. 
am1 · · · amn bm
wobei es üblich ist, einen Trennstrich zu schreiben:
 
a11 · · · a1n b1
 .. ..
(A, b) :=  . .

.
am1 · · · amn bm

Die hier verwendeten Notationen einer Matrix und eines Vektors werden wir in späteren
Abschnitten noch als eigenständige Konzepte behandeln. Obige Matrix A lässt sich kurz
16 1. LINEARE ALGEBRA

auch als
A = (aij )1≤i≤m
1≤j≤n

und der Vektor b entsprechend als

b = (bi )1≤i≤m

schreiben.

Mit
Lös(A, b) := {x ∈ Rn : Ax = b}
bezeichnen wir die Lösungsmenge des linearen Gleichungssytems. Jedes Element von Lös(A, b)
heißt Lösung. Das System Ax = b heißt lösbar, wenn Lös(A, b) 6= ∅ ist.

Ziel: Forme das Gleichungssystem äquivalent um, so dass A in Zeilenstufenform (auch:

Treppenform) kommt:
  


 *
∗

*
  

  
r

 ... 

  
  




 * 
 
0 *
  
(  
 
m−r
 

Die mit * markierten Elemente sind ungleich 0, die Elemente unterhalb der „Treppe“
sind 0, die übrigen Elemente ∗ sind beliebig. Mit r sei die Anzahl der Zeilen im oberen
Teil bezeichnet, die von der Nullzeile verschieden sind, und mit m − r sei die Anzahl der
Nullzeilen im unteren Teil bezeichnet.

Definition 2.1. Sei A = (aij )1≤i≤m . A heißt in Zeilenstufenform, wenn folgende Bedin-
1≤j≤n
gungen erfüllt sind:

1. Es gibt ein r ∈ N0 , so dass jede der ersten r Zeilen ein von Null verschiedenes Element
enthält und alle Elemente der letzten m − r Zeilen 0 sind.

2. Für i = 1, . . . , r sei ji := min{j : aij 6= 0}. Dann gilt j1 < j2 < · · · < jr (Stufenbedin-
gung).
 2. DAS ELIMINATIONSVERFAHREN VON GAUß 17

Bemerkung. Der Fall r = 0 ist zugelassen, dieser entspricht der 0-Matrix

 
0 ··· 0
A = 0 :=  ... ..  .

. 
0 ··· 0

Die Elemente a1j , . . . , ar,jr , also die in oben dargestellter Matrix durch * visualierten
Elemente, heißen Pivotelemente.

Beispiel. 1. Die Matrix

 
2 1 1
0 1 −1
ist in Zeilenstufenform mit r = 2 und 1 = j1 < j2 = 2.

2. Die Matrix
 
0 1 0 2 7
 0 0 0 1 0 
0 0 0 0 0
ist in Zeilenstufenform mit r = 2 und 2 = j1 < j2 = 4.

Bemerkung. Durch Umordnung der Spalten, d.h. durch Permutation der Variablen des
Gleichungssystems, kann man eine Matrix in Zeilenstufenform stets in eine Gestalt brin-
gen, so dass j1 = 1, j2 = 2, . . . jr = r gilt.
 
*
* ∗
 
 
 . .


 . 

 
 * 
 

 * 

 0 
 

Man spricht dann von einer kanonischen Zeilenstufenform.

Wir sagen, dass ein Gleichungssystem in Zeilenstufenform ist, wenn die Koeffizientenma-
trix auf der linken Seite in Zeilenstufenform ist.
18 1. LINEARE ALGEBRA

Lösung von Gleichungssystemen in Zeilenstufenform. Nach der voranstehenden

Bemerkung können wir ohne Beschränkung der Allgemeinheit annehmen, dass die erwei-
terte Koeffizientenmatrix (A, b) die Gestalt
 
a11 ··· a1n b1
 0 a
 22 ··· a2n b2  
 . .. .. .. 
 .. . . . 
 
 ..
(1)

 .
 arr · · · arn br  
 0 · · · 0 b r+1

 .. .. .. 
 
 . . . 
0 ··· 0 bm
hat mit aii 6= 0 für i = 1, . . . , r.

Satz 2.2. (A, b) sei in der Form (1). Es gilt genau dann Lös(A, b) 6= ∅, wenn br+1 = · · · =
bm = 0 ist.

Im Einzelnen stecken hinter dieser “genau dann wenn” Aussage die folgenden beiden Teil-
aussagen:

(1) Falls Lös(A, b) 6= ∅, dann gilt br+1 = · · · = bm = 0.

(2) Falls br+1 = · · · = bm = 0, dann gilt Lös(A, b) 6= ∅.

In dem nachstehend ausgeführten Beweis des Satzes werden diese beiden Teilaussagen se-
parat bewiesen. Wir bezeichnen diese beiden Teile des Beweises mit dem Folgepfeil („=⇒“)
und dem rückwärts gerichteten Folgepfeil („⇐=“); im anschließenden Abschnitt über ma-
thematische Grundbegriffe werden diese Bezeichnungen dann noch näher beleuchtet.

Beweis. „=⇒“: Sei x∗ ∈ Lös(A, b) und i ∈ {r + 1, . . . , m}. Dann erfüllt x∗ insbesondere

die i-te Gleichung und es folgt
bi = 0 · x∗1 + 0 · x∗2 + · · · + 0 · x∗n = 0.

„⇐=“: Es gelte nun bi = 0 für i = r + 1, . . . , m. Wir fassen xr+1 , . . . , xn als freie Variable
auf und bestimmen x1 , . . . , xr als Funktionen von xr+1 , . . . , xn aus den Gleichungen
ajj xj + · · · + ajr xr + aj,r+1 xr+1 + · · · + ajn xn = bj
für j = r, r − 1, . . . , 1. Hierzu berechnen wir für l = 0, . . . , r − 1 sukzessive
r n
!
1 X X
x∗r−l := br−l − ar−l,j x∗j − ar−l,j xj .
ar−l,r−l j=r−l+1 j=r+1
 2. DAS ELIMINATIONSVERFAHREN VON GAUß 19

Offenbar liefert jede Setzung von xr+1 , . . . , xn eindeutige Werte x∗r , . . . , x∗1 für xr , . . . , x1 ,
und man erhält eine Lösung. 

Bezeichnung. Die im Beweis verwendete Abbildung φ : Rn−r → Rn , definiert durch

 ∗ 
x1
. 
 .. 
  
xr+1  ∗ 
 xr 
φ  ...  :=   xr+1  ,
  
xn
 
 .. 
 . 
xn
heißt Parametrisierung von Lös(A, b).

Beachte: Per Konvention gilt R0 := {0}, d.h. für r = n gibt es genau eine Lösung wenn
die Bedingungen aus Satz 2.2 erfüllt sind.

Beispiel. Es sei  
1 3 2 1 2
(A, b) = .
0 1 0 1 1
Dann ist also m = 2, n = 4, r = 2. Ferner gilt
x∗2 = 1 − x4 ,
x∗1 = 2 − 3x∗2 − 2x3 − x4 = 2 − 3 + 3x4 − 2x3 − x4
= −1 − 2x3 + 2x4 .
Die Parametrisierung φ ist hier also eine Abbildung R2 → R4 mit
−1 − 2x3 + 2x4
 
 
x3  1 − x4 
φ =  
x4  x3 
x4
−1 −2
     
2
 x3 +  −1  x4 .
 1   0   
=  +
 0   1   0 
0 0 1

Überführung eines Gleichungssystems in Zeilenstufenform. Mit dem nachstehend

beschriebenen Verfahren lässt sich ein Gleichungssystem in eine Zeilenstufenform über-
führen.
20 1. LINEARE ALGEBRA

Definition 2.3. Die folgenden drei Operationen auf einer erweiterten Koeffizientenmatrix
(A, b) heißen elementare Zeilenumformungen.

(I) Vertauschung von zwei Zeilen.

(II) Multiplikation einer Zeile (d.h. jedes Elements der Zeile) mit einer reellen Zahl
λ 6= 0.
(III) Addition einer Zeile zu einer anderen Zeile (komponentenweise).

Lemma 2.4. Die erweiterte Koeffizientenmatrix (Â, b̂) gehe aus (A, b) durch endlich viele
elementare Zeilenumformungen hervor. Dann gilt

Lös(Â, b̂) = Lös(A, b).

Beweis. Es genügt für jede der drei Zeilenumformungstypen (I), (II), (III) zu beobachten,
dass die Lösungsmenge dabei erhalten bleibt. Exemplarisch führen wir dies für Typ (II)
im Detail aus. Hier beobachten wir für den Nachweis der Äquivalenz, dass
n
X n
X
aij xj = bi ⇐⇒ λ aij xj = λbi (da λ 6= 0)
j=1 j=1
n
X
⇐⇒ (λaij )xj = λbi ,
j=1

und die unterste Zeile ist genau die i-te Zeile nach der Zeilenumformung vom Typ (II). 

Satz 2.5. Jedes lineare Gleichungssystem kann durch elementare Zeilenumformungen in

Zeilenstufenform gebracht werden.

Ist A = 0, dann gilt die Behauptung. Sei also im Folgenden A nicht die Nullmatrix.
Wir beweisen den Satz, indem wir einen Algorithmus angeben, der eine gegebene Matrix
erweiterte Koeffizientenmarix (A, b) mittels elementaren Zeilenumformungen in Zeilenstu-
fenform überführt. Da die besondere Bezeichnung b für die letzte Spalte unerheblich ist,
sei zur einfacheren Notation die Gesamtmatrix mit A bezeichnet.

Schritt 1. Sei j1 der Index der am weitesten links stehenden Spalte, die nicht nur aus
lauter Nullen besteht.

Schritt 2. Durch Anwendung von Operation (I), sofern erforderlich, bringe ein von Null
verschiedenes Element in die erste Zeile der Spalte j1 .
 2. DAS ELIMINATIONSVERFAHREN VON GAUß 21

Die Matrix hat nun also die Gestalt

 
0 · · · 0 â1,j1
 0 · · · 0 â2,j ∗ 
1
mit â1,j1 6= 0.
 
 .. .. 
 . . 
0 ··· 0 âm,j1

Schritt 3. Für jedes i = 2, . . . , m addiere das (−âi,j1 /â1,j1 )-fache der ersten zur i-ten Zeile
hinzu (Operationen (II) und (III)).
â i,j1
Dabei geht âi,j1 in âi,j1 − â1,j â1,j1 = 0 über. Die Matrix erhält so die Gestalt
1
 
0 · · · 0 â1,j1 ∗ · · · ∗
 0 ··· 0 0 
 mit â1,j1 6= 0
 
 .. ..
 . . A2 
0 ··· 0 0
und einer Matrix A2 .

Schritt 4. Setze das Verfahren analog mit A2 fort. Nach spätestens m Durchläufen ist
die Matrix in Zeilenstufenform gebracht.

Beispiel.
     
0 1 1 0 1 0 1 1 0 1 0 1 1 0 1
 0 2 2 0 5  →  0 0 0 0 3  →  0 0 2 0 4 ,
0 4 6 0 8 0 0 2 0 4 0 0 0 0 3
wobei im letzten Schritt die Zeilen 2 und 3 getauscht wurden. Es ist j1 = 2, j2 = 3 und
j3 = 5.

Für das Lösen eines linearen Gleichungssystems ergibt sich daher der folgende Algorith-
mus, der als Gaußsches Eliminationsverfahren bezeichnet wird.

1. Bringe (A, b) mittels elementarer Zeilenoperationen auf Zeilenstufenform (Â, b̂).

2. Löse Âx = b̂.

Fragen, die in diesem Zusammenhang aufkommen, und die durch in späteren Abschnitten
eingeführten Konzept erfasst werden, sind:

(1) Wie unterscheiden sich verschiedene Parametrisierungen von Lös(A, b) ?

(2) Welche „Struktur“ hat Lös(A, b) ?
22 1. LINEARE ALGEBRA

Bemerkung. Sei (A, b) die erweiterte Koeffizientenmatrix eines linearen Gleichungssy-

stems. Dann kann (A, b) durch elementare Zeilenoperationen auch auf die Gestalt
 
1 0 0 0
 .. .. 
 1 . . ∗ 
.. .
 

 . 0 .. 

 

 1 0 


 0 1 

 
 

gebracht werden, also mit Einsen an den Stellen, an denen wir lediglich von Null verschie-
dene Elemente forderten, und Nullen in den Spaltenelementen oberhalb dieser Einsen.
Man spricht von einer reduzierten Zeilenstufenform. Die zugehörige kanonische Zeilenstu-
fenform ist dann
 
1 0
..
. ∗
 
 
 
 0 1
.


 
 
 0 0 

Beispiel. Wir schreiben das Gleichungssystem

2x1 + x2 + x3 = 4 ,
x1 + x2 = 1

in Matrixform und bestimmen die reduzierte Zeilenstufenform:

     
2 1 1 4 2 1 1 4 2 1 1 4
→ →
1 1 0 1 0 12 − 12 −1 0 1 −1 −2
   
2 0 2 6 1 0 1 3
→ →
0 1 −1 −2 0 1 −1 −2

In dieser Form lassen sich die Lösungen direkt ablesen:

x1 = 3 − x3 , x2 = −2 + x3 , x3 frei .
 2. DAS ELIMINATIONSVERFAHREN VON GAUß 23

Bemerkung. Ein lineares Gleichungssystem kann in O(n2 m) Rechenoperationen gelöst

werden. Für weitergehende praktische Aspekte zur numerischen Behandlung linearer Glei-
chungssysteme sei zudem auf die Nachfolgevorlesung „Analysis und Numerische Mathe-
matik für die Informatik“ verwiesen.
24 1. LINEARE ALGEBRA

3. Mathematische Grundbegriffe

Für die weiteren Untersuchungen stellen wir zunächst einige mathematische Grundbegriffe
zu Mengen und Abbildungen zusammen. Anhand dieser Konzepte werden auch einige
Aspekte mathematischer Beweise erläutert.

Mengen. Den Begriff der Menge wollen und können wir hier nicht im strengen mathema-
tischen Sinne definieren. Er dient uns nur als Hilfsmittel für eine möglichst kurze Notation
konkreter Mengen. In dieser Situation ist es nützlich und üblich, die Mengendefinition von
Georg Cantor (1845–1918), dem Begründer der Mengentheorie, zum Auftakt seiner be-
rühmten Abhandlung aus dem Jahr 1895 zu zitieren: Unter einer Menge verstehen wir
jede Zusammenfassung bestimmter, wohlunterschiedener Objekte unserer Anschauung oder
unseres Denkens – welche die Elemente der Menge genannt werden – zu einem Ganzen.1

Eine Menge ist definiert oder gebildet, wenn angegeben ist, welche Elemente in ihr enthal-
ten sind. Das kann durch explizite Aufzählung der in ihr enthaltenen Elemente erfolgen,
z.B. {2, 3, 5, 7, 11}, oder durch Angabe einer definierenden Eigenschaft, z.B. {n ∈ N :
n Primzahl}. Wenn das Bildungsgesetz klar ist, können auch unendliche Aufzählungen
verwendet werden, z.B. {3, 6, 9, 12, . . .} Die Kardinalität |M | einer Menge M bezeichnet
die Anzahl der Elemente von M ; im Falle unendlicher Mengen schreibt man |M | = ∞.

Wir verwenden die Notationen

N = {1, 2, 3, . . . , } Menge der natürlichen Zahlen,
N0 = N ∪ {0} Menge der natürlichen Zahlen mit Null,
Z = {.
n . . , −2, −1, 0, 1, 2,o3, . . .} Menge der ganzen Zahlen,
p
Q= q
: p ∈ Z, q ∈ N Menge der rationalen Zahlen.

Aussagen und Quantoren. Mathematische Schlussweisen (und Computerprogramme

natürlich ebenfalls) beruhen auf den Grundprinzipien der mathematischen Logik. Unter
einer Aussage versteht man ein sprachliches oder auf mathematischen Zeichen aufgebau-
tes Gebilde, dem man entweder den Wahrheitswert wahr oder den Wahrheitswert falsch
zuordnen kann. Wir verwenden für diese beiden Wahrheitswerte die Abkürzungen w und
f.

Beispiel.

(1) „17 ist eine Primzahl“ ist eine wahre Aussage.

1Indieser Definition steckt eine gewisse Unschärfe. Je nach Art der Formalisierung kann diese bei
gewissen Mengenbildungen zu Widersprüchen führen, zum Beispiel bei der Russellschen Antinomie: die
Menge aller Mengen, die sich nicht selbst als Element enthalten.
 3. MATHEMATISCHE GRUNDBEGRIFFE 25
√
(2) „ 2 ist eine rationale Zahl“ ist eine falsche Aussage. Wir kommen bei der Be-
handlung von Beweistechniken in Beispiel 3.1 hierauf zurück.
(3) Die Goldbachsche Vermutung „Jede gerade natürliche Zahl größer als 2 kann als
Summe zweier Primzahlen geschrieben werden“ ist entweder eine wahre oder eine
falsche Aussage. Bis heute ist jedoch unbekannt, welchen der beiden Wahrheits-
werte die Aussage hat.
(4) Bei dem Russellschen Paradoxon „Dieser Satz ist falsch.“ handelt es sich nicht um
eine Aussage, da der Satz weder den Wahrheitswert wahr noch den Wahrheitswert
falsch haben kann. 2

Gegenstand der Aussagenlogik ist die Untersuchung einfacher logischer Verknüpfungen

zwischen elementaren Aussagen. Für eine eingehende Betrachtung der Aussagenlogik sei
auf die Vorlesung „Diskrete Modellierung“ verwiesen.

Quantoren. Tritt in einer Formulierung eine Variable auf (z.B. x ≥ 3), dann kann sie
durch einen Quantor „gebunden“ werden. Der Allquantor ∀ und der Existenzquantor ∃
haben die folgende Bedeutung:

∀: „Für alle . . . gilt . . .“

∃: „Es existiert (mindestens) ein . . . mit . . .“

Beispiel. Die Aussage „∀x ∈ R x ≥ 3“ ist eine falsche Aussage, die Aussage „∃x ∈ R x ≥
3“ hingegen hat den Wahrheitswert w. Ferner ist die Aussage „∀x ∈ R (x ≥ 3 =⇒ x2 ≥
9)“ eine wahre Aussage, da für jede konkrete Wahl einer reellen Zahl x die Implikation
„x ≥ 3 =⇒ x2 ≥ 9“ eine wahre Aussage ist.

Beweistechniken. Unter einem Beweis versteht man eine Folge mathematisch korrekter
Schlussfolgerungen, aus denen auf die Gültigkeit einer zu beweisenden Aussage geschlossen
werden kann. Beachten Sie hierbei, dass ein mathematischer Satz oft aus Voraussetzungen
und Behauptungen besteht. Die Argumentation in einem Beweis muss die Gültigkeit der
Behauptungen in all den Situationen nachweisen, in denen die Voraussetzung gilt.

Wir betrachten einige Beweistechniken. Bei einem direkten Beweis startet man von den
gegebenen Voraussetzungen und überführt diese durch eine Folge von Schlussfolgerungen
in die zu zeigende Aussage. Wir werden diesen Beweistyp beispielsweise bei Satz 3.2 weiter
unten sehen.

2MitParadoxa dieser Art hat Bertrand Russell (1872–1970) zu Beginn des 20. Jahrhunderts die zuvor
angenommene These, dass allen Sätzen ein Wahrheitswert zugeordnet werden kann, tief erschüttert.
26 1. LINEARE ALGEBRA

Ein indirekter Beweis beruht auf der Tatsache, dass für zwei Aussagen A und B gilt:

A =⇒ B genau dann, wenn ¬B =⇒ ¬A ,

wobei ¬A die Negation der Aussage A bezeichnet. Hiermit eng verwandt ist der Beweis
durch Widerspruch. Dieser beruht auf der Idee, dass eine Aussage B auf jeden Fall dann
gilt, wenn aus der Aussage ¬B ein Widerspruch hergeleitet werden kann.

Beispiel 3.1. Es soll folgende Behauptung gezeigt werden:

√ √
2 ist irrational (d.h. 2 6∈ Q) .

√
Wir nehmen an, dass 2 ∈ Q und führen diese Aussage zum Widerspruch.
√ √
Im Fall 2 ∈ Q existieren teilerfremde Zahlen p, q ∈ N mit pq = 2. Durch Quadrieren
folgt p2 = 2q 2 , so dass p2 gerade ist. Dann ist aber auch p gerade, d.h., p ist von der Form
p = 2t mit t ∈ N. Es folgt 4t2 = p2 = 2q 2 , also 2t2 = q 2 , so dass aus dem gleichen Grunde
wie zuvor auch q gerade ist. Damit liegt ein Widerspruch zur Teilerfremdheit von p und
q vor.

Teilmengen und Operationen auf Mengen. Eine Menge A heißt eine Teilmenge
einer Menge B, wenn jedes Element von A auch in B enthalten ist. Unter Verwendung
des Symbols :⇐⇒, das den Wahrheitswert des Ausdrucks auf der linken Seite durch den
Wahrheitswert auf der rechten Seite definiert, kann diese Definition formal auch mittels

A ⊆ B :⇐⇒ ∀x ∈ A (x ∈ A =⇒ x ∈ B)

notiert werden. Zwei Mengen sind gleich, wenn sie die gleichen Elemente enthalten, d.h.,

A = B :⇐⇒ (A ⊆ B und B ⊆ A) .

Mit den folgenden Operationen lassen sich zwei Mengen A und B verknüpfen:

A∪B := {x : x ∈ A oder x ∈ B} (Vereinigung) ,

A∩B := {x : x ∈ A und x ∈ B} (Durchschnitt) ,
A\B := {x : x ∈ A und x 6∈ B} (Differenz) ,
A×B := {(a, b) : a ∈ A und b ∈ B} (kartesisches Produkt) .

Wir stellen einige Regeln für Operationen auf Mengen zusammen.

 3. MATHEMATISCHE GRUNDBEGRIFFE 27

Satz 3.2. Für beliebige Mengen A, B, C gelten die folgenden Eigenschaften.

Assoziativität: A ∪ (B ∪ C) = (A ∪ B) ∪ C ,
A ∩ (B ∩ C) = (A ∩ B) ∩ C .
Kommutativität: A∪B = B ∪ A,
A∩B = B ∩ A.
Distributivität: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ,
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) .

Beweis. Wir begnügen uns hier damit, die vorletzte Aussage zu zeigen. Zu zeigen ist:
A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C), (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C) .

Ist x ∈ A ∩ (B ∪ C), dann gilt x ∈ A und x ∈ B ∪ C. Es folgt x ∈ A ∩ B oder x ∈ A ∩ C,

je nachdem, ob x ∈ B oder x ∈ C. Insgesamt ergibt sich x ∈ (A ∩ B) ∪ (A ∩ C).

Ist umgekehrt x ∈ (A ∩ B) ∪ (A ∩ C), dann gilt x ∈ A ∩ B oder x ∈ A ∩ C. Es folgt also

x ∈ A ∩ (B ∪ C). 

Tatsächlich ist jeder Teilschritt des voranstehenden Beweises sowohl im gewöhnlichen

Vorwärtssinn als auch im Rückwärtssinn eine gültige Schlussfolgerung, so dass wir den
Beweis auch mittels Äquivalenzen notierten können:
x ∈ A ∩ (B ∪ C)
⇐⇒ x ∈ A und x ∈ B ∪ C
⇐⇒ x ∈ A ∩ B oder x ∈ A ∩ C.

Hierbei ist darauf zu achten, dass bei der Verwendung von Äquivalenzpfeilen (⇐⇒) eine
Schlussfolgerung in beide Richtungen zu gelten hat. Gilt sie nur in Vorwärtsrichtung,
schreibt man einen Folgepfeil (=⇒). Gilt eine Schlussfolgerung nur in Rückwärtsrichtung,
lässt sich das durch einen rückwärts gerichteten Folgepfeil (⇐=) ausdrücken.

Die Potenzmenge P(M ) einer Menge M ist die Menge aller Teilmengen von M , P(M ) =
{T : T ⊆ M } .

Beispiel. Für A = {a, b, c} ist

P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} .

Für eine endliche Menge M besteht P(M ) aus 2|M | Elementen, so dass man die Potenz-
menge gelegentlich auch mit 2M abkürzt.
28 1. LINEARE ALGEBRA

Abbildungen. Unter einer Abbildung oder einer Funktion von einer Menge A auf eine
Menge B versteht man eine Vorschrift, die jedem Element aus A genau eine Element aus
B zuordnet. Als Schreibweise für eine Funktion dient f : A → B, a 7→ f (a), wobei f (a)
das einem Element a ∈ A zugeordnete Element in B ist. A heißt die Definitionsmenge
und B die Zielmenge der Funktion.

Der Funktionswert f (a) eines Elements a ∈ A wird als Bild von a bezeichnet. Das Urbild
f −1 (b) eines Elements b ∈ B ist definiert als f −1 (b) := {a ∈ A : f (a) = b} . Für X ⊆ A
und Y ⊆ B setze f (X) = {f (x) : x ∈ X} sowie
f −1 (Y ) = {a ∈ A : es existiert ein y ∈ Y mit f (a) = y} .
Definition 3.3. Eine Abbildung f : A → B heißt

(1) injektiv , wenn für alle a, a0 ∈ A mit a 6= a0 gilt f (a) 6= f (a0 ).

(2) surjektiv , wenn für alle b ∈ B ein a ∈ A existiert mit f (a) = b.
(3) bijektiv , wenn f injektiv und surjektiv ist.

Beispiel. 1. Die Abbildung f : N → N, x 7→ x2 ist injektiv, aber nicht surjektiv.

2. Die Abbildung f : Z → N0 , x 7→ |x| ist surjektiv, aber nicht injektiv.

Beispiel. Die Anzahl der Möglichkeiten, n verschiedene Elemente in einer Reihenfol-

ge anzuordnen, beträgt n! . Formal verbirgt sich hinter dieser Aussage der Begriff der
Permutation. Unter einer Permutation einer endlichen Menge M versteht man eine bi-
jektive Abbildung einer Menge auf sich. Ist M = {1, . . . , n}, so erzeugt jede Permutation
σ : M → M eine Anordnung der Zahlen 1, . . . , n, nämlich σ(1), . . . , σ(n). Die Anzahl der
Permutationen einer n-elementigen Menge beträgt n!.

Vollständige Induktion. Das Beweisprinzip der vollständigen Induktion ist in der Ma-
thematik unerlässlich.

Zu jeder natürlichen Zahl n sei eine Aussage A(n) gegeben. Eine Strategie, um die Rich-
tigkeit der Aussage für alle n ∈ N zu beweisen, ist die folgende: Alle Aussagen A(n) sind
richtig, wenn die nachstehenden beiden Eigenschaften bewiesen werden können.

(1) A(1) ist richtig (Induktionsanfang).

(2) Für jedes n, für welches A(n) richtig ist, ist auch A(n + 1) richtig (Induktions-
schluss).

Das Induktionsprinzip reflektiert also einen „Dominoeffekt“. Um alle Steine einer Kette
von Dominosteinen umzuwerfen, muss dafür gesorgt werden, dass der erste Stein umfällt
 3. MATHEMATISCHE GRUNDBEGRIFFE 29

(Induktionsanfang) und jeder beliebige Stein den darauffolgenden umwirft (Induktions-

schluss).

Beispiel. Ein klassisches Beispiel lautet: Für jede natürliche Zahl n gilt die Aussage
1
(2) A(n) : 1 + 2 + 3 + · · · + n = n(n + 1) .
2

Induktionsanfang: Für n = 1 stimmt die Formel.

Induktionsschluss: Es ist zu zeigen, dass unter der Voraussetzung A(n) (Induktionsannah-

me) auch die Aussage A(n + 1) gilt. Dies folgt aus
1 + 2 + · · · + n + (n + 1) = (1 + 2 + · · · + n) + (n + 1)
Ind.-Annahme 1
= n(n + 1) + (n + 1)
2
1
= (n + 1)(n + 2) .
2
Pn Pn
Mit der Kurznotation für Summen k=1 k = 1 + 2 + · · · + n lässt sich (2) als k=1 k=
1
2
n(n + 1) schreiben.

Bemerkung. Tatsächlich lässt sich diese spezielle Summenformel noch eleganter bewei-
sen. Carl-Friedrich Gauß (1777–1855) löste als Kind die Aufgabe, alle Zahlen von 1 bis 100
zu addieren, indem er die 50 gleichen Summen 1+100, 2+99, 3+98, . . . , 50+51 bildete.
Allgemein liefert diese Idee für gerade n die Schlussweise 1 + · · · + n = 12 n(n + 1) und für
ungerade n analog 1 + · · · + n = 21 (n − 1)(n + 1) + 12 (n + 1) = 12 n(n + 1).

Beispiel. Es soll nun per vollständiger Induktion die Summenformel für die ersten n
Quadratzahlen gezeigt werden:
n
X 1
k2 = n(n + 1)(2n + 1) .
k=1
6

Induktionsanfang: Für n = 1 ergibt sich links die Zahl 1 und rechts 61 ·1·(1+1)(2·1+1) = 1,
also stimmt die Formel.
Pn 1
Induktionsschluss: Es ist zu zeigen, dass unter der Voraussetzung k=1 k2 = 6
n(n +
1)(2n + 1) für ein gegebenes n auch
n+1
X 1
k2 = (n + 1)((n + 1) + 1)(2(n + 1) + 1)
k=1
6
30 1. LINEARE ALGEBRA

gilt. Der Induktionsschluss folgt aus

n+1 n
X X Ind.-Annahme 1
k2 = k 2 + (n + 1)2 = n(n + 1)(2n + 1) + (n + 1)2
k=1 k=1
6
1 1
= (n + 1) (n(2n + 1) + 6(n + 1)) = (n + 1)(2n2 + 7n + 6)
6 6
1
= (n + 1)((n + 2)(2n + 3))
6
1
= (n + 1)((n + 1) + 1)(2(n + 1) + 1) .
6
 4. GRUPPEN UND KÖRPER 31

4. Gruppen und Körper

Wir betrachten nun Strukturen, die zu folgenden sowie zu verschiedenen damit zusam-
menhängenden Fragen gehören:

(1) Welche Eigenschaften müssen Zahlsysteme haben, damit über Ihnen das Elimi-
nationsverfahren funktioniert?
(2) Welche Struktur haben Lösungsmengen von linearen Gleichungssystemen?

Beispielsweise funktioniert das Gauß-Verfahren in der beschriebenen Form nicht über den
ganzen Zahlen, da die verwendete Division aus den ganzen Zahlen herausführen kann. Das
Gauß-Verfahren funktioniert sowohl über den reellen Zahlen als auch über den rationalen
Zahlen.

Gruppen. Im Folgenden betrachten wir (nichtleere) Mengen G zusammen mit einer Ver-
knüpfung ∗ : G × G → G. Wir schreiben die Verknüpfüng zweier Elemente in der Regel
als g1 ∗ g2 (und gelegentlich als ∗(g1 , g2 ).)

Beispiel. 1. Einige Beispiele sind (R, +), (R \ {0}, ·), (Z, +), (Z \ {0}, ·), (N, +), (N, ·).

2. Sei X eine (nichtleere) Menge, G die Menge der bijektiven Abbildungen auf X, und
∗ := ◦ die Komposition solcher Abbildungen.

Definition 4.1. Eine nichtleere Menge G mit einer Verknüpfung ∗ : G × G → G heißt

Gruppe, wenn folgende Bedingungen erfüllt sind.

i) ∀a, b, c ∈ G : (a ∗ b) ∗ c = a ∗ (b ∗ c) (Assoziativität) ,
ii) ∃e ∈ G ∀a ∈ G : e ∗ a = a ∗ e = a (neutrales Element) ,
iii) ∀a ∈ G ∃b ∈ G a ∗ b = b ∗ a = e (inverses Element; Schreibweise a−1 ) .

Gilt darüber hinaus Kommutativität (d.h. a ∗ b = b ∗ a ∀a, b ∈ G), dann heißt G abelsch.

Gelten i) und ii), dann heißt (G, ∗) eine Halbgruppe. Eine Gruppe heißt endlich, wenn die
zu Grunde liegende Menge G endlich ist.

Beispiel. Wir betrachten die Mengen und Verknüpfungen aus dem vorangegangenen
Beispiel.

1. (R, +), (R \ {0}, ·) und (Z, +) bilden abelsche Gruppen.

(Z \ {0}, ·) ist keine Gruppe, da nicht jedes Element in Z ein multiplikatives Inverses
in Z besitzt. (N, +) ist keine Gruppe, denn es existiert noch nicht einmal ein neutrales
32 1. LINEARE ALGEBRA

Element. (N, ·) ist keine Gruppe, da nicht jedes Element in N ein multiplikatives Inverses
in N besitzt.

2. Sei wie in dem früheren Beispiel G die Menge der bijektiven Abbildungen auf X, und
∗ := ◦ die Komposition.

Behauptung: (G, ∗) ist eine Gruppe, die sogenannte symmetrische Gruppe auf X.

Das neutrale Element ist die identische Abbildung idX : X → X, die durch idX (x) = x
gegeben ist. Die zu einer Permutation f : X → X inverse Abbildung g = f −1 ist wie folgt
gegeben. Da f bijektiv ist, gibt es zu jedem x ∈ X genau ein y ∈ X mit f (x) = y. Die
inverse Abbildung ist dann durch g(y) = x gegeben. Die Assoziativät gilt, da allgemein
die Komposition von Abbildungen eine assoziative Operation ist; denn für drei beliebige
Abbildungen f, g, h von einer Menge A auf eine Menge B gilt für alle x ∈ A
((f ◦ g) ◦ h)(x) = (f ◦ g)(h(x)) = f (g(h(x))
= (f (g ◦ h))(x) = (f ◦ (g ◦ h))(x) .

Ist X eine endliche Menge, dann sind die bijektiven Abbildungen auf X gerade die Permu-
tationen auf X. Durch Nummerierung der Elemente können wir X dann mit {1, 2, . . . , n}
identifizieren.

Für n ≥ 3 Elemente ist die Menge der Gruppe der Permutationen auf der Menge {1, . . . , n}
nicht abelsch. Beispielsweise lässt sich die Menge der Permutationen auf {1, 2, 3} schreiben
als
           
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
, , , , , ,
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
die folgenden beiden Verknüpfungen (Ausführung aufgrund der Komposition von rechts
her) stimmen jedoch nicht überein:
     
1 2 3 1 2 3 1 2 3
◦ = ,
2 1 3 1 3 2 2 3 1
     
1 2 3 1 2 3 1 2 3
◦ = .
1 3 2 2 1 3 3 1 2

Körper. Wir beginnen mit der Beobachtung, dass beim Rechnen mit reellen Zahlen die
nachstehend aufgeführten Rechenregeln gelten.

Beispiel. Beim Rechnen mit reellen Zahlen gelten für alle x, y, z ∈ R die folgenden
Rechenregeln:
 4. GRUPPEN UND KÖRPER 33

Kommutativität: x + y = y + x und x · y = y · x.
Assoziativität: (x + y) + z = x + (y + z) und (x · y) · z = x · (y · z).
Neutrales Element: 0 + x = x und 1 · x = x.
Distributivität: x · (y + z) = x · y + x · z.
Inverses: Jede reelle Zahl x hat eine negative Zahl −x mit x + (−x) = 0, und zu jeder
reellen Zahl x 6= 0 gibt es ein inverses Element x−1 , so dass x · x−1 = 1.

Als Ausgangspunkt zur Einführung von Körpern beobachten wir, dass (R, +) und (R \
{0}, ·) Gruppen sind und beide Operationen in Gleichungssystemen auftreten. Wir be-
trachten daher Mengen R mit zwei Operationen. Die Operationen seien als „Addition“
und „Multiplikation“ bezeichnet, auch wenn sie mit den gleichnamigen Operationen auf R
nicht in allen Fällen etwas zu tun haben.

Definition 4.2. Eine nichtleere Menge K mit zwei Operationen

+ : K × K → K, · : K × K → K.
heißt Körper, wenn folgende Bedingungungen erfüllt sind.

(1) (K, +) ist eine abelsche Gruppe mit neutralem Element 0 ∈ K.

(2) (K \ {0}, ·) ist eine abelsche Gruppe.
(3) Für alle a, b, c ∈ K gilt das Distributivgesetz a · (b + c) = a · b + a · c.

Das neutrale Element bezüglich der Multiplikation wird mit 1 bezeichnet. Da das additive
neutrale Element 0 nicht in der multiplikativen Gruppe enthalten ist, muss 0 6= 1 gelten.

Beispiel. 1. R und Q sind mit den gewöhnlichen Operationen + und · Körper.

2. Z ist mit den Operationen + und · kein Körper, da (Z \ {0}, ·) keine Gruppe bildet.

3. Die Menge {0, 1} mit der Addition modulo 2 und der Multiplikation modulo 2 bildet
einen Körper.

Lemma 4.3. In jedem Körper K gelten die folgenden Rechenregeln.

(1) Für alle a ∈ K gilt 0 · a = 0.

(2) Aus a · b = 0 folgt a = 0 oder b = 0.

Beweis. Es gilt
a · 0 = a · (0 + 0) = a · 0 + a · 0,
so dass durch Addition von −(a · 0) die erste Aussage folgt.
34 1. LINEARE ALGEBRA

Da (K \ {0}, ·) eine Gruppe bildet, liefert die multiplikative Verknüpfung zweier von
Null verschiedener Elemente ein von Null verschiedenes Element. Hieraus folgt die zweite
Aussage. 
 5. MATRIZEN 35

5. Matrizen

Vektoren und Matrizen sind mathematische Konzepte, die aus der Sicht der Informatik
eng mit dem Datentyp eines arrays in einer Programmiersprache in Beziehung stehen. Bei
einem array werden gleichartige Elemente zusammengefasst. Besitzt jedes Element nur
einen Index, dann entspricht dies dem Konzept eines Vektors. Besitzt jedes Element hin-
gegen zwei Indizes, dann entspricht dies dem Konzept einer Matrix. Vektoren kann man als
Unterklasse von Matrizen auffassen. Matrizen mit Elementen aus den reellen Zahlen ha-
ben wir bei der einführenden Betrachtung von Gleichungssystemen bereits kennengelernt,
um die Koeffizienten eines Gleichungssystems übersichtlich zu notieren.

Im Folgenden gehen wir von einem Körper K aus. Für viele Konzepte des vorliegenden
Abschnitts kann man sich hierbei zur besseren Anschauung zunächst den Fall K = R
vorstellen.

Eine m × n-Matrix ist ein rechteckiges Zahlschema

 
a11 a12 ··· a1n
 a21 a22 ··· a2n 
A = (aij )1≤i≤m =  ..
 
.. .. 
1≤j≤n  . . . 
am1 am2 · · · amn
aus m Zeilen und n Spalten mit Einträgen aij ∈ K für 1 ≤ i ≤ m, 1 ≤ j ≤ n. Wenn die
Anzahl der Zeilen und Spalten klar ist, schreibt man die Matrix auch kurz als (aij ).

Die Einträge der Matrix werden auch als Elemente der Matrix oder Koeffizienten der
Matrix bezeichnet. Ist aij ein Element einer Matrix, dann gibt der erste Index i die Zei-
le an und der zweite Index j die Spalte. Man spricht daher vom Zeilenindex und vom
Spaltenindex. Mit K m×n wird die Menge aller m × n-Matrizen mit Koeffizienten aus K
bezeichnet.

Die m × 1-Matrizen werden auch als Spaltenvektoren und die 1 × n-Matrizen als Zeilen-
vektoren bezeichnet, der jeweils feste Index 1 braucht dabei nicht aufgeführt zu werden.
Ein Vektor mit Einträgen aus K (also ein n-Tupel mit Einträgen aus K) kann also als
Spezialfall einer Matrix betrachtet werden, in der Regel identifizieren wir Vektoren mit
Spaltenvektoren.

Beispiel. Beispiele für Matrizen mit reellen Einträgen sind

 
1 2  
√1 −1 π
3 4 , .
2 79 5
5 6
36 1. LINEARE ALGEBRA

Die Addition zweier m × n-Matrizen A = (aij ) und B = (bij ) ist erklärt als
A + B = (aij + bij )1≤i≤m
1≤j≤n
m×n
und die Menge K aller m × n-Matrizen über K bildet zusammen mit dieser Addition
eine Gruppe. Hierbei ist die Nullmatrix, d.h., die aus lauter Nullen bestehende m × n-
Matrix, das neutrale Element und das zu A = (aij ) inverse Element ist
 
−a11 · · · −a1n
−A = (−aij ) =  ... ... ..  .

. 
−am1 · · · −amn

Die Multiplikation einer Zahl λ mit einer m × n-Matrix A = (aij ) bezeichnet man als
Skalarmultiplikation, und sie ist definiert als
 
λa11 · · · λa1n
λ · A = λ · (aij ) =  ... ... ..  .

. 
λam1 · · · λamn
Oft lässt man den Punkt in der Schreibweise auch weg.

Eine Matrix heißt quadratisch, wenn sie gleich viele Zeilen wie Spalten besitzt. Eine qua-
dratische n × n-Matrix A = (aij )i,j=1,...,n heißt eine Diagonalmatrix, falls aij = 0 für alle
i, j ∈ {1, . . . , n} mit i 6= j. Für gegebene Zahlen d1 , . . . , dn bezeichnet
diag(d1 , . . . , dn )
die Diagonalmatrix mit den Diagonaleinträgen d1 , . . . , dn .

Beispiel. Die n × n-Identitätsmatrix (oder n × n-Einheitsmatrix )

 
1 0 ··· 0 0
0 1 0 0
 
 .. . . .
.
diag(1, . . . , 1) =  .

| {z } . . 
 
n-mal 0 0 1 0
0 0 ··· 0 1
ist eine Diagonalmatrix. Sie wird mit In bezeichnet (auch En ist eine übliche Bezeichnung).
Geht n aus dem Zusammenhang hervor, schreibt man auch einfach kurz I.

Multiplikation von Matrizen. Das Produkt einer m × n-Matrix A mit einer n × p-

Matrix B ist definiert als die m × p-Matrix C mit
Xn
cij = aik bkj (i = 1, . . . , m, j = 1, . . . , p) .
k=1
 5. MATRIZEN 37

Merkregel: „Zeile mal Spalte“.

Beispiel.
       
1 2 5 6 1·5+2·7 1·6+2·8 19 22
· = = .
3 4 7 8 3·5+4·7 3·6+4·8 43 50
Beachte, dass beispielsweise
       
0 1 0 1 0·0+1·0 0·1+1·0 0 0
· = =
1 0 0 0 1·0+0·0 1·1+0·0 0 1
       
0 1 0 1 0·0+1·1 0·1+1·0 1 0
und · = = ,
0 0 1 0 0·0+0·1 0·1+0·0 0 0
die Matrixmultiplikation ist also im Allgemeinen nicht kommutativ.

Es ist        
0 1 1 0 0·1+1·0 0·0+1·0 0 0
· = = ,
0 0 0 0 0·1+0·0 0·0+0·0 0 0
das Ergebnis einer Multiplikation kann also die Nullmatrix sein, obwohl beide Faktoren
von Null verschieden sind.

Auf der Menge der m × n-Matrizen über K ist Im das linksneutrale Element und In das
rechtsneutrale Element, d.h.
Im · A = A und A · In = A für alle A ∈ K m×n .
Beispielsweise ist
     
1 0 1 2 3 1·1+0·4 1·2+0·5 1·3+0·6
· =
0 1 4 5 6 0·1+1·4 0·2+1·5 0·3+1·6
 
1 2 3
= .
4 5 6
Nicht jede m × n-Matrix A über K besitzt ein multiplikatives Linksinverses (d.h. eine
Matrix B mit BA = In ) und nicht jede m × n-Matrix über K besitzt ein multiplikatives
Rechtsinverses (d.h. eine Matrix B mit AB = Im ).

Beispiel. Ist A eine m×n-Matrix und x ∈ K n ein Spaltenvektor, dann lautet das Produkt
Ax:
   
a11 a12 · · · a1n   a11 x1 + a12 x2 + · · · + a1n xn
 a21 a22 · · · a2n  x1  a21 x1 + a22 x2 + · · · + a2n xn 
  .. 
Ax =  .. = .
  
.. ..   .   ..
 . . .   . 
xn
am1 am2 · · · amn am1 x1 + am2 x2 + · · · + amn xn
38 1. LINEARE ALGEBRA

In der bisher nur als Abkürzung verstandenen Schreibweise Ax = b für ein lineares Glei-
chungssystem erhält die linke Seite also die richtige Deutung.

Lineare Abbildungen. Der Zusammenhang zwischen Matrizen und linearen Abbildun-

gen ist zentral in der linearen Algebra. Im Folgenden sei K ein Körper.

Definition 5.1. Eine Abbildung f : K n → K m heißt linear, wenn für alle x, y ∈ K n und
λ ∈ K gilt

(1) f (x + y) = f (x) + f (y) und

(2) f (λx) = λf (x).

Jede m × n-Matrix A über dem Körper K definiert mittels

 
a11 x1 + a12 x2 + · · · + a1n xn
 a21 x1 + a22 x2 + · · · + a2n xn 
x 7→ Ax = 
 
.. 
 . 
am1 x1 + am2 x2 + · · · + amn xn

eine lineare Abbildung K n → K m .

Beispiel. Im Fall m = n = 1 und K = R sind lineare Abbildungen von der Form

f : R → R, x 7→ λ · x für ein λ ∈ R.

Der Graph einer solchen Funktion ist eine Gerade durch den Nullpunkt.

Ein zentraler Grund, warum die Multiplikation genau wie zuvor definiert ist, entspringt
diesem Zusammenhang von Matrizen und linearen Abbildungen. Sei A eine m × n-Matrix
und B eine n × p-Matrix. Dann definieren also die Abbildungen fA : K n → K m , x 7→ Ax
und fB : K p → K n , x 7→ Bx lineare Abbildungen. Die Komposition (Hintereinanderaus-
führung)
K p → K m, x 7→ fA (fB (x)) = A · (B · x)

ist dann ebenfalls eine lineare Abbildung, die wir mit g bezeichnen.

Behauptung: Bezeichnet C := A · B ∈ K m×p das Produkt der Matrizen A und B, dann

lässt sich g als die Abbildung x 7→ Cx beschreiben.
 5. MATRIZEN 39

Nach Definition von g gilt für jedes x ∈ K p

 Pp   Pn Pp 
k=1 b 1k x k j=1 a 1j k=1 b jk x k

g(x) = A · (B · x) = A · 
 .. 
=
 .. 
.   . 
Pp Pn Pp
k=1 bnk xk j=1 amj k=1 bjk xk
 Pp Pn   
k=1 xk j=1 a1j bjk n x1
. aij bjk 1≤i≤m ·  ... 
X 
= 
 ..  =
  
Pp Pn j=1 1≤k≤p
k=1 xk j=1 amj bjk xp
= C · x.

Man kann das so auffassen, dass die Matrixmultiplikation deshalb oben genau wie angege-
ben definiert wurde, damit das Produkt C := A·B zweier Matrizen A und B die Hinterein-
anderausführung der zugeordneten linearen Abbildungen fA : x 7→ Ax und fB : x 7→ B(x)
beschreibt, also für die Hintereinanderausführung g(x) = fA (fB (x)) gerade g(x) = Cx
gilt.

Die beiden nachstehenden Lemmas lassen sich unmittelbar nachrechnen.

Lemma 5.2. (Assoziativitätsgesetz der Matrixmultiplikation.) Seien A, B, C Matrizen
der Größen ` × m, m × n und n × p. Dann gilt
(A · B) · C = A · (B · C) .
Lemma 5.3. (Distributivgesetze der Matrixmultiplikation.) Seien A, B, C, D Matrizen
der Größen ` × m, m × n, m × n und n × p. Es gelten die Distributivgesetze
A · (B + C) = A · B + A · C
und (B + C) · D = B · D + C · D .
Definition 5.4. Sei A = (aij )i,j eine m × n-Matrix. Die transponierte Matrix A> ist die
n × m-Matrix
 
a11 · · · am1
A> = (aji ) j=1,...,n =  ... .. ..  .

. . 
i=1,...,m
a1n · · · amn

Anstatt A> (mit dem speziellen gesetzten Exponenten >) verwendet man auch die Schreib-
weise AT (mit dem gewöhnlichen Buchstaben T ).

Beispiel.
   >
 > 1 4 1  >  
1 2 3
1 0 1 0
= 2 5  , 2 = 1 2 3 , = .
4 5 6 0 1 0 1
3 6 3
40 1. LINEARE ALGEBRA

Die inverse Matrix. Wir haben oben die Matrixmultiplikation eingeführt. Es stellt
sich die Frage, ob es auch eine Matrixdivision gibt? In den reellen Zahlen kann man
eine Division durch eine Zahl a 6= 0 als Multiplikation mit dem multiplikativen Inversen a1
ausdrücken. Auf der Menge der quadratischen n×n-Matrizen lässt sich das Konstrukt einer
Inversenbildung verallgemeinern, wobei es hierbei außer der Nullmatrix weitere Matrizen
gibt, für die kein Inverses existiert.
Definition 5.5. Sei A eine n × n-Matrix über dem Körper K. A heißt invertierbar, wenn
es eine Matrix B ∈ K n×n gibt mit
AB = BA = In .
Wir nennen B dann die zu A inverse Matrix und bezeichnen sie mit A−1 .
Lemma 5.6. Sind A und B zwei invertierbare n × n-Matrizen, dann ist auch A · B
invertierbar und es gilt
(A · B)−1 = B −1 · A−1 .
Ferner ist A−1 invertierbar und es gilt (A−1 )−1 = A.

Beweis. Für die Matrix Z := B −1 A−1 gilt

Z · (A · B) = B −1 A−1 AB = B −1 B = In ,
also ist Z ein Inverses zu A · B.

Wegen A · A−1 = In ist A ein Inverses zu A−1 . 

Bemerkung. Die inverse Matrix ist eindeutig bestimmt. Sind B und C zwei n × n-
Matrizen mit AB = BA = In und AC = CA = In , dann ist
B = In B = (CA)B = C(AB) = CIn = C .
Dieses Argument lässt sich in gleicher Weise zum Nachweis der Eindeutigkeit inverser
Elemente in beliebigen Gruppen verwenden.

In ähnlicher Weise gilt: Bei der Bestimmung von A−1 genügt es, eine Matrix B zu finden,
die eine der beiden Gleichungen AB = In oder BA = In erfüllt. Die andere Beziehung
ist dann automatisch erfüllt. Gilt A−1 A = In , dann folgt, dass das Element Z := A · A−1
(ebenfalls) das neutrale Element bezüglich der Matrixmultiplikation sein muss, denn nach
dem voranstehenden Lemma ist Z invertierbar mit
Z = In Z = (Z −1 Z)Z = Z −1 · (Z · Z) = Z −1 · Z = In .
| {z }
(A·A−1 )·(A·A−1 )
 5. MATRIZEN 41

Also ist Z = In .

Die Bestimmung einer Matrix B mit AB = In können wir als n lineare Gleichungssysteme
interpretieren,
Ab(i) = e(i) , 1 ≤ i ≤ n,
wobei b(i) die i-te Spalte der zu bestimmenden Matrix B ist und e(i) der i-te Einheitsvektor.
Es ergibt sich der folgende Satz, wobei (b(1) , . . . , b(n) ) die Matrix mit Spalten b(1) , . . . , b(n)
bezeichnet.
Satz 5.7. (Bestimmung der Inversen einer n × n-Matrix A.) Besitzt eine Matrix A eine
Inverse, dann sie durch (b(1) , . . . , b(n) ) gegeben, wobei b(i) die Lösung des Gleichungssystems
Ab(i) = e(i) ist, 1 ≤ i ≤ n.

Die inverse Matrix lässt sich wie folgt geschickt mittels simultaner linearer Gleichungssy-
steme berechnen. Für eine gegebene n × n-Matrix A bildet man die n × (2n)-Matrix
(A In ) ,
die wir zweckmäßig mit einem Trennstrich als
(A | In )
schreiben. Durch elementare Zeilenumformungen wird (sofern möglich) diese Matrix in
die Matrix
(In | B)
übergeführt. Dann ist A−1 = B. Falls eine Überführung in die Form (In | B) nicht möglich
ist, ist A nicht invertierbar.

Beispiel. Sei
 
−1 1 1
A =  1 −2 1 .
1 1 −3
Wir bilden die 3 × 6-Matrix
 
−1 1 1 1 0 0
 1 −2 1 0 1 0 
1 1 −3 0 0 1
und bringen sie zunächst in Zeilenstufenform:
   
−1 1 1 1 0 0 −1 1 1 1 0 0
 0 −1 2 1 1 0  −→  0 −1 2 1 1 0 .
0 2 −2 1 0 1 0 0 2 3 2 1
42 1. LINEARE ALGEBRA
 
1 0 0
Um die ersten drei Spalten in die Form I3 =  0 1 0  zu überführen, werden weitere
0 0 1
elementare Zeilentransformationen verwendet:
   
−1 1 1 1 0 0 −1 1 1 1 0 0
 0 −1 2 1 1 0  −→  0 −1 0 −2 −1 −1 
3 1 3 1
0 0 1 2
1 2
0 0 1 2
1 2

− 12 −1 − 21 − 12 −1 − 12
   
−1 1 0 −1 1 0
−→  0 −1 0 −2 −1 −1  −→  0 1 0 2 1 1 
3 1 3 1
0 0 1 2
1 2
0 0 1 2
1 2

− 52 −2 − 32 5 3
   
−1 0 0 1 0 0 2
2 2
−→  0 1 0 2 1 1  −→  0 1 0 2 1 1 
3 1 3
0 0 1 2
1 2
0 0 1 2
1 12
Die inverse Matrix lautet daher
5
2 23

2
A−1 = 2 1 1 .
3
2
1 21
Zur Probe rechnen wir A−1 · A:
5
2 32
    
2
−1 1 1 1 0 0
 2 1 1  ·  1 −2 1  = 0 1 0 .
3
2
1 12 1 1 −3 0 0 1

Es gelten die folgenden Rechenregeln für invertierbare quadratische Matrizen.

Lemma 5.8. Seien A eine invertierbare n × n-Matrix. Dann gilt:

1. A> invertierbar und es ist

(A> )−1 = (A−1 )> .

2. Falls u, y ∈ Rn Spaltenvektoren mit Au = y sind, dann ist

u = A−1 y .

Beweis. 1. Mit der Rechenregel zum Transponieren eines Produkts ist

(A−1 )> · A> = (A · A−1 )> = In> = In ,
also ist (A−1 )> die inverse Matrix zu A> .

2. Es ist A−1 y = A−1 (Au) = A−1 Au = u. 

 5. MATRIZEN 43

Aus den Eigenschaften dieses Abschnitts ergibt sich, dass die Menge der invertierbaren
n × n-Matrizen über dem Körper K mit der Matrixmultiplikation eine Gruppe bildet. Sie
heißt die allgemeine lineare Gruppe vom Grad n und wird kurz als GL(n, K) bezeichnet
(vom englischen Begriff general linear group). Für jeden Körper K und jedes n ≥ 2 ist
die Gruppe GL(n, K) nicht abelsch.
44 1. LINEARE ALGEBRA

6. Lineare Abbildungen

Wie wir bereits im vergangenen Abschnitt in erster Näherung gesehen haben, hängen Ma-
trizen eng mit dem Begriff der linearen Abbildungen zusammen. Als konkrete Beispiele
für lineare Abbildungen seien Drehungen, Spiegelungen, Streckungen und Stauchungen
genannt. In der Informatik treten lineare Abbildungen daher in sehr expliziter Form bei-
spielsweise in der Computergrafik auf. Als weitere Anwendungen linearer Abbildungen
(über Körpern mit endlich vielen Elementen) in der Informatik seien beispielsweise linea-
re Codes genannt, die jedoch über die vorliegende einführende Darstellung hinausgehen.

Wir erinnern uns an die Definition aus dem vergangenen Abschnitt, wobei wir uns hier der
Einfachheit halber auf den Körper K = R der reellen Zahlen beschränken. Eine Abbildung
f : Rn → Rm heißt linear, wenn für alle x, y ∈ Rn und λ ∈ R gilt

(1) f (x + y) = f (x) + f (y) und

(2) f (λx) = λf (x).

Wir betrachten m × n-Matrizen über den rellen Zahlen. Wie zuvor gesehen definiert jede
m × n-Matrix A eine lineare Abbildung

f : Rn → Rm , x 7→ Ax .

Umgekehrt existiert zu jeder linearen Abbildung f : Rn → Rm eine Matrix A ∈ Rm×n

mit f (x) = Ax. Denn aufgrund der Linearität ist durch die Bilder der Einheitsvektoren
     
1 0 0
 0   1   0 
e(1) =  ..  , e(2) =  ..  , . . . , e(n) =  .. 
     
 .   .   . 
0 0 1

bereits die gesamte Abbildung erklärt. Setze die i-te Spalte von A daher auf f (e(i) ),
1 ≤ i ≤ n. Aufgrund dieser gegenseitigen Überführbarkeit können relevante Konzepte
daher sowohl als Aussagen über Matrizen als auch als Aussagen über lineare Abbildungen
formuliert werden. Wir verwenden hier überwiegend die Sprache der Matrizen.

Drehungen und Spiegelungen. Als interessante theoretische und praktische Anwen-

dung linearer Abbildungen betrachten wir Drehungen und Spiegelungen. Diese Operatio-
nen sind beispielsweise bei Problemen der Computergrafik von großer Bedeutung. Beim
Verändern der Position eines Beobachters verändert sich die Perspektive des betrachteten
Objekts. Es sind nun die Koordinaten des gedrehten Objekts zu berechnen. Wir konzen-
trieren uns hier vorwiegend auf den Fall des R2 .
 6. LINEARE ABBILDUNGEN 45

Sei F : R2 → R2 die Drehung eines Ortsvektors (x, y) ∈ R2 um einen festen Winkel im

Gegenuhrzeigersinn um den Ursprung. Wir überlegen uns zunächst, dass diese Abbildung
linear ist. Zum einen ist es gleichgültig, ob wir zwei Vektoren a und b zuerst addieren
und dann den Summenvektor drehen oder ob wir zuerst die beiden Vektoren a und b
drehen und danach die Summe der gedrehten Vektoren bestimmen. Zum anderen ist es
auch gleichgültig, ob wir einen Vektor vor oder nach der Drehung mit einem Faktor λ
strecken.

Die Matrix A, die die Drehabbildung F beschreibt, finden wir aufgrund der Lineari-
(1) (2)
tät durch  Anwendung
 der Drehung  auf die beiden Einheitsvektoren e und e . Es ist
cos α − sin α
F (e(1) ) = und F (e(2) ) = .
sin α cos α

Wir können diese Matrixbeschreibung wie folgt festhalten.

Satz 6.1. Für α ∈ R wird die Drehung des Punktes (x, y) ∈ R2 mit dem Drehwinkel α
gegen den Uhrzeigersinn um den Ursprung durch die lineare Abbildung
    
2 2 x cos α − sin α x
Dα : R → R , 7→
y sin α cos α y
beschrieben.

Analog wird im R3 eine Drehung um den Winkel α gegen den Uhrzeigersinn um die x-,
y- bzw. z-Achse beschrieben durch
   
1 0 0 cos α 0 − sin α
Ax =  0 cos α − sin α  , Ay =  0 1 0 ,
0 sin α cos α sin α 0 cos α
 
cos α − sin α 0
Az =  sin α cos α 0  .
0 0 1

(Hinweis: Ax und Az ergeben sich kanonisch für ein „Rechtssystem“ im Sinne der Rechte-
Hand-Regel. Bei Ay sind wir etwas vereinfachend davon ausgegangen, dass wir die neue
Koordinate so orientieren, dass sich auch hier die zweidimensionale Drehmatrix als Un-
termatrix ergibt; falls ein Rechtssystem gefordert ist, dann ist in Ay der Winkel α durch
−α zu ersetzen.)

Spiegelungen. Eine weitere Klasse geometrischer Operationen in der Ebene wird durch
Spiegelungen an einer Geraden definiert. Analog zur Drehungsaussage ergibt sich die fol-
gende Aussage.
46 1. LINEARE ALGEBRA

Satz 6.2. Für α ∈ R wird die Spiegelung an der Geraden

  
 α α > α α >
R · cos , sin := λ · cos , sin :λ∈R
2 2 2 2
durch die lineare Abbildung
    
2 2 x cos α sin α x
Sα : R → R , 7→
y sin α − cos α y
beschrieben.

Beispiel. Für einen gegebenen Winkel α betrachten wir die Spiegelung an der Achse
R(cos α2 , sin α2 )> . Der Punkt (cos α2 , sin α2 )> liegt auf der Spiegelachse. Sein Bild unter der
Spiegelungsabbildung ist
cos α · cos α2 + sin α · sin α2 cos α2
   
=
sin α · cos α2 − cos α · sin α2 sin α2
aufgrund der Identitäten sin(x − y) = sin x cos y − cos x sin y und cos(x − y) = cos x cos y +
sin x sin y.
 7. VEKTORRÄUME 47

7. Vektorräume

Die Eigenschaften linearer Gleichungssysteme sowie die Struktur ihrer Lösungsmengen

führt auf den in dem vorliegenden Abschnitt eingeführten Begriff des Vektorraums.

Wie bereits früher in Zusammenhang mit Matrizen und Vektoren erläutert, können wir
Skalare aus einem beliebigen Körper K zur Multiplikation von Vektoren zulassen. Im
Folgenden sei ein Körper K fixiert, als Beispiele kann man sich K = R, K = Q oder
den Körper K = C der komplexen Zahlen vorstellen. Die nachstehende Definition eines
Vektorraums führt nun den Begriff des Vektors in abstrakterer Weise ein, der als Spezialfall
die bereits bekannten Vektoren aus dem Rn beinhaltet, aber darüber hinausgeht.

Definition 7.1. Eine nichtleere Menge V zusammen mit zwei Verknüpfungen

+ : V ×V →V (Addition von Vektoren)
und · : K ×V →V (Skalarmultiplikation)
heißt Vektorraum über dem Körper K, wenn die folgenden Bedingungen erfüllt sind.

(1) (V, +) ist eine abelsche Gruppe.

(2) Für alle v, w ∈ V und λ, µ ∈ K gilt
(λµ) · v = λ · (µ · v),
(λ + µ) · v = λ · v + µ · v,
λ · (v + w) = λ · v + λ · w,
1·v = v.

Die Elemente von V werden Vektoren genannt.

Ein Vektorraum über einem Körper K wird kurz auch als K-Vektorraum bezeichnet. Das
neutrale Element 0 der additiven abelschen Gruppe heißt Nullvektor. Das additive Inverse
eines Vektors v ∈ V wird wie gewöhnlich als −v geschrieben.

Beispiel. 1. Für jede natürliche Zahl n ≥ 1 ist die Menge der n-Tupel
K n := {(x1 , . . . , xn ) : xi ∈ K für i = 1, . . . , n}
ein K-Vektorraum, wenn die Addition und die Skalarmultiplikation durch
(x1 , . . . , xn ) + (y1 , . . . , yn ) := (x1 + y1 , . . . , xn + yn ) und
λ · (x1 , . . . , xn ) := (λx1 , . . . , λxn )
erklärt werden. Oft werden die Elemente von K n als Spaltenvektoren interpretiert, aus
Platzgründen schreibt man sie manchmal auch als Zeilenvektoren.
48 1. LINEARE ALGEBRA

Im Fall K = Rn sind das genau die Vektorräume, die wir bereits bei der Behandlung
linearer Gleichungssysteme über den reellen Zahlen gesehen haben.

2. Die Menge Mat(m×n, K) aller m×n-Matrizen mit Einträgen aus K (auch kurz K m×n )
bildet einen K-Vektorraum, wenn die Addition und die Skalarmultiplikation komponen-
tenweise definiert sind. Das heißt, für Matrizen A, B ∈ Mat(m × n, K) und λ ∈ K ist
C := A + B durch cij = aij + bij und D := λA durch dij = λaij für alle i ∈ {1, . . . , m}
und j ∈ {1, . . . , n} erklärt.

3. Sei K = R und A ∈ Mat(m × n, R). Dann ist die Lösungsmenge Lös(A|0) ⊆ Rn des
linearen Gleichungssystems Ax = 0 ein R-Vektorraum. Für 0 6= b ∈ Rm ist Lös(A|b) kein
Vektorraum, da 0 6∈ Lös(A|b).

4. Für ein gegebenes d ∈ N0 ist die Menge der Polynome (“ganzrationale Funktionen”) in
der Variablen x mit reellen Koeffizienten und Grad höchstens d bezüglich der gewöhnlichen
Addition von Polynomen und der Multiplikation eines Polynoms mit einem Skalar ein R-
Vektorraum. Die Koeffizienten eines Polynoms vom Grad höchstens d können auch als
Vektor im Vektorraum Rd+1 betrachtet werden.

5. Die Menge aller Polynome in x mit reellen Koeffizienten bildet einen R-Vektorraum.

6. Die Menge aller reellen Folgen (xn )n≥1 bildet einen R-Vektorraum.

7. Wir bezeichnen mit Abb(R, R) die Menge aller Abbildungen f : R → R. Die Additi-
on f + g zweier Funktionen und die Skalarmultplikation λf mit einem Skalar λ werden
punktweise erklärt:

(f + g)(x) = f (x) + g(x) und (λf )(x) = λ · f (x) für x ∈ R .

Dann bildet Abb(R, R) mit diesen beiden Operationen einen R-Vektorraum.

Bemerkung. 1. Für das Produkt 0 · v des neutralen Körperelements 0 mit einem Vektor
v ergibt sich der Nullvektor 0, den wir in dieser Bemerkung zur besseren Unterscheidung
als 0 schreiben. Um die Eigenschaft aus obigen Axiomen herzuleiten, verwenden wir die
Neutralität des Körperelements 0 sowie eines der Distributivgesetze des Vektorraums, um

0 · v = (0 + 0) · v = 0 · v + 0 · v

zu erhalten. Durch Subtraktion von 0 · v auf beiden Seiten ergibt sich 0 = 0 · v.

2. Für das Produkt aus dem Körperelement −1 und einem Vektor v ergibt sich

(−1) · v = −v.
 7. VEKTORRÄUME 49

Denn nach obigen Axiomen sowie des ersten Teils der Bemerkung ist

v + (−1) · v = 1 · v + (−1) · v = (1 + (−1))v

= 0,

so dass sich aus der additiven Gruppenstruktur die Behauptung ergibt.

Definition 7.2. Eine nichtleere Menge U ⊆ V eines K-Vektorraums V heißt Untervek-

torraum (kurz Unterraum), wenn für alle u, v ∈ U und alle λ ∈ K stets u + v ∈ U und
λ · u ∈ U gilt.

Ist U ⊆ V ein Unterraum, dann bildet U zusammen mit den auf ganz V erklärten Ope-
rationen + und · einen Vektorraum. Beispielsweise ist der in obigem Beispiel behandelte
Lösungsraum Lös(A|0) des rellen Gleichungssystems Ax = 0 ein Unterraum des Rn .

Die nachstehenden Konzepte befassen sich damit, auf welche Weise ein Unterraum, etwa
der Lösungsraum eines linearen Gleichungssystems, durch eine Teilmenge von Vektoren
dieses Unterraums dargestellt werden kann.

Definition 7.3. Ein Vektor v ∈ V in einem K-Vektorraum V heißt Linearkombination

der Vektoren v1 , . . . , vr ∈ V , wenn es Zahlen λ1 , . . . , λr ∈ K gibt mit
r
X
v = λi vi .
i=1
Pr
Die Menge Lin(v1 , . . . , vr ) := { i=1 λi vi : λ1 , . . . , λr ∈ K} aller Linearkombinatio-
nen der Vektoren v1 , . . . , vr heißt lineare Hülle von v1 , . . . , vr . (Alternative Notation z.B.
span(v1 , . . . , vr ), aus der englischsprachigen Literatur). Per Konvention ist Lin(∅) = {0}.

Aus der Definition ergibt sich unmittelbar, dass Lin(v1 , . . . , vr ) ein Unterraum des Vektor-
raums V ist. Detaillierter beschrieben ist die lineare Hülle der (bezüglich Mengeninklusion)
kleinste Unterraum, der die Vektoren v1 , . . . , vr enthält, denn jeder Unterraum U ⊆ V , der
v1 , . . . , vr enthält, enthält nach den definierenden Vektorraumeigenschaften die gesamte
Menge Lin(v1 , . . . , vr ).

Beispiel. Für v1 = (1, 0, 0), v2 = (0, 1, 0) und v3 = (1, 2, 3) im Vektorraum R3 gilt

Lin(v1 , v2 , v3 ) = R3 .

Wir beobachten hierzu zunächst, dass wegen

1
(v3 − v1 − 2v2 ) = (0, 0, 1)
3
50 1. LINEARE ALGEBRA

der dritte Einheitsvektor w = (0, 0, 1) in Lin(v1 , v2 , v3 ) liegt und daher Lin(v1 , v2 , v3 ) =

Lin(v1 , v2 , v3 , w). Wegen
Lin((1, 0, 0), (0, 1, 0), w) = R3
ergibt sich dann das behauptete Ergebnis.

In der Darstellung eines Unterraums als lineare Hülle gegebener Vektoren kann es sein,
dass einige der Vektoren überflüssig sind, also als Linearkombination der anderen gege-
benen Vektoren dargestellt werden können. Auch in der Rechnung des voranstehenden
Beispiels war ein solches Phänomen zu beobachten. Die Frage der Redundanz wird durch
die Begriffsbildung der linearen Unabhängigkeit erfasst.
Definition 7.4. Sei V ein K-Vektorraum und v1 , . . . , vr Vektoren (nicht notwendigerweise
alle verschieden). Die Folge v1 , . . . , vr heißt linear unabhängig, falls aus ri=1 λi vi = 0 mit
P

λ1 , . . . , λr ∈ K folgt, dass λ1 = · · · = λr = 0. Anderenfalls heißt die Folge v1 , . . . , vr linear

abhängig.

Mit anderen Worten: Die Folge v1 , . . . , vr heißt linear unabhängig, falls die Null nur als
triviale Linearkombination von v1 , . . . , vr dargestellt werden kann.

Wir bemerken, dass wir beim Begriff der linearen Unabhängigkeit von einer Folge von Vek-
toren sprechen, um zu erlauben, dass Vektoren auch mehrfach auftreten können. Unter
der linearen Unabhängigkeit einer Menge {v1 , . . . , vr } versteht man die lineare Unabhän-
gigkeit einer Folge, bei der jeder der Vektoren genau einmal vorkommt.

Beispiel. Im vorangegangenen Beispiel mit v1 = (1, 0, 0), v2 = (0, 1, 0), v3 = (1, 2, 3), w =
(0, 0, 1) ist die Folge v1 , v2 , v3 , w linear abhängig, da sich die Null nichttrivial darstellen
lässt, z.B. als
1 · v1 + 2 · v2 + (−1) · v3 + 3 · w = 0.
P3
Die Vektoren v1 , v2 , v3 hingegen sind linear unabhängig, denn aus i=1 λi vi = 0 mit
λi ∈ R folgt durch Betrachtung der ersten und zweiten Koordinate λ1 = 0 und λ2 = 0
und anschließend durch Betrachtung der dritten Koordinate λ3 = 0.

Definition 7.5. Sei V ein K-Vektorraum und v1 , . . . , vr ∈ V (nicht notwendigerweise alle

verschieden). Die Folge v1 , . . . , vr heißt Erzeugendensystem von V , wenn Lin(v1 , . . . , vr ) =
V.

Ist v1 , . . . , vr ein Erzeugendensystem von V , dann besitzt jeder Vektor v ∈ V also eine
Darstellung der Form
Xr
v= λi vi .
i=1
 7. VEKTORRÄUME 51

Diese Darstellung muss jedoch nicht eindeutig sein. Ist die Folge v1 , . . . , vr linear unab-
hängig, dann ist sie eindeutig. Denn aus
Xr r
X
v = λi vi = µi vi
i=1 i=1
mit Zahlen λi , µi ∈ K würde wegen
r
X
(λi − µi )vi = 0
i=1

aus der linearen Unabhängigkeit von v1 , . . . , vr folgen, dass λi = µi für alle i ∈ {1, . . . , r}.
Die Eindeutigkeitsüberlegungen bei der Darstellbarkeit von Vektoren durch andere Vek-
toren motivieren den nachfolgenden Begriff einer Basis.
Definition 7.6. Eine Folge v1 , . . . , vr von Vektoren aus V heißt eine Basis von V , wenn
sie linear unabhängig ist und ein Erzeugendensystem von V bildet.

Besteht V nur aus dem Nullvektor, dann ist per Konvention die leere Folge (d.h. r = 0)
eine Basis von V .
Satz 7.7. Sei V ein K-Vektorraum und v1 , . . . , vr eine Folge von Vektoren aus V . Dann
sind folgende Aussagen äquivalent:

(1) v1 , . . . , vr ist eine Basis von V .

(2) v1 , . . . , vr ist eine nicht verlängerbare linear unabhängige Folge.
(3) v1 , . . . , vr ist ein unverkürzbares Erzeugendensystem von V .

Beispiel. 1. Die Einheitsvektoren e(1) , . . . , e(n) bilden eine Basis des Rn .

2. Die Vektoren (1, 0, 0)> , (2, 1, 0)> , (5, −2, −3)> bilden eine Basis des R3 .

Beweis. Wir zeigen die Äquivalenz der drei Aussagen mittels des Ringschlusses von Im-
plikationen (1) =⇒ (2) =⇒ (3) =⇒ (1).

(1) =⇒ (2) : Sei v1 , . . . , vr eine Basis von V . Nach Definition ist diese Folge linear un-
abhängig. Es verbleibt zu zeigen, dass es keinen Vektor v ∈ V gibt, so dass v1 , . . . , vr , v
linear unabhängig ist.

Annahme: Sei v ∈ V ein Vektor, so dass v1 , . . . , vr , v linear unabhängig ist.

Pr
Da v1 , . . . , vr eine Basis ist, existieren λ1 , . . . , λr mit v = i=1 λi vi . Es existiert also eine
nichttriviale Linearkombination der Null,
1 · v + (−λ1 )v1 + · · · + (−λr )vr = 0,
52 1. LINEARE ALGEBRA

im Widerspruch zur linearen Unabhängigkeit von v1 , . . . , vr , v.

(2) =⇒ (3) : Sei v1 , . . . , vr eine nicht verlängerbare linear unabhängige Folge.

Zeige zunächst: v1 , . . . , vr bildet ein Erzeugendensystem von V .

Sei v ∈ V beliebig. Da v1 , . . . , vr eine nicht verlängerbare linear unabhängige Folge ist,

existieren Skalare λ1 , . . . , λr ∈ K und λ ∈ K, nicht alle Null, mit
λv + λ1 v1 + · · · + λr vr = 0.
Es muss λ 6= 0 sein, da anderenfalls v1 , . . . , vr abhängig wären. Also ist v in der linearen
Hülle von v1 , . . . , vr erhalten, so dass insgesamt die Folge v1 , . . . , vr ein Erzeugendensystem
von V bildet.

Zeige nun: Das Erzeugendensystem v1 , . . . , vr ist unverkürzbar.

Wäre das Erzeugendensystem v1 , . . . , vr verkürzbar, dann müsste einer der Vektoren aus
der Folge als Linearkombination der anderen darstellbar sein und das würde der linearen
Unabhängigkeit von v1 , . . . , vr widersprechen. Also ist das Erzeugendensystem v1 , . . . , vr
unverkürzbar.

(3) =⇒ (1) : Sei v1 , . . . , vr ein unverkürzbares Erzeugendensystem von V .

Zeige: Die Folge v1 , . . . , vr ist linear unabhängig.

Wäre v1 , . . . , vr linear abhängig, dann gäbe es λ1 , . . . , λr ∈ K, nicht alle Null, mit ri=1 λi vi
P

= 0. Ist etwa j ein Index mit λj 6= 0, dann lässt sich vj als Linearkombination der anderen
Vektoren darstellen, woraus sich ein Widerspruch zur vorausgesetzten Unverkürzbarkeit
der Folge ergibt. Da die linear unabhängige Folge v1 , . . . , vr nach Voraussetzung ein Er-
zeugendensystem von V ist, bildet sie folglich eine Basis. 

Lemma 7.8. Sei v1 , . . . , vr eine Basis des K-Vektorraums V und w1 , . . . , ws eine linear
unabhängige Folge von Vektoren aus V . Dann gilt r ≥ s.

Beweis. Aufgrund der Basiseigenschaft von v1 , . . . , vr existieren Elemente aij ∈ K mit

r
X
aij vi = wj , 1 ≤ j ≤ s.
i=1

Wir untersuchen nun das durch die Matrix A = (aij ) ∈ Mat(r × s, K) definierte Glei-
chungssystem A · x = 0. Durch elementare Zeilentransformationen (über dem Körper K)
kann A in Zeilenstufenform Ā überführt werden.
 7. VEKTORRÄUME 53

Annahme: r < s.

Dann besitzt Ā mehr Spalten als Zeilen, so dass es in dem System Āx = 0 mindestens eine
von Null verschiedene Lösung gibt, die wir hier mit x∗ = (λ1 , . . . , λs ) bezeichnen. Wegen
Lös(A|0) = Lös(Ā|0) gilt auch Ax∗ = 0.
s
P
Behauptung: λj wj = 0.
j=1

Die Behauptung folgt aus

s s r
! r s
!
X X X X X
λj w j = aij vi · λj = aij λj · vi = 0.
j=1 j=1 i=1 i=1 j=1

Aus der Behauptung folgt die lineare Abhängigkeit von w1 , . . . , wr , ein Widerspruch zur
Voraussetzung. Also muss r ≥ s sein. 

Satz 7.9. Sei V ein K-Vektorraum, der ein endliches Erzeugendensystem besitzt. Dann
besitzt V eine Basis, die aus endlich vielen Vektoren besteht. Alle Basen von V bestehen
aus gleich vielen Elementen.

Beweis. Zu einem gegebenen endlichen Erzeugendensystem von V lässt sich durch suk-
zessives Weglassen von Elementen ein nicht verkürzbares Erzeugendensystem gewinnen.
Nach Satz 7.7 bildet dieses eine Basis.

Seien nun v1 , . . . , vr und w1 , . . . , ws zwei Basen. Durch Anwendung des voranstehenden

Satzes auf jede der beiden Basen ergibt sich r ≥ s sowie s ≥ r. 

Die Anzahl der Elemente einer Basis von V , die aufgrund des voranstehenden Satzes ja
für alle Basen gleich ist, wird gemäß der nachstehenden Definition als Dimension von V
bezeichnet.
Definition 7.10. Sei V ein K-Vektorraum. Falls V ein endliches Erzeugendensystem be-
sitzt, dann heißt die Zahl der Elemente einer Basis von V die Dimension von V (Schreib-
weise: dimK V ). Existiert kein endliches Erzeugendensystem, ordnen wir V die Dimension
∞ zu.

Beispiel. 1. Die Dimension des Vektorraums K n ist n.

2. Die Dimension des Vektorraums Mat(m × n, K) ist m · n. Eine Basis ist gegeben durch
die Menge der Matrizen, die in genau einem Eintrag eine Eins haben und eine Null in
allen anderen Einträgen haben.
54 1. LINEARE ALGEBRA

8. Der Rang einer Matrix

Wie behandeln hier den Begriff des Rangs einer Matrix. Er dient insbesondere auch dazu,
die Struktur der Lösungen linearer Gleichungssysteme näher zu beschreiben und beispiels-
weise zu charakterisieren, wann ein inhomogenes Gleichungssystem überhaupt eine Lösung
besitzt. Der zu Grunde liegende Körper sei im Folgenden wieder mit K bezeichnet.
Definition 8.1. Der Zeilenrang einer Matrix A ist die Anzahl der linear unabhängigen
Zeilen der Matrix. Wir schreiben kurz zrg(A).

Nach den früheren Überlegungen ändern elementare Zeilenumformungen den Zeilenrang

einer Matrix nicht. Folglich stimmt der Zeilenrang einer Matrix A mit der Anzahl der von
Null verschiedenen Zeilen in einer zugehörigen Zeilenstufenform überein.

Beispiel. Die Matrix  

1 3 5
A= 0 2 4 
0 0 0
hat den Zeilenrang 2. Es liegt ja bereits eine Zeilenstufenform mit zwei Zeilen vor. Die
Matrix  
1 3 5
A= 0 2 4 
1 5 9
hat ebenfalls den Rang 2, denn durch Subtraktion der ersten und zweiten Zeile von der
dritten Zeile ergibt sich die vorherige Matrix als Zeilenstufenform.

Analog zur Definition des Zeilenrangs ist definiert:

Definition 8.2. Der Spaltenrang einer Matrix A ist die Anzahl der linear unabhängigen
Spalten der Matrix. Wir schreiben kurz srg(A).

Um einen Zusammenhang zwischen dem Zeilenrang und dem Spaltenrang herzustellen,

studieren wir in diesem Abschnitt den Zeilenraum von A und den Spaltenraum von A.
Definition 8.3. Sei A ∈ K m×n . Der Zeilenraum von A ist der von Zeilen von A erzeugte
Vektorraum. Der Spaltenraum von A ist der von den Spalten von A erzeugte Vektorraum.

Es gilt also
Spaltenraum von A = {Ax : x ∈ K n } ,
Zeilenraum von A = {y > A : y ∈ K m } .
 8. DER RANG EINER MATRIX 55

Lemma 8.4. Für alle A ∈ K m×n und alle invertierbaren Matrizen P ∈ K m×m , Q ∈ K n×n
gilt:

(1) A und AQ haben denselben Spaltenraum.

(2) A und P A haben denselben Zeilenraum.

Beweis. Aufgrund der Beziehung

Ax = (AQ)(Q−1 x) = AQx0 mit x0 = Q−1 x

liegt jedes Element des Spaltenraums von A im Spaltenraum von AQ und umgekehrt.
Wegen der analogen Beziehung

y > A = y > P −1 P A = (y 0 )> P A mit (y 0 )> = y > P −1

liegt jedes Element des Zeilenraums von A im Zeilenraum von P A und umgekehrt. 

Durch die früher beschriebenen elementaren Zeilenumformungen auf den Zeilen der Matrix
ändert sich der Zeilenraum und der Zeilenrang nicht. Analog zu den elementaren Zeilen-
umformungen lassen sich auch elementare Spaltenumformungen betrachten. Durch ele-
mentare Spaltenumformungen ändert sich der Spaltenrang nicht. Die elementaren Zeilen-
und Spaltenumformungen auf den Matrizen lassen sich mittels Multiplikation sogenannter
Elementarmatrizen beschreiben.

Elementarmatrizen. Wir betrachten die folgenden elementaren Zeilen- und Spaltenumfor-

mungen:

Typ I: Vertauschung von zwei Zeilen (Spalten).

Typ II: Multiplikation einer Zeile (Spalte) mit einem λ 6= 0.
Typ III: Addition des Vielfachen einer Zeile (Spalte) zu einer anderen.

Definition 8.5. Eine m×m-Matrix E heißt Elementarmatrix vom Typ i (i ∈ {I, II, III}),
wenn sie aus der m×m-Einheitsmatrix Im durch eine einzige elementare Zeilenumformung
vom Typ i hervorgeht.
56 1. LINEARE ALGEBRA

Beispiel. Seien mit e(i) die Einheitszeilenvektoren bezeichnet. Beispiele für Elementar-
matrizen, die zu den elementaren Zeilenumformungen vom Typ I, II, III gehören, sind:
 (2)   
e 0 1 0
 e(1)  =  1 0 0  (Typ I, e(1) ↔ e(2) ) ,
e(3) 0 0 1
 (1)   
e 1 0 0
 αe(2)  =  0 α 0  (Typ II, e(2) → αe(2) ) ,
e(3) 0 0 1
 (1) (3)
  
e + αe 1 0 α
 e(2)  =  0 1 0  (Typ III, e(1) → e(1) + αe(3) ) .
e(3) 0 0 1
Alternativ lassen sich die Elementarmatrizen auch spaltenweise ausdrücken. So lässt sich
die Matrix in dem eben beschriebenen Beispiel einer Zeilenumformung vom Typ III (Ad-
dition des α-fachen der 3-ten Zeile zur ersten Zeile) auch als
(e(1) , e(2) , e(3) + αe(1) )
mit den Spalteneinheitsvektoren e(i) ausdrücken.

Durch Nachrechnen ergibt sich:

Satz 8.6. 1. Entsteht Ā aus A ∈ K m×n durch genau eine elementare Zeilenumformung
(bzw. Spaltenumformung), dann gilt
Ā = EA (bzw. Ā = AE > )
mit der zugehörigen Elementarmatrix E.

2. Die Elementarmatrizen sind invertierbar und die Inversen sind ebenfalls Elementarma-
trizen.

Beweis. Die erste Aussage ist nach Konstruktion klar. Für die zweite Aussage geben wir
die Inversen explizit an.

Typ I: Ist Pij die Elementarmatrix für die Vertauschung zweier Zeilen (Spalten) i und j,
dann gilt (Pij )−1 = Pij .

Typ II: Ist Mi (α) die Elementarmatrix für die Multiplikation der i-ten Zeilen (Spalte) mit
α, dann gilt (Mi (α))−1 = Mi (α−1 ).

Typ III: Ist Gij (α) die Elementarmatrix für die Addition des α-fachen der i-ten Zeile
(Spalte) zur j-ten Zeile, dann gilt
Gij (α) = (e(1) , . . . , e(i−1) , e(i) + αe(j) , e(i+1) , . . . , e(n) )
 8. DER RANG EINER MATRIX 57

mit den Spalteneinheitsvektoren e(k) für alle k. Die inverse Matrix ist Gij (−α), denn mit
der Bezeichnung
Eij := e(i) (e(j) )> = (0, . . . , 0, |{z}
e(i) , 0, . . . , 0) ∈ K n×n
Spalte j

gilt
Gij (α)Gij (−α) = (In + αEji )(In + (−α)Eji )
= In + αEji + (−α)Eji + (−α2 )Eji
2

= In ,
2
da Eji = 0 für i 6= j. 

Als Konsequenz stimmt der Zeilenrang einer Matrix A mit der Anzahl r der von Null
verschiedenen Zeilen in der Zeilenstufenform
  


 *
∗

*
  

  
r
 . .


 . 

M =

  




 * 
  
( 
 0 * 

 
m−r
 

von A überein. Es existiert zudem eine invertierbare Matrix P mit M = P A. Die Matrix P
geht als Produkt der Elementarmatrizen zu den elementaren Zeilenumformungen hervor,
die bei der Überführung in die Zeilenstufenform ausgeführt werden.

In analoger Weise lässt sich eine Matrix durch elementare Spaltenumformungen in eine
Matrix N in Spaltenstufenform
 

 *
 

 
 
 
* 0
 
 
 
 
 .. 

 . 

 
 ∗ * 

überführen. Der Spaltenrang von A stimmt dann überein mit der Anzahl der von Null
verschiedenen Spalten in N . Es existiert zudem eine invertierbare Matrix Q mit N = AQ.
58 1. LINEARE ALGEBRA

Die Matrix Q geht als Produkt der Elementarmatrizen zu den elementaren Spaltenumfor-
mungen hervor, die bei der Überführung in die Spaltenstufenform ausgeführt werden.

Beispiel. Wir überführen die nachstehende Matrix A durch elementare Spaltenumfor-

mungen in Spaltenstufenform.
       
1 5 2 1 0 2 1 0 0 1 0 0
A= 0 2 1
  −→  0 2 1 −→ 0
  2 1  −→ 0 2 0
1 1 0 1 −4 0 1 −4 −2 1 −4 0
Da diese Matrix in Spaltenstufenform zwei von Null verschiedene Spalten hat, ist srg(A) =
2.

Gleichwertig dazu transponiert man die Matrix, überführt die entstehende Matrix mittels
elementarer Zeilenoperationen in Zeilenstufenform und transponiert wieder zurück in die
Ausgangsform.

Den Zeilenrang bezeichnen wir von nun an kurz als Rang, und wir werden im Nachste-
henden sehen, dass der Rang (also der Zeilenrang) mit dem Spaltenrang übereinstimmt.
Satz 8.7 (Normalform bezüglich des Rangs). Für jede m × n-Matrix A existieren
invertierbare Matrizen P ∈ K m×m und Q ∈ K n×n , so dass
 
Ir 0
P AQ = , r = rg A .
0 0

Beweis. In leichter Verallgemeinerung der obigen Vorbemerkungen existiert eine Matrix

P ∈ K m×m , so dass M := P A in reduzierter Zeilenstufenform ist. Es verbleibt nun noch,
Spalten zu vertauschen, was nach den beschriebenen Elementarmatrizen der Multiplika-
tion von rechts mit einer invertierbaren Matrix Q ∈ K n×n entspricht. 

Wir bringen den Begriff des Rangs nun mit linearen Gleichungssystemen in Verbindung.
Hierzu ist es nützlich, den Begriff des Kerns einer Matrix einzuführen.
Definition 8.8. Der Kern einer Matrix A ∈ K m×n ist definiert als
ker A = {x ∈ K n : Ax = 0}.

Der Kern von A ist also die Lösungsmenge des durch A definierten homogenen Gleichungs-
systems Ax = 0. ker A ist ein Unterraum von K n .
Satz 8.9. 1. (Basis des Kerns.) Sei A ∈ K m×n eine Matrix vom Rang  P ∈
 r. Sind
Is 0
K m×m , Q = (q (1) , . . . , q (n) ) ∈ K n×n invertierbare Matrizen mit P AQ = , dann
0 0
gilt s = r und die letzten n − r Spalten q (r+1) , . . . , q (n) von Q bilden eine Basis von ker A.
 8. DER RANG EINER MATRIX 59

2. (Dimensionsformel.) Für jede Matrix A ∈ K m×n

rg A + dim ker A = n.

Beispiel. Für die Matrix

 
2 5 3 4
0 1 7 6  4×4
4 10 6 8  ∈ R .
A =  

2 6 10 10

soll die Dimension des Kerns von A und eine Basis von ker A bestimmt werden. Mittels
elementarer Zeilenumformungen lässt sich A in
 
2 5 3 4
0 1 7 6
A =  0 0 0 0


0 0 0 0

überführen. Es folgt rg(A) = 2 und damit nach der Dimensionsformel dim ker A = 4 − 2 =
2. Zur Bestimmung einer Basis setzen wir etwa die hinteren beiden Komponenten (x3 , x4 )
auf (0, 1) bzw. (1, 0). Im ersten Fall ergibt sich
1
x2 = −6, x1 = (5 · 6 − 4 · 1) = 13
2
und im zweiten Fall
1
x2 = −7, x1 = (5 · 7 − 3 · 1) = 16 .
2
Eine Basis des Kerns ist daher

(13, −6, 0, 1)> , (16, −7, 1, 0)> .



Die Dimension des Kerns gibt gerade die Anzahl der freien Parameter beim Lösen des
Gleichungssystems Ax = 0 an. Die Bestimmung einer Basis eines Kerns entspricht dem
aus den Anfangsabschnitten bekannten Vorgehen beim Berechnen der allgemeinen Lösung
des Gleichungssystems Ax = 0.

Beweis. Vorbemerkung: Ist Q invertierbar, dann existiert eine Matrix M mit M Q = In .

Folglich sind die Spalten von Q linear unabhängig, denn aus Qy = 0 mit y ∈ K n folgt

0 = M Qy = In y = y .
60 1. LINEARE ALGEBRA

Für x ∈ K n gilt:

x ∈ ker A ⇐⇒ Ax = 0 ⇐⇒ P −1 P AQ(Q−1 x) = 0
 
  y1
Is 0  ..  −1
⇐⇒  .  = P · 0 = 0 mit y := Q x
0 0
yn
⇐⇒ y1 = · · · = ys = 0 und ys+1 , . . . , yn ∈ K beliebig
⇐⇒ x = Q(ys+1 e(s+1) + · · · + yn e(n) ) = ys+1 q (s+1) + · · · + yn q (n) .

Folglich erzeugen die linear unabhängigen Vektoren q (s+1) , . . . , q (n) den Unterraum ker A
und bilden deshalb eine Basis von ker A.

Insbesondere ist dim(ker A) = n−s, d.h., s ist eindeutig bestimmt durch s = n−dim ker A.
In Verbindung mit der Matrizennormalform in Satz 8.7 ergibt sich r = n − dim ker A und
s = r. Dies zeigt auch die Dimensionsformel. 

Satz 8.10. (Zeilenrang=Spaltenrang.) Für jede Matrix A stimmen der Rang von A
(also der Zeilenrang von A) und der Spaltenrang von A überein.

Beweis. Es gibt eine invertierbare Matrix Q, so dass N := AQ eine reduzierte Spalten-

stufenform von A ist. Durch elementare Zeilenumformungen erhalten wir
 
Ip 0
P AQ = , p = dim(Spaltenraum)
0 0

mit einer invertierbaren Matrix P . Nach dem voranstehenden Satz ist p = rg A, woraus
die Behauptung folgt. 

Da sich der Zeilenrang unter elementaren Zeilentransformationen nicht ändert und der
Spaltenrang sich unter elementaren Spaltentransformationen nicht ändert, gilt also: Der
Rang ändert sich weder unter elementaren Zeilentransformationen noch unter elementaren
Spaltentransformationen.

Da der Zeilenrang und der Spaltenrang übereinstimmen, gilt für jede Matrix

rg(A) = rg(A> ) .

Beispiel. Da der Zeilenrang und der Spaltenrang übereinstimmen, darf man bei der
Bestimmung des Rangs Zeilen- und Spaltenumformungen miteinander mischen. Bei der
nachstehend gegebenen Matrix A subtrahieren wir die zunächst die erste Zeile von der
 8. DER RANG EINER MATRIX 61

letzten Zeile:
   
1 8 8 1 1 8 8 1
0 1 1 0 0 1 1 0
A=
0
 −→  
1 1 0 0 1 1 0
1 8 8 1 0 0 0 0
Durch Subtraktion der zweiten von der dritten Spalte und die erste Spalte von der letzten
Spalte ergibt sich
   
1 8 0 0 1 8 0 0
0 1 0 0 0 1 0 0
0 1 0 0 −→ 0 0 0 0
   

0 0 0 0 0 0 0 0
Hierbei wurde im letzten Schritt die zweite Zeile von der dritten subtrahiert. Die Matrix
ist in Zeilenstufenform und rg(A) = 2.

Mittels des Rangs lässt sich die Lösbarkeit eines linearen Gleichungssystems mit rechter
Seite b wie folgt charakterisieren:

Satz 8.11. Sei A ∈ K m×n , b ∈ K m , und (A b) die Matrix, die aus A entsteht, indem b
als Spalte hinzugefügt wird. Das Gleichungssystem Ax = b ist genau dann lösbar, wenn
der wenn rg(A) = rg(A b).

Beweis. Seien a(1) , . . . , a(n) die Spalten von A. Das Gleichungssystem Ax = b ist genau
dann lösbar, wenn es x1 , . . . , xn ∈ K gibt mit

b = Ax .

Äquivalent dazu lässt sich b als Linearkombination der Spalten a(1) , . . . , a(n) von A aus-
drücken:
b = x1 a(1) + · · · + xn a(n) .
Das ist genau dann der Fall, wenn der Spaltenrang von A mit dem Spaltenrang von (A b)
übereinstimmt, also genau dann wenn rg(A) = rg(A b). 

Um die Lösbarkeit eines linearen Gleichungssystems aus geometrischer Sicht zu beschrei-

ben, führen wir das Bild einer Matrix ein.

Definition 8.12. Das Bild (engl. image) einer m × n-Matrix A ist definiert als

Bild A = {Ax : x ∈ K n } ⊆ K m .
62 1. LINEARE ALGEBRA

Das Bild von A besteht also aus allen Vektoren, die durch Anwendung von A erreicht
werden können. Alternativ spricht man auch vom Bild der durch x 7→ Ax definierten
linearen Abbildung f : K n → K m .

Unmittelbar aus der Begriffsbildung folgt: Ein Gleichungssystem Ax = b ist genau dann
lösbar, wenn b ∈ Bild(A).
Satz 8.13. Das Bild einer Matrix A ∈ K m×n ist ein Unterraum von K m , der von den
Spaltenvektoren von A aufgespannt wird. Die Dimension des Bildes stimmt daher mit dem
Rang von A überein,
dim Bild A = rg A .

Beweis. Seien a(1) , . . . , a(n) die Spalten von A. Ein Vektor y liegt genau dann im Bild,
wenn er als y = Ax = x1 a(1) +· · ·+xn a(n) mit x1 , . . . , xn darstellbar ist. Hieraus folgt auch
die Unterraumeigenschaft und damit die gesamte erste Aussage. Für die zweite Aussage
genügt es festzustellen, dass die Dimension des von a(1) , . . . , a(n) definierten Unterraums
gerade der Spaltenrang von A ist. 

Wir haben bereits früher auf die Beziehung zwischen linearen Abbildungen f : K n → K m
und Matrizen A ∈ K m×n hingewiesen. Entsprechend übertragen sich auch die hier für
Matrizen definierten Begriffe wie Kern, Bild und Rang auf lineare Abbildungen,
ker f = {x ∈ K n : f (x) = 0},
Bild f = {f (x) : x ∈ K n },
rg f = dim Bild f .
Die Dimensionsformel lautet in dieser Sprache dann
rg f + dim ker f = n .
 9. DIE DETERMINANTE 63

9. Die Determinante

Mit der Determinante lassen sich beispielsweise elementargeometrische Größen elegant

beschreiben, die Lösung eines linearen Gleichungssystems mit invertierbarer Koeffizien-
tenmatrix direkt als Funktion der Koeffizienten darstellen sowie der Test einer Matrix auf
Invertierbarkeit auf die Abfrage zurückzuführen, ob eine Zahl von Null verschieden ist.
Wir betrachten zur Motivation im Folgenden zunächst Matrizen über R, die zentralen
Konzepte lassen sich über beliebigen Körpern K betrachten.
   
a1 b1
Determinanten von 2 × 2-Matrizen. Das von zwei Vektoren a = und b =
a2 b2
aufgespannte Parallelogramm hat den Flächeninhalt
   
a1 b1
F = a2  × b2  = |a1 b2 − a2 b1 | .
0 0

Die Zahl
det A := a1 b2 − a2 b1
 
a1 b 1
heißt die Determinante der 2 × 2-Matrix A = . Sie lässt sich nach dem Schema
a2 b 2
 
a1 b1
det  %
&  = a1 b 2 − a2 b 1
a2 b2

berechnen, wobei bei dem Produkt der Diagonalelemente der Matrix ein positives Vor-
zeichen auftritt und bei dem Produkt der entgegengesetzten Diagonalen ein negatives
Vorzeichen.
     
a1 b 1 a1 b1
Es gilt genau dann det A = det = 0, wenn und parallel sind (oder
a2 b 2 a2 b2
einer
 der beiden der Nullvektor) und damit linear abhängig. Anders ausgedrückt ist A =
a1 b 1
genau dann invertierbar, wenn det A 6= 0.
a2 b 2
 
2 1
Beispiel. Wegen det = 2 · 4 − 1 · 3 = 5 ist die zu Grunde liegende Matrix
3 4
   
2 1
invertierbar. Der Flächenhinhalt des von und aufgespannten Parallelogramms
3 4
ist F = | det A| = 5.
64 1. LINEARE ALGEBRA

Determinanten von 3 × 3-Matrizen. Ein Spat (die dreidimensionale Verallgemeinerung

eines Parallelograms, aufgespannt also von drei Vektoren im R3 ), das durch die Vektoren
     
a11 a12 a13
(1) (2) (3)
a = a21 , a = a22 , a = a23 
    
a31 a32 a33
aufgespannt wird, hat das Volumen

V = |a11 (a22 a33 − a32 a23 ) − a21 (a12 a33 − a32 a13 ) + a31 (a12 a23 − a22 a13 )|.

Der Ausdruck innerhalb der Betragsstriche ist auch als „Spatprodukt“ bekannt und wir
definieren nun die Determinante der 3 × 3-Matrix
 
a11 a12 a13
A = a21 a22 a23 
a31 a32 a33
als diesen Ausdruck in den Betragsstrichen,
 
a11 a12 a13
det A = det a21 a22 a23 
a31 a32 a33
:= a11 (a22 a33 − a32 a23 ) − a21 (a12 a33 − a32 a13 ) + a31 (a12 a23 − a22 a13 ) .

Für eine Matrix A ∈ R3×3 gilt genau dann det A = 0, wenn a(1) , a(2) und a(3) linear
abhängig sind. Anders ausgedrückt ist A ∈ R3×3 genau dann invertierbar, wenn det A 6= 0.

Die in der Definition der 3 × 3-Determinante eingeklammerten Ausdrücke lassen sich als
2 × 2-Determinanten interpretieren:
     
a22 a23 a12 a13 a12 a13
det A = a11 det − a21 det + a31 det .
a32 a33 a32 a33 a22 a23

Für 3 × 3-Matrizen lässt sich die Berechnung auch mit der sogenannten Regel von Sarrus
(auch „Jägerzaun“-Regel) ausführen. Hierbei werden rechts neben den drei Spalten der
Matrix A noch einmal die ersten beiden geschrieben und nun die drei &-Diagonalen
addiert und die drei %-Diagonalen subtrahiert:
a11 a12 a13 a11 a12
& %
& %
& %
a21 a22 a23 a21 a22
% &
% &
% &
a31 a32 a33 a31 a32
 9. DIE DETERMINANTE 65

Es ergibt sich

det A = a11 a22 a33 + a12 a23 a31 + a13 a21 a32
−a31 a22 a13 − a32 a23 a11 − a33 a21 a12 .

 
2 0 −1
Beispiel. Für A = 3 4 0  liefert die Regel von Sarrus
1 −5 2

det A = 16 + 0 + 15 − 0 − 0 − (−4) = 35 .

Die Matrix A ist daher invertierbar, und das von den Spalten von A aufgespannte Spat
hat das Volumen |35| = 35.

Die Determinante einer allgemeinen n × n-Matrix über einem Körper K. Aufbauend auf
den Spezialfällen n = 2 und n = 3 definieren wir Determinanten wie folgt rekursiv. Sei K
nun ein fest gewählter Körper.

Definition 9.1. Sei A = (aij ) ∈ K n×n .

Für n = 1 ist det A := a11 .

Für n ≥ 2 ist

det A := a11 det A11 − a21 det A21 + a31 det A31
− + · · · + (−1)n+1 an1 det An1 ,

wobei Ai1 die (n − 1) × (n − 1)-Matrix bezeichnet, die aus A durch Streichen der ersten
Spalte und der i-ten Zeile hervorgeht, 1 ≤ i ≤ n.

Diese rekursive Rückführung bezeichnet man als Entwicklung nach der ersten Spalte.

Beispiel. Wir betrachten

3 5 −2
 
6  
1 2 −1 2 −1 1
1
A = det  2 4 1 ∈ R4×4 , also A11 = 4 1 5 ,
5
7 5 3
3 7 5 3
     
5 −2 6 5 −2 6 5 −2 6
A21 = 4 1 5 , A31 = 2 −1 1 , A41 = 2 −1 1 .
7 5 3 7 5 3 4 1 5
66 1. LINEARE ALGEBRA

Dann ist

det A = 3 · det A11 − 1 · det A21 + 2 · det A31 − 3 · det A41

= 3 · (−54) − 1 · (−78) + 2 · 60 − 3 · 18
= −18 .

Hinweis: Die Regel von Sarrus für 3 × 3-Matrizen lässt sich nicht auf n × n-Matrizen
übertragen.

Als Grundlage für weitere Betrachtungen und eine geschickte Berechnungsmethode für
Determinanten stellen wir in den nachstehenden Aussagen einige Rechenregeln zusammen.

Satz 9.2. Für eine obere Dreiecksmatrix gilt

 
a11 ∗ ··· ∗
. .  n
a21 . . .. 

0 Y
det 
 .. .. ..
 = aii = a11 a22 · · · ann .
. . ∗ 

 . i=1
0 · · · 0 ann

Insbesondere gilt für die Determinante der Einheitsmatrix det In = 1.

Beweis. Da die Elemente a21 , . . . , an1 alle Null sind, vereinfacht sich die Entwicklung
nach der ersten Spalte zu
 
a22 ∗
det A = a11 · det 
 .. ,

.
0 ann

woraus sich induktiv det A = a11 a22 · · · ann ergibt. 

Lemma 9.3. Die Determinantenfunktion det ist linear in jeder Zeile. D.h., im Detail:

a) Besitzen alle Elemente einer fest gewählten Zeile den gleichen Faktor λ, dann kann
dieser herausgezogen werden.

b) Besteht eine fest gewählte Zeile aus einer Summe c = a + b mit Zeilenvektoren a, b, c,
dann besitzt det A die zugehörige Summenzerlegung.
 9. DIE DETERMINANTE 67

Es gelten also die Formeln

         
z (1) z (1) z (1) z (1) z (1)
 ..   ..   ..   ..   .. 
 .   .   .   .   . 
 (i)         
det  λz  = λ det  z (i)  , det a + b  = det  a  + det  b 
 ..   ..   ..   ..   .. 
         
 .   .   .   .   . 
z (n) z (n) z (n) z (n) z (n)

mit Zeilenvektoren z (1) , . . . , z (n) , a, b und einem Skalar λ.

Beweis. Die beiden Eigenschaften ergeben sich mittels vollständiger Induktion unmittel-
bar aus der Entwicklung nach der ersten Spalte. 

Lemma 9.4. Die Determinantenfunktion det ist alternierend in folgendem Sinne. Ent-
steht eine Matrix Ā aus A ∈ K n×n durch Vertauschung zweier Zeilen, dann gilt det Ā =
− det A. Als Konsequenz ist det A = 0, falls A zwei identische Zeilen enthält.

Beweis. Aufgrund des alternierenden Vorzeichens in der Entwicklung nach der ersten
Spalte, ergibt sich (wiederum induktiv), dass sich bei Vertauschung zweier benachbarter
Zeilen das Vorzeichen der Determinante ändert. Da sich jede Vertauschung zweier belie-
biger Zeilen stets durch eine ungerade Anzahl von Vertauschungen benachbarter Zeilen
realisieren lässt, folgt die Behauptung.

Im Spezialfall der Vertauschung zweier identischer Zeilen gilt also det A = − det A, woraus
sich det A = 0 ergibt. 

Satz 9.5. Seien A, B ∈ K n×n .

a) Geht Ā aus A durch eine elementare Zeilen- oder Spaltenoperation vom Typ i (i ∈
{I, II, III}, gemäß dem vorherigen Abschnitt) hervor, dann gilt

Typ I: det Ā = − det A.

Typ II: det Ā = λ det A.
Typ III: det Ā = det A.

b) A ist genau dann invertierbar wenn det A 6= 0. Anders ausgedrückt gilt rg A < n, falls
det A = 0.

c) Es gilt det(AB) = det(A) · det(B). (Multiplikationssatz)

d) Es gilt det A> = det A.

68 1. LINEARE ALGEBRA

Beweis. a) Die Regeln für Zeilenumformungen der Typen I und II ergeben sich aus den
voranstehenden beiden Lemmas. Die Regel für Zeilenumformungen des Typs III ergeben
sich aus der Linearität sowie der Eigenschaft, dass die Determinante einer Matrix mit zwei
identischen Zeilen Null ist.

Die Regeln für die Spaltenumformungen ergeben sich dann unmittelbar, wenn wir später
in diesem Beweis Aussage d) bewiesen haben.

b) Mittels elementaren Zeilenumformungen kann A in eine obere Dreiecksmatrix M über-

führt werden. Nach a) gilt det M = βA mit einem Skalar β 6= 0. Da eine obere Drei-
ecksmatrix genau dann invertierbar ist, wenn alle Diagonalelemente 6= 0 sind, folgt die
Behauptung.

c) Wir können annehmen, dass A und B invertierbar sind, denn anderenfalls ist auch AB
nicht invertierbar und es gilt det A · det B = 0.

In den Regeln für die Zeilenumformungen aus a) lässt sich unmittelbar verifizieren, dass
es sich bei den Faktoren auf den rechten Seiten der Regeln (also −1, λ, +1) jeweils um
die Determinante der zugehörigen Elementarmatrix handelt. Wir können die Regeln für
die Zeilenumformungen aus a) daher in der einheitlichen Form

det(ĒA) = det Ē det A

notieren, wobei Ē die zugehörige Elementarmatrix ist. Da sich jede invertierbare Matrix
als Produkt von Elementarmatrizen darstellen lässt, ergibt sich induktiv die zu zeigende
Produktregel.

d) Ist A nicht invertierbar, dann gilt nach b) die Eigenschaft det A = 0 = det A> .

Umgekehrt sei nun A invertierbar. Da sich A als Produkt von Elementarmatrizen dar-
stellen lässt, genügt es wegen c) zu zeigen, dass für jede Elementarmatrix Ē gilt det Ē =
det Ē > . Für Typ I und II gilt Ē > = Ē, so dass also auch die Determinanten gleich sind. Für
Typ III ist auch Ē > eine Elementarmatrix vom Typ III, woraus folgt det Ē = 1 = det Ē > .


Entwicklung der Determinante nach einer beliebigen Zeile oder Spalte. Sei A = (a(1) , . . . ,
a(n) ) ∈ K n×n eine Matrix mit den Spalten a(1) , . . . , a(n) . Für gegebenes j ∈ {1, . . . , n} geht
die Matrix Ā := (a(j) , a(1) , . . . , a(j−1) , a(j+1) , . . . , a(n) ) durch j − 1 Spaltenvertauschungen
aus A hervor. Es folgt
det Ā = (−1)j−1 det A.
 9. DIE DETERMINANTE 69

Durch Entwicklung von Ā nach der ersten Spalte ergibt sich der folgende Ausdruck zur
Entwicklung von A nach der j-ten Spalte:
n
X
det A = (−1)i+j aij det Aij ,
i=1

wobei Aij die (n − 1) × (n − 1)-Matrix bezeichnet, die aus A durch Entfernen der i-ten
Zeile und der j-ten Spalte hervorgeht. Aufgrund der Beziehung det A = det A> gilt auch
die folgende Formel zur Entwicklung nach der i-ten Zeile:
n
X
det A = (−1)i+j aij det Aij .
j=1

Beispiel. Bei der Berechnung einer Determinante bietet es sich an, eine Entwicklung nach
einer Zeile oder Spalte mit vielen Nullen auszuführen. Liegen keine oder nur wenige Nullen
vor, kann man zunächst versuchen, durch elementare Zeilen- oder Spaltentransformationen
eine Zeile oder Spalte mit vielen Nullen zu erzeugen. Bei der Anwendung elementarer
Zeilen- und Spaltentransformationen auf eine Determinante ist darauf zu achten, etwaige
bei den Rechenregeln auftretetenden Faktoren weiter mitzuführen. Beispielsweise ergibt
sich für die bereits in einem früheren Beispiel betrachtete Matrix
3 5 −2 6
 
1 2 −1 1 4×4
A = det  2 4 1 5 ∈ R


3 7 5 3
durch Addition geeigneter Vielfache der zweiten Zeile zur ersten, dritten und vierten Zeile
und dann durch Entwicklung nach der ersten Spalte
0 −1 1 3
 
 
1 2 3 3 −1 1 3
det A = det  0 0 3 3 = − det 0 3 3
  
1 8 0
0 1 8 0
= −(3 − (−24) − 9) = −18 ,

wobei die 3×3-Determinante direkt mit der Regel von Sarrus bestimmt wurde. (Alternativ
hätte man die auch die 3 × 3-Determinante erneut nach einer Zeile oder Spalte entwickeln
können.)

Zur systematischen Berechnung der Determinante kann man die Berechnung durch ele-
mentare Zeilen- und Spaltenoperationen auch auf die Determinante einer oberen Drei-
ecksmatrix zurückführen.
70 1. LINEARE ALGEBRA

Beispiel. Mit der Matrix A des voranstehenden Beispiels ergibt sich nach initialer Ver-
tauschung der ersten beiden Zeilen
1 2 −1 1
   
1 2 3 3
3 5 −2 6
 = − det 0 −1 1 3
 
det A = − det  2 4 1 5 0 0 3 3
3 7 5 3 0 1 8 0
   
1 2 3 3 1 2 3 3
0 −1 1 3 0 −1 1 3 
= − det  0 0 3 3 = − det 0 0 3 3  = −18 .
  

0 0 9 3 0 0 0 −6

Die Leibniz-Darstellung der Determinante. Wendet man die Entwicklung nach der ersten
Spalte,
n
X
det A := (−1)i+1 ai1 det Ai1 ,
i=1
auf die Berechnung aller Determinanten det Ai1 erneut rekursiv an, ergibt sich zum Schluss
die vollständige Entwicklung der Determinante
X
det A = sgn(i) ai1 ,1 ai2 ,2 · · · ain ,n ,
i=(i1 ,...,in )

wobei die Summe über alle Permutationen i = (i1 , . . . , in ) der Zahlen 1, 2, . . . , n läuft.
sgn(i) ist definiert als (−1)k , wobei k die Anzahl der Vertauschungen (Transpositionen)
ist, die benötigt werden, um (i1 , . . . , in ) in die natürliche Reihenfolge zu bringen. Wir
nennen sgn(i) das Signum einer Permutation. Die beschriebene vollständige Entwicklung
nennt man die Leibniz-Darstellung der Determinante. Bei Betrachtung von Zeilen statt
Spalten gilt entsprechend auch
X
det A = sgn(i) a1,i1 a2,i2 · · · an,in ,
i=(i1 ,...,in )

Beispiel. Für die Determinante einer 3 × 3-Matrix A ergibt sich wegen sgn(1, 2, 3) = 1,
sgn(1, 3, 2) = −1, sgn(2, 1, 3) = −1, sgn(2, 3, 1) = 1, sgn(3, 1, 2) = 1, sgn(3, 2, 1) = −1 die
von der Regel von Sarrus bekannte Entwicklung
det A = a11 a22 a33 − a11 a32 a23 − a21 a12 a33 + a21 a32 a13 + a31 a12 a23 − a31 a22 a13 .

Da die Anzahl der Terme n! beträgt, ist die Leibniz-Darstellung in der Regel nicht für das
praktische Berechnen der Determinante einer größeren Matrix geeignet.
 9. DIE DETERMINANTE 71

Anwendung: Die Cramersche Regel. Mittels der Determinante lässt sich die Lösung eines
inhomogenen quadratischen Gleichungssystems in sehr expliziter Form angeben.
Satz 9.6 (Die Cramersche Regel.). Sei A = (a(1) , . . . , a(n) ) eine invertierbare n × n-
Matrix über K mit Spalten a(1) , . . . , a(n) und sei b ∈ K n . Dann hat das Gleichungssystem
Ax = b die Lösung
1
xi = det(a(1) , . . . , a(i−1) , b, a(i+1) , . . . , a(n) ) .
det A

In der Determinante ganz rechts wird also die i-te Spalte von A durch b ersetzt.

Beweis. Ohne Beschränkung der Allgemeinheit sei i = 1. Wir schreiben

X n
b = Ax = xj a(j) .
j=1

Aus der Linearität der Determinantenfunktion in der ersten Spalte ergibt sich nun
det(b, a(2) , . . . , a(n) ) = det(x1 a(1) + · · · + xn a(n) , a(2) , . . . , a(n) )
Xn
= xj det(a(j) , a(2) , . . . , a(n) )
j=1

= x1 det(a(1) , . . . , a(n) )
= x1 det A .


Hinweis: Die Cramersche Regel ist normalerweise kein praktisches Rechenschema zum
Lösen linearer Gleichungssysteme.

Beispiel. Gegeben sei das Gleichungssystem

     
1 2 x1 5
· = .
3 4 x2 6
Mit der Cramerschen Regel ergibt sich die Lösung
   
5 2 1 5
det det
6 4 8 3 6 −9 9
x1 = = = −4, x2 = = = .
−2 −2
 
1 2 1 2 2
det det
3 4 3 4

Im Fall K = R verallgemeinert die n-dimensionale Determinante auch die zu Beginn

des Abschnitts gesehenen 2- bzw. 3-dimensionalen Flächen- bzw. Volumenbetrachtungen.
Der Betrag der Determinante einer Matrix A = (a(1) , . . . , a(n) ) liefert das n-dimensionale
72 1. LINEARE ALGEBRA

Volumen des von den n Spaltenvektoren a(1) , . . . , a(n) aufgespannten Parallelepipeds (die
n-dimensionale Verallgemeinerung eines zweidimensionalen Parallelogramms bzw. eines
dreidimensionalen Spats).
 10. DAS SKALARPRODUKT UND ORTHOGONALITÄT 73

10. Das Skalarprodukt und Orthogonalität

Durch das Skalarprodukt wird eine multiplikative Operation auf Vektoren eingeführt, die
enge Beziehungen zu den elementargeometrischen Aspekten von Längen sowie zu Win-
keln und damit auch zur Orthogonalität hat. Wir beschränken uns hier auf den Fall des
Vektorraums Rn mit dem euklidischen Skalarprodukt (auch: inneres Produkt oder Stan-
dardskalarprodukt).
Definition 10.1. Seien u = (u1 , . . . , un )> , v = (v1 , . . . , vn )> ∈ Rn . Die reelle Zahl
u · v := uT v = u1 v1 + · · · + un vn
heißt (euklidisches) Skalarprodukt der Vektoren u, v. (Beachte, dass u> v das Matrixpro-
dukt einer 1 × n-Matrix mit einer n × 1-Matrix ist.) Die (euklidische) Norm (oder die
Länge) eines Vektors v ist definiert als
√ q
kvk := v · v = v12 + v22 + · · · + vn2 .
Der Vektor v heißt normiert, wenn kvk = 1.

Als alternative Schreibweise für das euklidische Skalarprodukt von u von v existieren auch
hu, vi2 oder kurz hu, vi.

Beispiel.
     
1 3 3
· = (1 2) · = 1 · 3 + 2 · 4 = 11 ,
2 4 4
     
1 0
0
−1 · −1 = 1 −1 0 · −1 = 1 · 0 + (−1) · (−1) + 0 · 1 = 1 .
0 1 1
In jedem dieser beiden Beispiele steht die Multiplikation vor dem ersten Gleichheitszeichen
für ein Skalarprodukt und die Multiplikation unmittelbar hinter dem ersten Gleichheits-
zeichen für ein Matrixprodukt.

Satz 10.2 (Rechenregeln des Skalarprodukts). Für u, v, w ∈ Rn und λ ∈ R gilt:

Kommutativität: u · v = v · u.
Linearität im ersten Argument: (u + v) · w = u · w + v · w und (λ · u) · w =
λ · (u · w).
Positivität: v · v > 0 für alle v 6= 0.
Cauchy-Schwarz-Ungleichung: |u · v| ≤ kukkvk.

Durch Kombination der Kommutativität und der Linearität im ersten Argument ergibt
sich auch die Linearität im zweiten Argument.
74 1. LINEARE ALGEBRA

Beweis. Die ersten Regeln ergeben sich unmittelbar aus der Definition des Skalarpro-
dukts. Die Cauchy-Schwarz-Ungleichung ist im Spezialfall v = 0 klar, sei daher nun v 6= 0.
Für alle λ ∈ R gilt nach den ersten Regeln
0 ≤ (u − λv) · (u − λv) = u · u − 2λ(u · v) + λ2 (v · v) .
u·v
Die Wahl λ = kvk2
ergibt
0 ≤ (u · u)(v · v) − (u · v)2 ,
somit ist die Cauchy-Schwarz-Unleichung gezeigt. 

Satz 10.3 (Rechenregeln für die Norm). Für alle u, v ∈ Rn und alle λ ∈ R gilt

(1) kuk = 0 ⇐⇒ u = 0 ,
(2) kλ · uk = |λ| · kuk ,
(3) ku + vk ≤ kuk + kvk (Dreiecksungleichung).

Beweis. Die erste Eigenschaft folgt unmittelbar aus der Positivität von u · u für u 6= 0.
Die zweite Eigenschaft ergibt sich unmittelbar aus der Definition von Norm und Skalar-
produkt.

Die Dreiecksungleichung folgt unter Nutzung der Cauchy-Schwarz-Ungleichung aus

ku + vk2 = (u + v) · (u + v) = kuk2 + 2(u · v) + kvk2
≤ kuk2 + 2kukkvk + kvk2 = (kuk + kvk)2 .


Satz 10.4. Für u, v ∈ Rn gilt

u · v = kukkvk cos ϕ,
wobei ϕ ∈ [0, π] der (kleinere) Winkel zwischen u und v in der von den beiden Vektoren
aufgespannten Ebene ist.

Beweis. Der Einfachheit halber gehen wir hier davon aus, dass u und v Vektoren in
der Grundebene R2 sind. Der allgemeine Fall kann mittels der weiter unten im Text
beschriebenen „orthogonalen Transformationen“ darauf zurückgeführt werden.

Sei α der Winkel zwischen u und der x-Achse. Dann kann u als (kuk cos α, kuk sin α)>
geschrieben werden. Entsprechend ist v = (kvk cos β, kvk sin β)> , wobei β der Winkel
zwischen v und der x-Achse ist. Das euklidische Skalarprodukt von u und v ist dann
u · v = kukkvk cos α cos β + kukkvk sin α sin β
= kukkvk cos(α − β),
 10. DAS SKALARPRODUKT UND ORTHOGONALITÄT 75

wobei der letzte Schritt aus dem Additionstheorem für cos(α − β) folgt.

Wir können ϕ := α − β ohne Einschränkung als Winkel in [0, 2π) betrachten. Im Fall
ϕ ∈ [0, π] folgt dann direkt die Behauptung. Falls ϕ ∈ (π, 2π), dann ergibt sich die
Aussage durch Betrachtung von ϕ0 := 2π − ϕ, da cos ϕ0 = cos ϕ. 

Der voranstehende Satz bietet auch eine geometrische Interpretation des Skalarprodukts.
Ein Vektor u ∈ Rn ist ein Einheitsvektor, falls kuk = 1 (oder äquivalent kuk2 = u · u = 1).

Für zwei Vektoren u ∈ Rn und v ∈ Rn \ {0} heißt der Vektor

u·v
·v
v·v
orthogonale Projektion (oder Lotfußpunkt) von u auf den von v erzeugten Unterraum.
Nach Konstruktion ist dieser Vektor parallel zu v. Falls v ein Einheitsvektor ist, dann
beträgt die Länge dieses Vektors |u · v| und ist nach den vorherigen Überlegungen die
Länge der Projektion von u auf den von  v erzeugten
 Unterraum. Als Beispiel betrachte
1
man im R2 die Projektion auf den von erzeugten Unterraum, also die Projektion
0
auf die x-Achse.
Definition 10.5. Zwei Vektoren u, v ∈ Rn sind orthogonal (Schreibweise: u ⊥ v), falls
u · v = 0. Eine Folge von Vektoren v (1) , . . . , v (r) heißt orthogonal, falls
v (i) ⊥ v (j) für alle 1 ≤ i < j ≤ r.
Sind v (1) , . . . , v (r) zudem alle normiert, dann heißt die Folge orthonormal.
Definition 10.6. Sei U ⊆ Rn ein Unterraum. Die Vektoren v (1) , . . . , v (r) nennen wir eine
Orthonormalbasis von U , falls

(1) v (1) , . . . , v (r) orthonormal sind und

(2) v (1) , . . . , v (r) eine Basis von U ist.

1 0



Beispiel. 1. Die Vektoren 0
, 1
sind eine Orthonormalbasis von R2 .
√ √
2/2
− 2/2

2. Die Vektoren √
2/2
, √
2/2
sind ebenfalls eine Orthonormalbasis von R2 .
2 0



3. Die Vektoren 0
, 1/2
sind orthogonal, aber nicht orthonormal.

4. Die Vektoren
   
1 0
0 , −1 ∈ R3
0 0
76 1. LINEARE ALGEBRA

sind orthonormal aber keine Orthonormalbasis von R3 . Sie bilden aber eine Orthonormal-
basis des Unterraums
  
 x 
U = y  : x, y ∈ R .
0
 

Es gilt:

Lemma 10.7. Sind die Vektoren v (1) , . . . , v (r) ∈ Rn \ {0} orthogonal, dann sind sie linear
unabhängig.

Pr (i)
Beweis. Sei i=1 λi v = 0 eine Linearkombination des Nullvektors. Für jedes j ∈
{1, . . . , r} betrachten wir das Skalarprodukt jeder Seite der Gleichung mit dem Vektor
v (j) . Aufgrund der Orthogonalität der Vektoren v (1) , . . . , v (r) ergibt sich

r
!
X
0 = λi v (i) · v (j) = λj v (j) · v (j) .
i=1

Wegen v (j) 6= 0 ergibt sich λj = 0 für alle j. Folglich sind v (1) , . . . , v (r) linear unabhängig.


Satz 10.8. Jeder Untervektorraum U ⊆ Rn besitzt eine Orthonormalbasis.

Dieser Satz lässt sich durch das nachstehende algorithmische Verfahren konstruktiv bewei-
sen, das als das Gram-Schmidt Orthonormalisierungsverfahren bekannt ist. Sei u(1) , . . . , u(k)
eine gegebene Basis des k-dimensionalen Unterraums U . Wir können k ≥ 1 voraussetzen.

Ausgabe: Orthonormalbasis v (1) , . . . , v (k) von U .

1
(1) Setze v (1) = ku(1) k
u(1) .
(2) Für i = 2, . . . , k:
(a) Setze w(i) = u(i) − i−1 (i)
· v (j) ) · v (j) .
P
j=1 (u
(b) Setze v (i) = w(i) /kw(i) k.
 10. DAS SKALARPRODUKT UND ORTHOGONALITÄT 77

Korrektheit des Algorithmus: Offenbar gilt w(i) 6= 0 und kv (i) k = 1 für 1 ≤ i ≤ n. Zudem
gilt für t < i
i−1
X
(i) (t) (i)
w ·v = (u − (u(i) · v (j) ) · v (j) ) · v (t)
j=1
i−1
X
= u(i) · v (t) − (u(i) · v (j) )(v (j) · v (t) ) .
j=1

In einem induktiven Vorgehen kann hierbei vorausgesetzt werden, dass v (1) , . . . , v (i−1) be-
reits eine Orthonormalbasis des von diesen Vektoren aufgespannten Vektorraums ist. Es
folgt
w(i) · v (t) = u(i) · v (t) − (u(i) · v (t) )(v (t) · v (t) )
= u(i) · v (t) − (u(i) · v (t) ) · 1
= 0,
also auch v (i) · v (t) = 0. Damit ist gezeigt, dass das Verfahren eine Orthonormalbasis
generiert.

Beispiel. Gegeben seien die linear unabhängigen Vektoren

     
1 1 2
u(1) = 1 , u(2) =  1  , u(3) = −1 .
0 −4 1
Der Algorithmus berechnet zunächst
 √ 
1/√2
v (1) = 2−1/2 u(1) = 1/ 2 .
0
Es ergibt sich weiter
   √   
1 √ 1/√ 2 0
w(2) = u(2) − (u(2) · v (1) ) · v (1) =  1  − 2 1/ 2 =  0  .
−4 0 −4
 
0
Da kw(2) k = 4, erhalten wir v (2) = 14 w(2) =  0 . Weiter ist
−1
w(3) = u(3) − (u(3) · v (1) ) · v (1) − (u(3) · v (2) ) · v (2)
       
2 1/2 0 3/2
= −1 − 1/2 +  0  = −3/2 .
1 0 −1 0
78 1. LINEARE ALGEBRA

Schließlich ergibt sich  √ 

(3) 1/ √2
w
v (3) = = −1/ 2 .
kw(3) k
0

Die berechnete Orthonormalbasis lautet also

 √     √ 
1/√2 0 1/ √2
1/ 2 ,  0  , −1/ 2 .
0 −1 0

Wir übertragen den Begriff einer Orthonormalbasis auf Matrizen. Eine Matrix A ∈ Rn×n
heißt orthogonal, falls A> A = In .

Wir halten folgende Aussage ohne Beweis fest:

Satz 10.9. Für eine Matrix A ∈ Rn×n sind die folgenden Aussagen äquivalent.

(1) A ist orthogonal.

(2) A ist invertierbar und A−1 = A> .
(3) Die Spalten von A sind eine Orthonormalbasis von Rn .
(4) Für alle Vektoren u, v ∈ Rn gilt (Au)> (Av) = u> v.
(5) Für alle Vektoren u ∈ Rn gilt kAuk = kuk.

Beispiel. 1. Für jedes n ∈ N ist die Einheitsmatrix In orthogonal.

   
1 0 0 1
2. Die Matrizen , sind beide orthogonal.
0 −1 −1 0

3. Die Matrix
 √ √ 
1/√2 0 1/ √2
1/ 2 0 −1/ 2
0 −1 0
ist orthogonal.

Für die Determinante einer orthogonalen Matrix A ∈ Rn×n gilt | det A| = 1, denn
(det A)2 = det(A) · det(A) = det(A> ) · det(A) = det(A> A)
= det In = 1 .
Ferner lässt sich Aussage (4) des voranstehenden Satzes so interpretieren, dass Skalarpro-
dukte unter Anwendung orthogonaler Transformationen erhalten bleiben.
 10. DAS SKALARPRODUKT UND ORTHOGONALITÄT 79

Die Menge O(n) der orthogonalen Matrizen in Rn×n bildet eine Untergruppe der allge-
meinen linearen Gruppe GL(n) über den reellen Zahlen. Die Menge SL(n) der Matrizen
A ∈ GL(n) mit det(A) = 1 ist ebenfalls eine Untergruppe von GL(n). Auch die Menge
SO(n) = O(n) ∩ SL(n) der orthogonalen Matrizen A mit det(A) = 1 ist eine Untergruppe
von GL(n).

Die Gruppe SL(n) heißt die spezielle lineare Gruppe und die Gruppe SO(n) heißt die
spezielle orthogonale Gruppe.

Beispiel. 1. Die Matrix

 
cos α − sin α
∈ SO(2)
sin α cos α
mit einem α ∈ R stellt die Rotation um den Winkel α dar (siehe früherer Abschnitt).

2. Die Matrix  
cos α sin α
∈ O(2)
sin α − cos α
mit einem α ∈ R stellt eine Spiegelung dar (siehe früherer Abschnitt).

3. Da O(n) für n ≥ 2 eine Gruppe ist, sind beliebige Produkte der Matrizen in den ersten
beiden Beispielen orthogonal.
80 1. LINEARE ALGEBRA

11. Eigenwerte

Eigenwerte bilden ein wichtiges Konzept der linearen Algebra. Zur Motivation betrachten
wir einen Übergang von einer gegebenen Basis des Rn auf eine andere Basis. Die neue
Basis kann eine einfachere Form annehmen. Eine besonders einfache Form liegt vor, wenn
die durch die Basisvektoren definierte spaltenweise Matrix B eine Diagonalmatrix ist,
also nur in den Diagonalelementen von Null verschiedene Einträge enthalten kann. Ist A
die durch die ursprünglichen Basisvektoren spaltenweise definierte Matrix, dann wird der
Basiswechsel durch eine Gleichung der Form
 
λ1
S −1 AS = B = 
 .. 
. 
λn
mit einer invertierbaren Matrix S und Zahlen λ1 , . . . , λn ∈ R beschrieben, also AS = SB.
Die j-te Spalte dieser Matrixgleichung lautet

As(j) = λj s(j) ,

wobei s(1) , . . . , s(n) die Spalten von S sind.

Wir konzentrieren uns in diesem Abschnitt wiederum auf den Rn als zu Grunde liegenden
Vektorraum.

Definition 11.1. Sei A eine reelle n × n-Matrix. Eine Zahl λ ∈ R heißt Eigenwert von A,
falls es einen Vektor v ∈ Rn \{0} mit Av = λv gibt. Ein solcher Vektor v heißt Eigenvektor
von A zum Eigenwert λ.

Eine Zahl λ ∈ R ist also genau dann ein Eigenwert von A, wenn die Matrix A − λIn einen
von {0} verschiedenen Kern besitzt, denn für einen Vektor v ∈ Rn \ {0} gilt:

Av = λv ⇐⇒ (A − λIn )v = 0 .

Bemerkung. Allgemeiner spricht man auch bei komplexen Zahlen λ, die obige Definition
erfüllen, von einem Eigenwert von A. Da wir in dem vorliegenden Skript nicht näher auf
die komplexen Zahlen eingehen, beschränken wir uns hier auf die Betrachtung reeller
Eigenwerte.

Beispiel. Die Matrix

 
1 0
A=
0 2
 11. EIGENWERTE 81

hat die Eigenwerte 1 und 2, zugehörige Eigenvektoren sind

   
1 0
und .
0 1
Allgemein sind die Eigenwerte einer Diagonalmatrix
diag(c1 , . . . , cn )
immer genau die Zahlen c1 , . . . , cn .

Zur Berechnung der Eigenwerte einer n×n-Matrix A betrachtet man das charakteristische
Polynom (in einer Variablen λ) von A:
χA : R → R, λ 7→ det(A − λ · In )

Satz 11.2. Für eine n × n-Matrix A und λ ∈ R gilt: λ ist genau dann ein Eigenwert von
A, wenn χA (λ) = 0.

Beweis. Sei A eine n × n-Matrix und λ ∈ R. Genau dann ist λ ein Eigenwert, wenn das
homogene lineare Gleichungssystem (A − λIn )x = 0 eine von Null verschiedene Lösung
besitzt. Das ist genau dann der Fall, wenn rg(A − λIn ) < n, also wenn det(A − λIn ) = 0.


Lemma 11.3. Sei A eine n × n-Matrix und sei λ ∈ R ein Eigenwert von A. Die als
Eigenraum zum Eigenwert λ bezeichnete Menge
Eig(A, λ) = {v ∈ Rn : Av = λv}
bildet einen Unterraum von Rn .

Der Eigenraum zum Eigenwert λ besteht allen Eigenvektoren zum Eigenwert λ sowie aus
dem Nullvektor. Nach Konstruktion hat jeder Eigenraum mindestens die Dimension 1.

Beweis. Es genügt zu bebachten, dass für gegebene v, w ∈ Eig(A, λ) und α ∈ R die

Vektoren v + w und αv wieder in Eig(A, λ) enthalten sind. 

Berechnung der Eigenwerte und Eigenvektoren: Man stellt zunächst das charakteristische
Polynom χA (λ) auf. Seien λ1 , . . . , λ` die Nullstellen von χA (x). Zur Bestimmung der Menge
aller Eigenvektoren zu diesen Eigenwerten werden die Eigenräume
Eig(A, λi ) = ker(A − λi · In ) für 1 ≤ i ≤ `
bestimmt.
82 1. LINEARE ALGEBRA

Beispiel. Betrachte die Matrix

 
1 2
A= .
4 −1
Das charakteristische Polynom lautet
     
1 2 1 0 1−λ 2
χA (λ) = det −λ· = det
4 −1 0 1 4 −1 − λ
= (1 − λ)(−1 − λ) − 8 = λ2 − 9.
Die Nullstellen sind also λ1 = 3 und λ2 = −3. Für die Eigenräume Eig(A, ±3) ergibt sich
   
−2 2 1
Eig(A, 3) = ker = span ,
4 −4 1
   
4 2 −1
Eig(A, −3) = ker = span .
4 2 2
   
1 −1
Konkrete Eigenvektoren zu den Eigenwerten ±3 sind also und .
1 2

Sei A ∈ Rn×n . Falls A linear unabhängige Eigenvektoren v (1) , . . . , v (n) ∈ Rn zu reellen

Eigenwerten λ1 , . . . , λn besitzt (möglicherweise kommen einige Eigenwerte als mehrfache
Nullstellen des charakteristischen Polynoms vor), dann lassen sich die Beziehungen
A · v (i) = λv (i) , 1≤i≤n
in Matrixform schreiben:
A·S = S·D
mit S = (v (1) , . . . , v (n) ) ∈ Rn×n und einer Diagonalmatrix D = diag(λ1 , . . . , λn ). Man
spricht hierbei von einer Diagonalisierung der Matrix A. Aufgrund der vorausgesetzten
linearen Unabhängigkeit der Eigenvektoren lässt sich die Darstellung auch als A = S · D ·
S −1 oder S −1 · A · S = D schreiben.

Beispiel. 1. In dem vorhergehenden Beispiel ergibt sich die Diagonalisierung AS = SD

mit      
1 2 1 −1 3 0
A= , S= , D= .
4 −1 1 2 0 −3
2. Sei  
0 0 −2
A = 1 2 1  .
1 0 3
Das charakteristische Polynom ist χA (λ) = 2(λ − 1)(λ − 2)2 und hat die Nullstelle λ1
sowie die doppelte Nullstelle λ2 = 2. Allgemein wird die Vielfachheit einer Nullstelle λ im
charakteristischen Polynom als algebraische Vielfachheit des Eigenwerts λ bezeichnet.
 11. EIGENWERTE 83

Eigenvektoren zum Eigenwert 1:

   
−1 0 −2 −1 0 −2
 1 1 1  →  0 1 −1
1 0 2 0 0 0
Basis von Eig(A, 1): (−2, 1, 1)> .

Eigenvektoren zum Eigenwert 2:

   
−2 0 −2 −2 0 −2
 1 0 1 → 0 0 0 
1 0 1 0 0 0
Basis von Eig(A, 2): (−1, 0, 1)> , (0, 1, 0)> .

Es gilt also AS = SD mit

   
−2 −1 0 1 0 0
S= 1 0 1 , D = 0 2 0 .
1 1 0 0 0 2
Beachte: In diesem Beispiel war der Eigenraum zum doppelten Eigenwert 2 zweidimen-
sional. Das ist nicht immer so, es ist auch möglich, dass der Eigenraum eines doppelten
Eigenwerts nur eindimensional ist. Ohne Beweis sei genannt, dass die Dimension eines Ei-
genraums stets höchstens so groß wie algebraische Vielfachheit des zugehörigen Eigenwerts
ist.

Die Eigenwerte einer reellen Matrix sind die Nullstellen des charakteristischen Polynoms
χA (λ), welches reelle Koeffizienten hat. Einige der Nullstellen von χA (λ) sind eventuell
jedoch nicht reell, sondern komplex. Sie sind dann von der Form a + ib mit der imagi-
nären Einheit i und a, b ∈ R (siehe die Übungsaufgabe zu den komplexen Zahlen). Ohne
Detailbetrachtung verwenden wir die folgenden Fakten, die sich aus den grundlegenden
Eigenschaften komplexer Zahlen ergeben: Besitzt ein Polynom mit reellen Koeffizienten
eine nicht-relle Nullstelle z = a + ib, dann ist auch auch z := a − ib (bezeichnet als
konjugiert-komplexe Zahl zu z) eine Nullstelle des Polynoms. Ferner ist das Produkt zz
der komplexen Zahlen z und z eine reelle Zahl, die das Quadrat des euklidischen Ab-
stands der komplexen Zahl z vom Nullpunkt in der komplexen Zahlenebene angibt (kurz
geschrieben als |z|2 = zz).

Die nachstehende Klasse symmetrischer Matrizen kommt oft vor und hat die besondere
Eigenschaft, dass alle Eigenwerte reell sind.
Definition 11.4. Eine Matrix A ∈ Rn×n heißt symmetrisch, wenn
A> = A.
84 1. LINEARE ALGEBRA

Satz 11.5. Für jede symmetrische Matrix A ∈ Rn×n gilt:

1. Alle Eigenwerte von A sind reell.

2. Sind λ, µ Eigenwerte von A mit λ 6= µ und sind v, w ∈ Rn zugehörige Eigenvektoren,

dann ist v orthogonal zu w.

Im zweiten Beweisteil verwenden wir die folgende Rechenregel für das Skalarprodukt:
(M v) · w = v · (M > w) für alle v ∈ Rn , M ∈ Rm×n , w ∈ Rn . Sie gilt wegen
X XX  X X X
(M v) · w = (M v)j wj = mij vi wj = vi mij wj = vi (M > w)i
j j i i j i
>
= v · (M w) .

Beweis. 1. Gilt Av = λv mit einem Skalar λ ∈ C und einem von Null verschiedenen
Vektor v ∈ Cn , dann folgt aus Av = λv durch Übergang zu den (komponentenweise)
komplex-konjugierten Vektoren, dass
Av = A v = Av = λv = λv
und folglich
λv > v = (Av)> v = v > A> v = v > Av = λv > v .
Pn
Wegen v > v = i=1 |vi |2 > 0 ergibt sich λ = λ, das heißt λ ∈ R.

2. Es gilt
A symmetrisch
µ(v · w) = v · (µw) = v · (Aw) = (Av) · w = λ(v · w)
und damit
(λ − µ)(v · w) = λ(v · w) − µ(v · w) = 0.
Wegen λ − µ 6= 0 folgt v · w = 0. 

Das nachstehenden fundamentale Resultat zur Diagonalisierung symmetrischer Matrizen

geben wir ohne Beweis an.
Satz 11.6. Sei A eine symmetrische n × n-Matrix mit reellen Koeffizienten. Dann gibt
es eine orthogonale Matrix U ∈ Rn×n und reelle Zahlen
λ1 ≤ λ2 ≤ · · · ≤ λn ,
so dass
U −1 AU = diag(λ1 , . . . , λn ).
Die Zahlen λ1 , . . . , λn sind genau die Eigenwerte von A (hierbei treten einige Eigenwerte
eventuell mehrfach auf ).
 11. EIGENWERTE 85

Die Spalten der Matrix U bilden eine Orthonormalbasis des Rn , die aus Eigenvektoren der
Matrix A besteht. Matrizen, die nicht symmetrisch sind, besitzen nicht notwendigerweise
eine Basis aus Eigenvektoren.

Die Diagonalisierung einer Matrix ermöglicht in vielen Fällen große Rechenvorteile. Als
Beispiel betrachten wir die Bestimmung der k-ten Potenz

Ak = A
| · A{z· · · A}
k-mal

einer quadratischen Matrix A. Unter Verwendung der Diagonalisierung A = U DU −1 mit

einer Diagonalmatrix D = diag(λ1 , . . . , λn ) gilt nämlich

Ak = (U DU −1 )(U DU −1 ) · · · (U DU −1 ) = U Dk U −1
 k 
λ1
 λk2 0  −1
= U · ·U .

 . .. 
0 λkn

Vorgehen beim Diagonalisieren: Sei A eine symmetrische n × n-Matrix mit reellen Koef-
fizienten.

(1) Bestimme das charakteristische Polynom χA (λ) und seine Nullstellen.

(2) Für jede Nullstelle λ von χA (λ) ermittle Eig(A, λ).
(3) Verwende das Gram-Schmidt-Verfahren, um für jedes λ eine Orthonormalbasis
von Eig(A, λ) zu berechnen.
(4) Diese Basisvektoren, nach Eigenwerten aufsteigend geordnet, liefern die Spalten
der Matrix U .

Beispiel. Betrachte die symmetrische Matrix

1 −1 −1 −1
 
−1 1 −1 −1
A= −1 −1
.
1 −1
−1 −1 −1 1
Wir berechnen zunächst χA (λ) = det(A − λ · I4 ):

1 − λ −1 −1 −1 −λ −2 −2 −λ
   
 −1 1 − λ −1 −1   = det  0 2 − λ 0 λ − 2

χA (λ) = det 
 −1
,
−1 1 − λ −1   0 0 2 − λ λ − 2
−1 −1 −1 1 − λ −1 −1 −1 1 − λ
86 1. LINEARE ALGEBRA

wobei wir mit λ als einer Unbestimmten rechnen. Die Entwicklung nach der ersten Spalte
ergibt
   
2−λ 0 λ−2 −2 −2 −λ
χA (λ) = (−λ) · det  0 2 − λ λ − 2 − (−1) · det 2 − λ 0 λ − 2
−1 −1 1 − λ 0 2−λ λ−2
= −λ · (2 − λ)2 · ((1 − λ) − 1 − 1) + 1 · ((2 − λ)2 · (−λ − 2 − 2)
= (2 − λ)2 · (−λ(−λ − 1) − λ − 4)
= (2 − λ)2 (λ2 − 4)
= (λ − 2)3 (λ + 2) .
Die Nullstellen von χA (x) sind also ±2. Wir bestimmen nun die Eigenräume ker(A + 2I4 ),
ker(A − 2I4 ) mit dem Gauß-Verfahren:
3 −1 −1 −1
 
−1 3 −1 −1
A+2·I = −1 −1 3 −1 .


−1 −1 −1 3
0 −4 −4 8 −1 −1 −1 3
     
0 0 0 0
0 4 0 −4  → 0
 4 0 −4 → 0
 4 0 −4
→  .
0 0 4 −4   0 0 4 −4   0 0 4 −4
−1 −1 −1 3 −1 −1 −1 3 0 0 0 0
Der Kern ist eindimensional und wird durch den Vektor (1, 1, 1, 1)T aufgespannt. Folg-
lich bildet der einzelne Vektor 21 (1, 1, 1, 1)> eine Orthonormalbasis von Eig(A, −2). Wir
bestimmen nun ker(A − 2I):
−1 −1 −1 −1 −1 −1 −1 −1
   
−1 −1 −1 −1
 → 0 0 0 0

A−2·I = −1 −1 −1 −1 0
.
0 0 0
−1 −1 −1 −1 0 0 0 0
Der Kern ist dreidimensional und die drei Vektoren u(1) = (−1, 1, 0, 0)> , u(2) = (−1, 0, 1, 0)>
und u(3) = (−1, 0, 0, 1)> bilden eine Basis. Wir wenden nun das Gram-Schmidt-Verfahren
an. Normieren des ersten Vektors ergibt v (1) = √12 (−1, 1, 0, 0)> .

Für den zweiten Vektor bestimmen wir zunächst

1 1
w(2) = u(2) − (u(2) · v (1) )v (1) = (− , − , 1, 0)> .
2 2
Normieren dieses Vektors liefert
 >
1 1 1 1
(2)
v =p − , − , 1, 0 = √ (−1, −1, 2, 0)> .
3/2 2 2 6
 11. EIGENWERTE 87

Für den dritten Vektor berechnen wir zunächst

w(3) = u(3) − (u(3) · v (1) )v (1) − (u(3) · v (2) )v (2)
1 1 1 1 1 1
= (−1, 0, 0, 1)> + ( , − , 0, 0)> + ( , , − , 0)> = − (−1, −1, −1, 3)> .
2 2 6 6 3 3
Normieren dieses Vektors ergibt
1 1 1
v (3) = p · (−1, −1, −1, 3)> = √ (−1, −1, −1, 3)> .
4/3 3 2 3
Wir erhalten die Orthonormalbasis √12 (−1, 1, 0, 0)> , √16 (−1, −1, 2, 0)> , 2√1 3 (−1, −1, −1, 3)>
des Eigenraums Eig(A, 2). Um die Matrix S zu erhalten, fügen wir die Orthonormalbasen
der Eigenräume zusammen:
√ √ √ 
1/2 −1/√ 2 −1/√6 −1/(2√3)

1/2 1/ 2 −1/ 6 −1/(2 3)
S= p √ .
1/2 0 2/3 −1/(2 √ 3)
1/2 0 0 3/2
Die Matrix S ist orthogonal, d.h. S > = S −1 . Wir haben somit die Matrix A diagonalisiert:
−2 0 0 0
 
 0 2 0 0 >
A=S  0 0 2 0 S .


0 0 0 2

Anwendung: Der PageRank-Algorithmus

Wir diskutieren hier eine moderne von Eigenwerten der linearen Algebra in der Informa-
tik. Der nachstehend vorgestellte PageRank-Algorithmus spielt bei der Berechnung der
Reihenfolge von Suchergebnissen in Internet-Suchmaschinen eine zentrale Rolle.

In der historischen Entwicklung war ein Hauptgrund für das Aufstreben von Google im
Vergleich zu anderen existierenden Suchmaschinen die Ermittlung der „besten“ Sucher-
gebnisse. Während in der Anfangszeit der Internet-Suchmaschinen viele Systeme damit
zu kämpfen hatten, dass sich Benutzer erst seitenweise durch die Suchergebnisse klicken
mussten, empfahl sich Google dadurch, dass die führenden Suchergebnisse meist diejenige
Seite enthielten, nach der man suchte. Grundidee des dabei verwendeten Algorithmus war
und ist es, jeder beim automatischen Durchsuchen des Internets gefundenen WWW-Seite
eine Bewertungspunktzahl (Seitenrang, engl. page rank ) zuzuordnen, die die „Wichtigkeit“
der Seite bestimmt und bei der die Ausgabe der Suchergebnisse unter allen Seiten, die die
eingegebenen Suchbegriffe enthalten, die wichtigsten zuerst anführt.
88 1. LINEARE ALGEBRA

Zunächst wird das Internet als gerichteter Graph G = (V, E) mit n Knoten {1, . . . , n}
und der Kantenmenge E modelliert. Jede WWW-Seite entspricht einem Knoten und jeder
Link einer Kante; hierbei lassen wir Selbstreferenzen außer acht. Jede Kante (j, i) verse-
hen wir nun mit einer als Übergangswahrscheinlichkeit interpretierten Kantengewicht aij .
Wir stellen uns hierbei eine zufällige Bewegung (engl. random walk) durch den Graphen
vor: Befinden wir uns an einem Knoten j, dann gehen wir durch eine zufällig ausgewählte
ausgehende Kante zu einem Nachfolgeknoten i über. Die Gesamtheit der Übergangswahr-
scheinlichkeiten kann als Matrix A = (aij ) ∈ Rn×n geschrieben werden kann. Aufgrund des
wahrscheinlichkeitstheoretischen Hintergrunds sind alle Koeffizienten der Matrix A nicht-
negativ und ihre Spaltensummen gleich eins. Eine Matrix mit dieser Eigenschaft heißt
stochastische Matrix.

Lemma 11.7. Sei A eine stochastische Matrix. Dann ist die Zahl 1 ein Eigenwert von A.

Beweis. Die transponierte Matrix AT hat alle Zeilensummen 1, so dass gilt AT 1 = 1,

wobei 1 den aus lauter Einsen bestehenden Vektor bezeichnet. Folglich ist 1 ein Eigen-
vektor von AT zum Eigenwert 1. Da A und AT die gleichen Eigenwerte haben, ist 1 auch
ein Eigenwert von A. 

Mit tiefer gehenden Methoden (etwa dem Satz von Perron-Frobenius) lässt sich für jede
stochastische Matrix mit positiven Einträgen zeigen: Alle Eigenwerte haben den Betrag
höchstens 1, die Zahl 1 ist der einzige Eigenwert vom Betrag 1 und es gibt einen Eigen-
vektor zum Eigenwert 1, dessen Einträge alle positiv sind.

Die Idee ist es nun, einer Seite einen hohen Seitenrang zuzuordnen, wenn eine hohe Anzahl
wichtiger Seiten auf sie verweisen; diese Definition ist natürlich rekursiv. Bei der Präzi-
sierung stellen wir uns vor, dass jede Seite in einer Wahl eine Wähleinheit zu vergeben
hat, die sie anteilig auf die von ihr referenzierten Seiten verteilt. Die „Wichtigkeit“, die
eine Seite S1 auf eine Seite S2 so weitergibt, ist der entsprechende Anteil der Wähleinheit
multipliziert mit dem Seitenrang von S1 .

Bezeichnet xi den Seitenrang der i-ten Seite im System (i = 1, . . . , n), dann ergibt sich
ein lineares Gleichungssystem der Form
n
X
xi = aij xj , 1 ≤ i ≤ n,
j=1

wobei der Koeffizient aij das Gewicht ist, mit dem Seite i von Seite j referenziert wird
(siehe das Beispiel). Das System kann kurz als

x = Ax
 11. EIGENWERTE 89

2 4

Abbildung 1. Ein Graph auf vier WWW-Seiten.

geschrieben werden. Wir suchen also einen Eigenvektor zum Eigenwert 1. Die Summe der
Komponenten soll 1 betragen.
Beispiel 11.8. Wir betrachten in Abbildung 1 eine Situation mit den vier WWW-Seiten
„1“ bis „4“, und xi bezeichne den Seitenrang von Seite i.

Da Seite 4 von den Seiten 3 (als einziger ausgehender Link) und Seite 1 (als einer von zwei
Links) referenziert wird, gilt x1 = x21 + x13 , und entsprechende Gleichungen lassen sich für
alle Seiten aufstellen.

Die Lösungen des Eigenvektorproblems erfüllen die Eigenschaften des Seitenrangs. Vom
stochastischen Standpunkt entspricht eine Lösung x, dessen Komponenten auf 1 normiert
sind, den stationären Wahrscheinlichkeiten bei einem zufälligen Bewegen (engl. random
walk) durch den Graphen.
Beispiel 11.9. In Fortführung von Beispiel 11.8 ist der Seitenrang-Vektor ein Eigenvektor
der Matrix  
0 1/2 0 0
 0 0 0 1 
A =   1/2 1/2 0 0 


1/2 0 1 0

zum Eigenwert 1, dessen Komponenten sich zu 1 aufsummieren. Eine Lösung ist hier
(x1 , x2 , x3 , x4 ) = (0.154, 0.308, 0.231, 0.308). Interessanterweise hat die Seite 2 – gemein-
sam mit Seite 4 – den größten Seitenrang, obwohl nur eine einzige Seite auf sie verweist.
Grund hierfür ist, dass Seite 4 ihre gesamte Wähleinheit an Seite 2 weitergibt.

Besitzt jede WWW-Seite eine ausgehende Kante, dann besitzt das Gleichungssystem eine
von Null verschiedene Lösung; die Lösung muss jedoch nicht unbedingt eindeutig sein. Für
90 1. LINEARE ALGEBRA

den Fall, dass einige Seiten keine ausgehenden Links haben, ergibt sich darüber hinaus
ein allgemeines Eigenwertproblem mit a priori unbekanntem Eigenwert, das numerisch
effizient auch in sehr großen Größenordnungen (wie es für den realen WWW-Graphen
erforderlich ist) gelöst werden kann.

Um einen Eigenvektor zum Eigenwert 1 zu bestimmen, ist ein sehr großes, in der Regel
sehr dünnbesetztes Gleichungssystem zu lösen. Bei der großen Anzahl von WWW-Seiten
im Internet ist es praktisch nicht möglich, die entsprechende Matrix hinzuschreiben. Hier
spielen Verfahren der numerischen linearen Algebra eine große Rolle, auf die wir hier nicht
näher eingehen.
 12. SINGULÄRWERTE 91

12. Singulärwerte

Die zuvor behandelten Eigenwerte sind in vielen Bereichen von zentraler Bedeutung. Ei-
genwerte existieren jedoch nur bei quadratischen Matrizen. In diesem Abschnitt behandeln
wir eine Verallgemeinerung von Eigenwerten auf beliebige rechteckige Matrizen. Wir be-
ginnen mit folgender Vorbemerkung. Sind A, B reelle Matrizen der Größen m × n und
n × p, dann ist
(A · B)> = B > · A> .
Die Matrix A> A hat die Größe n × n und ist wegen (A> A)> = A> A symmetrisch. Die
Matrix A> A heißt die Gram-Matrix von A. Im Folgenden sei A reell. Dann sind aufgrund
der Symmetrie von A> A alle Eigenwerte von A> A reell. Wir zeigen, dass jeder Eigenwert
λ von A> A zudem nichtnegativ ist. Ist v ein Eigenvektor von A> A zum Eigenwert λ, dann
lässt sich kvk2 bezüglich der euklidischen Norm als Matrixprodukt kvk2 = v > v schreiben,
so dass
λkvk2 = v > (λv) = v > (A> Av) = (Av)> Av
= kAvk2 ≥ 0 ,
also λ ≥ 0. Eine symmetrische reelle Matrix, deren Eigenwerte alle nichtnegativ sind,
nennt man positiv semidefinit.
Definition 12.1. Sei A eine reelle m × n-Matrix. Die Singulärwerte σ1 , . . . , σr von A
√
sind die positiven Quadratwurzeln σi = λi > 0 der von Null verschiedenen Eigenwer-
te λi der Gram-Matrix K := A> A. Die zugehörigen Eigenvektoren von K heißen die
Singulärvektoren von A.

Bemerkung. Beachte, dass in manchen Darstellungen auch der Eigenwert Null der Gram-
Matrix K als Singulärwert von A betrachtet wird. Ferner beachte, dass wir im aktuellen
Abschnitt stets über dem Körper der reellen Zahlen arbeiten und die Bezeichnung K für
die Gram-Matrix verwendet wird.

Beispiel. Sei  
3 5
A= .
4 0
Die zugehörige Gram-Matrix ist
    
> 3 4 3 5 25 15
K=A A= =
5 0 4 0 15 25
mit Eigenwerten λ1 = 40, λ2 = 10 sowie zugehörigen Eigenvektoren
   
(1) 1 (2) 1
v = , v = .
1 −1
92 1. LINEARE ALGEBRA
√ √
Die Singulärwerte von A sind daher σ1 = 40 ≈ 6.325 und σ2 = 10 ≈ 3.162 mit v (1) und
v (2) als Singulärvektoren. Die Singulärwerte von A stimmen nicht mit den Eigenwerten
von A überein, denn die Eigenwerte sind
1 √ 1 √
λ1 = (3 + 89) ≈ 6.217, λ2 = (3 − 89) ≈ −3.2170.
2 2
Die Singulärvektoren von A stimmen auch nicht mit den Eigenvektoren von A überein.

Für symmetrische Matrizen gibt es einen engen Zusammenhang zwischen den Singulär-
werten und den Eigenwerten.

Satz 12.2. Sei A ∈ Rn×n eine symmetrische Matrix. Dann stimmen die Singulärwerte mit
den Absolutwerten der von Null verschiedenen Eigenwerte überein. Die Singulärvektoren
stimmen mit den Eigenvektoren der von Null verschiedenen Eigenwerte überein.

Beweis. Aufgrund der Symmetrie der Matrix A hat die Gram-Matrix die Eigenschaft
K = A> A = A · A = A2 . Ist v ein Eigenvektor von A zum Eigenwert λ, dann gilt also
Kv = A2 v = A(λv) = λAv = λ2 v.
Jeder Eigenvektor v von A ist daher ein Eigenvektor von K zum Eigenwert λ2 . Folglich
ist eine Eigenvektorbasis von A auch eine Eigenvektorbasis von K und die Eigenvektoren
von A zu den von Null verschiedenen Eigenwerten sind die Singulärvektoren von A. 

Wir können nun folgende zentrale Aussage der Singulärwertzerlegung (SVD, singular value
decomposition) formulieren.

Satz 12.3. Zu jeder reellen m × n-Matrix A vom Rang r > 0 existiert eine Faktorisierung
A = P Σ Q> ,
wobei P eine m × r-Matrix mit orthonormalen Spalten ist, Σ = diag(σ1 , . . . , σr ) eine
r × r-Diagonalmatrix mit den Singulärwerten in den Diagonaleinträgen ist und Q> eine
r × n-Matrix mit orthonormalen Zeilen ist.

Mit nachfolgendem Rechenschema lässt sich eine Singulärwertzerlegung einer Matrix A ∈

Rm×n bestimmen. Die nachstehende Beschreibung des Rechenschemas liefert auch den
Beweis des Satzes. Seien r = rg A und σ1 , . . . , σr die Singulärwerte von A, aufgezählt
mit Vielfachheiten. Seien q (1) , . . . , q (r) orthonormale Eigenvektoren der Gram-Matrix K =
A> A, die zu von Null verschiedenen Eigenwerten korrespondieren. Es kann gezeigt werden
(siehe die Bemerkung nach dem Beweis), dass rg K = rg A = r und dass die Bildvektoren
w(i) := Aq (i) , 1 ≤ i ≤ r,
 12. SINGULÄRWERTE 93

Norm σi haben und zueinander orthogonal sind. Setze nun

w(i) Aq (i)
p(i) := = , 1 ≤ i ≤ r.
σi σi
Die Matrizen P = (p(1) , . . . , p(r) ), Σ = diag(σ1 , . . . , σr ), Q = (q (1) , . . . , q (r) ) erfüllen dann
Q> Q = I und P > P = I.

Behauptung: Es gilt AQ = P Σ und A = P ΣQ> . (Achtung: Q und P sind im Allgemeinen

keine quadratischen Matrizen.)

Für die j-te Spalte von P Σ gilt

σj p(j) = Aq (j) , 1 ≤ j ≤ n,
also ist AQ = P Σ. Wegen Q> Q = I folgt
A = P ΣQ> .
Um den letzten Schritt einzusehen, erweitert man die n×r-Matrix Q zu einer orthogonalen
n×n-Matrix Q̄ und erweitert P und Σ um Nullen zu einer m×n-Matrix bzw. n×n-Matrix,
so dass A = AQ̄Q̄−1 = AQ̄Q̄> = P̄ Σ̄Q̄> = P ΣQ> .

Bemerkung. Die im Beweis verwendeten Eigenschaften

(1) rg A = rg K,
(2) w(i) w(j) = 0,
(3) kw(i) k2 = σi2 ,

ergeben sich wie folgt.

(1) Da A eine m × n-Matrix und K eine n × n-Matrix ist, genügt es nach der Dimensi-
onsformel zu zeigen, dass ker(A) = ker(K).

„⊆“: Falls Ax = 0, dann gilt natürlich auch Kx = AT Ax = 0.

„⊇“: Sei x gegeben mit AT Ax = 0. Dann ist 0 = xT AT Ax = (Ax)T (Ax) = kAxk2 . Es folgt
Ax = 0. Damit ist insgesamt die Aussage (1) gezeigt.

(2)
Def. σj
w(i) · w(j) = (Aq (i) )> Aq (j) = (q (i) )T (A> Aq (j) ) = (q (i) )> σj2 q (j)
(
0 falls i 6= j,
=
σj2 falls i = j.

(3) Mit (2) ergibt sich unmittelbar kw(i) k2 = w(i) · w(i) = σi2 .
94 1. LINEARE ALGEBRA
 
1 1 0
Beispiel. Sei A = . Die Gram-Matrix K = A> A ist
0 1 1
 
1 1 0
>
A A = 1 2 1 .
0 1 1
√
Da K die Eigenwerte 3, 1, 0 hat, sind die Singulärwerte von A also 3, 1. Sei Q = (q (1) , q (2) )
eine Matrix mit orthonormalen Spalten, die Eigenvektoren zu K von 3 bzw. 1 sind,
1 
√ − √1
 6 2
Q = (q (1) , q (2) ) =  √26 0  .
√1 √1
6 2
Wegen √  
1 (2) 1 √ −1
 
(1) 1 (1) 2 1 (2)
p = √ Aq = , p = Aq = 2
3 2 1 1 2 1
lautet mit der Setzung √  
(1) 2 1 −1
(2)
P = (p , p ) =
2 1 1
eine Singulärwertzerlegung von A also
√ 
3 0
A = P Q> .
0 1

Die Singulärwertzerlegung bietet eine fundamentale Technik zur Datenkompression und

hat damit zahlreiche Anwendungen im Bereich Data Science.

Beispiel. Wir betrachten Schwarzweißbilder bestehend aus m×n Bildpunkten, bei denen
der Grauwert jedes Bildpunktes durch eine ganze Zahl (zwischen Null (entspricht weiß)
und einem Maximalwert (entspricht schwarz)) gegeben ist. Das Schwarzweißbild kann
als eine reelle Matrix A aufgefasst werden. Sei A = P ΣQ> eine Singulärwertzerlegung
von A mit Σ = diag(σ1 , . . . , σr ) und absteigenden Singulärwerten σ1 ≥ · · · ≥ σr . Die
Singulärwertzerlegung kann auch in der Form
Xr
A= σj p(j) q (j)
j=1

geschrieben werden, wobei p(j) bzw. q (j) die j-te Spalte von P bzw. Q ist. Da die Spalten
von P und von Q orthonormal sind, ist der „Einfluss“ der Terme zu großen Singulärwer-
ten auf die Summe großer als der Terme zu kleinen Singulärwerten. Als näherungsweise
Darstellung für A kann daher eine Teilsumme betrachtet werden, deren Summenindex nur
von 1 bis zu einem Wert k < r läuft. In vielen typischen realen Situationen ist bereits für
 12. SINGULÄRWERTE 95

Abbildung 2. Ein Schwarzweißbild mit Grauwerten in jedem Bildpunkt

lässt sich als reelle Matrix interpretieren.

Abbildung 3. Approximationen mittels der Singulärwertzerlegung für k =

30 bzw. k = 100.

recht kleine Werte von k der Approximationsfehler klein. Für kleine k wird jedoch viel
weniger Platz zum Speicher der Daten (hier: Bilddaten) benötigt.

Exemplarisch betrachten wir in Abbildung 2 ein Bild mit 2160 × 3840 Bildpunkten:

Abbildung 3 zeigt die Approximationen, bei denen in der Singulärwertzerlegung nur bis
zum Index 30 bzw. 100 summiert wird.

Derartige Anwendungen von Singulärwerten sind nicht auf klassische Bilddaten beschränkt,
sondern stehen immer dann zur Verfügung, wenn Daten durch reelle Matrizen beschrie-
ben werden. Solche Situation liegen in vielfältigen Kontexten vor (z.B. Unternehmen:
Welche Kunden kaufen wieviel von welchem Produkt? Welche Kunden sehen sich welche
Streaming-Filme an und wie oft?), und die Singulärwertzerlegung bietet eine Methode
96 1. LINEARE ALGEBRA

der Struktur- und damit zur Datenanalyse (z.B. beim Entwurf von Empfehlungssystemen
(„recommender systems“): welchem Kunden sollen welche weiteren Produkte empfohlen
werden).
 KAPITEL 2

Diskrete Mathematik

In der diskreten Mathematik existieren verschiedene zentrale Grundmodelle, und sie be-
treffen eine Reihe von Teilgebieten und Anwendungsgebieten: Kombinatorik/ganze Zah-
len, Modulare Arithmetik und endliche Gruppen, Graphen, endliche Körper, Polyeder,
lineare Optimierung, kombinatorische Optimierung, Codierungstheorie, Kryptographie,
...

In der hier vorliegenden Darstellung werden nur einige grundlegende Aspekte und The-
menstränge erfasst. Für einige hier nicht behandelte Teilthemen der diskreten Mathematik
(insbesondere die Behandlung von Graphen) sei auf die Einführungsvorlesung „Diskrete
Modellierung“ im Bachelor Informatik verwiesen.

In den ersten Betrachtungen stellen wir einige Zählprinzipien zusammen und bauen auf
diesen dann auf.

97
98 2. DISKRETE MATHEMATIK

1. Zählen

Wir stellen einige grundlegende Zählprinzipien zusammen. Bekanntlich bezeichnet für eine
natürliche Zahl n die Fakultät n! den Wert
n! = 1 · 2 · 3 · · · n .
Wir setzen 0! = 1; dann gilt für n ≥ 0 die Rekursionsformel (n + 1)! = (n + 1)n! . Die
Fakultätsfunktion wächst sehr rasch; beispielsweise ist 10! = 3 628 800. Die Anzahl der
Permutationen einer n-elementigen Menge beträgt n! .

n


Binomialkoeffizienten. Für n ∈ N0 und 0 < k ≤ n ist der Binomialkoeffizient k
definiert als  
n n(n − 1) · · · (n − k + 1) n!
:= = .
k k! k!(n − k)!
Wir setzen n0 := 1.

Satz 1.1. Die Anzahl der k-elementigen Teilmengen einer nichtleeren Menge mit n Ele-
n


menten beträgt k , wobei 0 ≤ k ≤ n.

Beweis. Es gibt n · (n − 1) · · · (n − k + 1) = n!/(n − k)! Möglichkeiten, die k Elemente

auszuwählen, wenn die Reihenfolge berücksichtigt wird. Durch Division durch die Anzahl
n! n


k! der Anordnungen ergibt sich (n−k)!k! = k . 

Aus der Definition der Binomialkoeffizienten folgt unmittelbar die Symmetriebeziehung

   
n n! n
= = .
k k!(n − k)! n−k
Darüber hinaus gilt:
Satz 1.2. Für n ∈ N0 und 0 ≤ k < n genügen die Binomialkoeffizienten der Rekursions-
formel      
n+1 n n
= + .
k+1 k k+1

Beweis. Für 0 ≤ k < n gilt

   
n n n! n!
+ = +
k k+1 k!(n − k)! (k + 1)!(n − k − 1)!
 
n! 1 1
= +
k!(n − k − 1)! n − k k + 1
 
n! n+1 n+1
= = .
k!(n − k − 1)! (n − k)(k + 1) k+1
 1. ZÄHLEN 99

Mit Hilfe der Rekursionsformel und der Werte 00 = nn = 1 können die Binomialkoef-

fizienten sukzessive berechnet werden. In der nachfolgend illustrierten Tabellierung der

Binomialkoeffizienten im
Pascalschen Dreieck werden in Zeile n (n ≥ 0) die Binomialko-
effizienten 0 , 1 , . . . , nn aufgeführt. Die Ränder des Pascalschen Dreiecks bestehen aus
n

n

Einsen, und jede weitere Zahl ist aufgrund der Rekursionsformel die Summe der beiden
schräg darüber stehenden.

n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
n=5 1 5 10 10 5 1
n=6 1 6 15 20 15 6 1
n=7 1 7 21 35 35 21 7 1

Der Binomialsatz. Bereits aus der Schule ist die binomische Formel (x + y)2 = x2 +
2xy + y 2 für reelle Variablen x, y wohlbekannt. Mittels Binomialkoeffizienten lässt sich für
n ≥ 0 unmittelbar die als Binomialsatz bekannte Verallgemeinerung
n  
n
X n k n−k
(x + y) = x y
k=0
k
angeben. Denn beim Ausmultiplizieren des linken Produkts entsteht ein Term xk y n−k für
ein festes k immer dann, wenn in k der Klammern die Variable x und
und in den n − k
verbleibende Klammern die Variable y gewählt wird; hierfür gibt es nk Möglichkeiten.

Für die Spezialfälle (x, y) = (1, 1) und (x, y) = (−1, 1) ergeben sich als Spezialfälle die
Formeln
n  
n
X n
2 = , n≥0
k=0
k
n  
k n
X
und 0 = (−1) , n ≥ 1.
k=0
k

Notation: Mit der Kurzschreibweise [n] wird die Menge {1, . . . , n} bezeichnet.
100 2. DISKRETE MATHEMATIK

2. Die Einschluss-Ausschluss-Formel

Die nachstehende Einschluss-Ausschluss-Formel erfasst die Bestimmung der Kardinalität

einer Vereinigung nicht-disjunkter endlicher Mengen.

Satz 2.1. Für endliche Mengen A1 , . . . , An gilt

n
[ n
X X
(3) Ak = (−1)k+1 |Ai1 ∩ Ai2 ∩ · · · ∩ Aik | .
k=1 k=1 1≤i1 <i2 <···<ik ≤n

Im Fall n = 2 gilt also

|A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |
und im Fall n = 3
|A1 ∪ A2 ∪ A3 | = |A1 | + |A2 | + |A3 | − |A1 ∩ A2 | − |A1 ∩ A3 | − |A2 ∩ A3 | + |A1 ∩ A2 ∩ A3 | .

Wir geben einen Beweis an, der auf dem Binomialsatz beruht.

Beweis. Setze A := nk=1 Ak . Für jedes gegebene a ∈ A untersuchen wir, wie oft a auf
S

der rechten Seite von (3) gezählt wird. Seien i1 , . . . , it mit einem t ≥ 1 die Indizes, so
dass a in Ai1 , . . . , Ait , aber nicht in den Mengen mit anderen Indizes enthalten ist. Auf
der rechten Seite von (3) wird a zunächst t-mal
gezählt (für den Summenindex k = 1),
anschließend für den Summenindex k = 2 dann 2t -mal abgezogen, für k = 3 dann wieder
t


3
-mal gezählt, usw. Insgesamt ergibt sich für das Zählen des Elements a auf der rechten
Seite
    
t t t+1 t
t− + − · · · + (−1)
2 3 t
t  
X t
= (−1) · (−1)k
k=1
k
= (−1) · ((1 − 1)t − 1)
= 1
nach dem oben gesehenen Spezialfall des Binomialsatzes. 

Oft wird die Einschluss-Ausschluss-Technik in folgender Version verwendet:

Satz 2.2 (Einschluss-Ausschluss-Prinzip). Sei S eine n-elementige Menge und E1 ,

. . . , Er eine Menge von Eigenschaften, die die Elemente von S besitzen oder nicht. Be-
zeichne mit N (Ei1 , . . . , Eik ) die Anzahl der Elemente die (mindestens) die Eigenschaften
 2. DIE EINSCHLUSS-AUSSCHLUSS-FORMEL 101

Ei1 , . . . , Eik erfüllen. Für die Anzahl N0 der Elemente, die keine der Eigenschaften erfüllt,
gilt dann
X X X
N0 = n − N (Ei ) + N (Ei , Ej ) − N (Ei , Ej , Ek ) + · · ·
i i<j i<j<k
r
+(−1) N (E1 , E2 , . . . , Er ) .

Beweis. Mit der Bezeichnung Ai = {x ∈ S : x hat Eigenschaft Ei } gilt N (Ei1 , . . . , Eik ) =

|Ai1 ∩ · · · ∩ Aik |. Die Aussage folgt daher aus Formel (3). 
102 2. DISKRETE MATHEMATIK

3. Grundlegendes zu den natürlichen und den ganzen Zahlen

Wir erinnern an die strukturellen Eigenschaften natürlicher und ganzer Zahlen:

Die Addition und Multiplikation in der Menge Z der ganzen Zahlen genügen den folgenden
fünf Gesetzen:

(R1) Addition und Multiplikation sind assoziativ :

(a + b) + c = a + (b + c) und (a · b) · c = a · (b · c) .
(R2) Addition und Multiplikation sind kommutativ :
a + b = b + a und a · b = b · a .
(R3) Es existiert ein neutrales Element bezüglich der Addition (Nullelement, 0) und
ein neutrales Element bezüglich der Multiplikation (Einselement, 1):
0 + a = a und 1 · a = a .
Es ist 0 6= 1.
(R4) Jedes Element a besitzt ein additives Inverses (−a).
(R5) Es gilt das Distributivgesetz
a · (b + c) = a · b + a · c .

Bemerkung. Allgemein sagt man, dass eine Menge R zusammen mit zwei Operatio-
nen ⊕ und einen kommutativen Ring mit Einselement definiert, wenn die Regeln R1
bis R5 erfüllt sind. (Lässt man die Forderung der Kommutativität an die multiplikative
Operation weg, dann spricht man von einem Ring mit Einselement.) Aus R1 bis R5 erge-
ben sich weitere Regeln, die in Z selbstverständlich sind. Wir kommen später auf andere
kommutative Ringe und ihre Rechenregeln zurück.

Seien a, b ∈ Z. Wir sagen a teilt b, wenn eine ganze Zahl m mit b = am existiert.
Schreibweise a | b. Insbesondere teilt also jede Zahl a ∈ Z die Null. Falls a 6= 0 ist, dann
folgt aus a | b, dass der Bruch ab eine ganze Zahl ist und dass |a| ≤ |b|. Falls a > 0 und a
kein Teiler von b ist, dann können wir b immer noch durch a teilen, allerdings mit Rest.
Der Rest r bei der Division b ÷ a ist eine ganze Zahl r, die 0 ≤ r < a erfüllt. Bezeichnet
q den Quotienten einer Division mit Rest, dann ist also
b = aq + r .

Der größte gemeinsame Teiler zweier von Null verschiedener ganzer Zahlen ist die größte
natürliche Zahl, die sowohl a als auch b teilt,
ggT(a, b) := max{k ∈ N : k teilt a und k teilt b} .
 3. GRUNDLEGENDES ZU DEN NATÜRLICHEN UND DEN GANZEN ZAHLEN 103

Ferner setzt man ggT(a, 0) := |a|, ggT(0, b) := |b|, so dass insbesondere ggT(0, 0) = 0.
Analog ist das kleinste gemeinsame Vielfache von a, b 6= 0 die kleinste natürliche Zahl,
die sowohl von a als auch von b geteilt wird:
kgV(a, b) := min{k ∈ N : a teilt k und b teilt k} .
Ferner ist kgV(a, 0) := 0, kgV(0, b) := 0, kgV(0, 0) := 0.

Bemerkung. Die Begriffe des größten gemeinsamen Teilers und des kleinsten gemein-
samen Vielfachen verallgemeinern sich in natürlicher Weise auf mehr als zwei Zahlen;
ggT(a1 , . . . , an ) bzw. kgV(a1 , . . . , an ). Gilt ggT(a1 , . . . , an ) = 1, so werden a1 , . . . , an tei-
lerfremd genannt.

Eine natürliche Zahl p ≥ 2 heißt prim, wenn 1 und p die einzigen positiven Teiler sind.
Jede natürliche Zahl n ≥ 2 lässt sich bekanntlich als Produkt von Primzahlen darstellen.
Satz 3.1. Jede natürliche Zahl n ≥ 2 besitzt eine eindeutige Darstellung als Produkt von
Primzahlen:
n = pe11 · pe22 · · · pekk
mit Primzahlen p1 < p2 < · · · < pk und e1 , . . . , ek ∈ N.

Tatsächlich erfordert ein vollständiger Beweis der Eindeutigkeitsaussage eine gewisse Sorg-
falt. Wir gehen die Eindeutigkeit deshalb erst in späteren Abschnitten an. Die Existenz
lässt sich wie folgt beweisen:

Beweis. Zum Nachweis der Existenz verwenden wir eine Induktion nach n.

n=2: klar.

Induktionsschritt: Sei n ∈ N mit n > 2. Falls n eine Primzahl ist, dann ist die Aussage
klar. Anderenfalls gibt es eine natürliche Zahl m ∈ {2, . . . , n − 1}, die n teilt; es gilt also
n = km mit einem k ≥ 2. Durch Anwendung der Induktionsvoraussetzung auf die Zahlen
k, m und Zusammensetzen der Primfaktorzerlegungen folgt die Behauptung. 

Für zwei gegebene Zahlen a, b ∈ N sind bei Kenntnis der Primfaktorzerlegungen

k
Y k
Y
a = pei i , b = pfi i
i=1 i=1

mit Primzahlen p1 , . . . , pk und ei , fi ∈ N0 der ggT und der kgV unmittelbar ablesbar:
k k
min{ei ,fi } max{ei ,fi }
Y Y
ggT(a, b) = pi , kgV(a, b) = pi .
i=1 i=1
104 2. DISKRETE MATHEMATIK

Hieraus ergibt sich auch, dass folgende Charakterisierung des ggT (für beliebig viele Zah-
len) im Fall r = 2 mit der obigen übereinstimmt: Eine nichtnegative Zahl d ∈ Z ist genau
dann der ggT von a1 , . . . , ar ∈ Z, wenn d | ai (1 ≤ i ≤ r) sowie

t | ai (1 ≤ i ≤ r) =⇒ t | d .

Wir stellen zudem einige weitere Rechenregeln für den größten gemeinsamen Teiler zu-
sammen.

Lemma 3.2. Es gelten die folgenden Rechenregeln:

(1) ggT(a, b) = ggT(b, a − bq) für a, b, q ∈ Z .

(2) Für a, b, c ∈ Z mit ggT(a, c) = 1 gilt ggT(ab, c) = ggT(b, c).

Beweis. (1) Der ggT von a und b teilt sowohl b als auch a − qb, und nach der voran-
stehenden Charakterisierung des ggT gilt damit ggT(a, b) | ggT(b, a − bq). Andererseits
teilt der ggT von b und a − qb auch a = (a − bq) + qb und b, und es folgt wieder mit der
voranstehenden Charakterisierung des ggTs, dass ggT(b, a − bq) | ggT(a, b). Also sind die
beiden ggTs gleich.

(2) Aus der Voraussetzung ggT(a, c) = 1 folgt dass a und c keine gemeinsamen Primfak-
toren haben. Damit folgt die Behauptung sofort aus der Formel für den ggT bei gegebener
Primfaktorzerlegung. 

Wir betrachten noch ein Beispiel mit einem ganz anderen kombinatorischen Aspekt der
natürlichen Zahlen.

Beispiel. Für eine natürliche Zahl n ist eine Partition von n eine nichtsteigende Folge
natürlicher Zahlen p1 , . . . , pk ∈ N, deren Summe n ergibt. Jede Zahl pi heißt ein Teil der
Partition. Die Partitionsfunktion p(n) bezeichnet die Anzahl der Partitionen der natürli-
chen Zahl n. Ferner setzen wir p(0) = 1.

Beispielsweise gibt es sieben verschiedene Partitionen der Zahl 5, nämlich

5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1

= 1 + 1 + 1 + 1 + 1,

so dass p(5) = 7. Die ersten Werte der Partitionsfunktion lauten p(2) = 2, p(3) = 3,
p(4) = 5, p(5) = 7, p(6) = 11, p(7) = 15.
 3. GRUNDLEGENDES ZU DEN NATÜRLICHEN UND DEN GANZEN ZAHLEN 105

Mit den Bezeichnungen

pu (n) = #Partitionen, bei denen alle Summanden ungerade sind,
pv (n) = #Partitionen, in denen alle Summanden verschieden sind
beobachten wir etwa pu (7) = pv (7) = 5. Die für pu (7) relevanten Partitionen sind 7,
5 + 1 + 1, 3 + 3 + 1, 3 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1, und die für pv (7) relevanten
Partitionen sind 7, 6 + 1, 5 + 2, 4 + 3, 4 + 2 + 1.

Tatsächlich gilt pu (n) = pv (n) für alle n ∈ N. Im Hinblick auf das Einschluss-Ausschluss-
Prinzip 2.1 ist
X X
pu (n) = p(n) − p(n − i) + p(n − i − j)
i gerade i<j, gerade
X
− p(n − i − j − k) + − · · · ,
i<j<k, gerade

so dass
pu (n) = p(n)
−p(n − 2) − p(n − 4) − p(n − 6) − · · ·
+p(n − 2 − 4) + p(n − 2 − 6) + p(n − 2 − 8) + · · ·
−p(n − 2 − 4 − 6) − · · ·
Für die Betrachtung von pv (n) sei Ei die Eigenschaft, dass die Zahl i mehrfach als Sum-
mand auftritt. Aus dem Einschluss-Ausschluss-Prinzip ergibt sich dann
pv (n) = p(n)
−p(n − 1 − 1) − p(n − 2 − 2) − p(n − 3 − 3) − · · ·
+p(n − 1 − 1 − 2 − 2) + p(n − 1 − 1 − 3 − 3) + · · ·
Durch zeilenweisen Vergleich der Ausdrücke für pu (n) und pv (n) erkennt man deren Gleich-
heit.
106 2. DISKRETE MATHEMATIK

4. Die Eulersche ϕ-Funktion

In diesem und dem nachfolgenden Abschnitt untersuchen wir eine grundlegende Funktion
auf den natürlichen Zahlen: die Eulersche ϕ-Funktion. Diese zeigt zentrale Prinzipien und
Beweistechniken auf und wird zudem bei der später behandelten Anwendung des RSA-
Schemas eine Rolle spielen.
Definition 4.1. Für n ∈ N ist ϕ(n) definiert als
ϕ(n) = |{m ∈ {1, 2, . . . , n} : ggT(n, m) = 1}| .
ϕ heißt die Eulersche ϕ-Funktion.

Zwei natürliche Zahlen, deren größter gemeinsamer Teiler 1 ist, werden auch relativ prim
genannt.
Beispiel 4.2. i) Es gilt ϕ(n) = n − 1 genau dann, wenn n prim ist.
ii) ϕ(6) = 2, da in {1, . . . , 6} genau die Zahlen 1, 5 relativ prim zu 6 sind.
iii) ϕ(8) = 4, da in {1, . . . , 8} genau die Zahlen 1, 3, 5, 7 relativ prim zu 8 sind.
iv) ϕ(12) = 4, da in {1, . . . , 12} genau die Zahlen 1, 5, 7, 11 relativ prim zu 12 sind.

Für n ≤ 12 lauten die Werte der ϕ-Funktion

n 1 2 3 4 5 6 7 8 9 10 11 12
ϕ(n) 1 1 2 2 4 2 6 4 6 4 10 4

Im Folgenden sehen wir, dass bei bekannter Primfaktorzerlegung einer Zahl n die Funktion
ϕ(n) leicht berechnet werden kann.
Satz 4.3. Es gilt

(1) ϕ(p) = p − 1, falls p prim;  

(2) ϕ(pk ) = pk − pk−1 = pk 1 − p1 , falls p prim und k ∈ N.
(3) Sind p1 , . . . , pr die unterschiedlichen Primteiler von n, dann ist
r  
Y 1
ϕ(n) = n 1− .
i=1
p i

Für eine Zahl n mit der Primzahldarstellung n = ri=1 pki i mit Exponenten ki ≥ 1 gilt
Q

also r
Y
pki i − piki −1 .


ϕ(n) =
i=1

Beweis. Aus Beispiel 4.2 wissen wir bereits ϕ(p) = p − 1 für p prim.
 4. DIE EULERSCHE ϕ-FUNKTION 107

Ist n = pk mit primem p, dann sind die Zahlen, die nicht relativ prim zu pk sind, Vielfache
von p, d.h., p, 2p, . . . , pk−1 p; innerhalb der Menge {1, . . . , n} gibt es pk−1 solche Vielfache.
Es verbleiben  
k k k−1 k−1 k 1
ϕ(p ) = p − p = p (p − 1) = p 1 − .
p
Zahlen, die relativ prim zu pk sind.

Die dritte Aussage ergibt sich aus dem Einschluss-Ausschluss-Prinzip 2.2. Bezeichnet Ei
die Eigenschaft, dass die gegebene Zahl n durch die Primzahl pi teilbar ist, dann folgt
Xn X n X n n
ϕ(n) = n − + − + · · · + (−1)r
i
pi pp
i<j i j i<j<k
pi pj pk p1 p2 · · · pr
r  
Y 1
= n 1− .
pi 
i=1

Die im nachstehenden Lemma auftretende Summation d|n bezeichnet von hier an die
positiven Teiler von n.
Lemma 4.4.
P
(1) Für n ∈ N gilt d|n ϕ(d) = n.
(2) Für teilerfremde m und n gilt
ϕ(mn) = ϕ(m)ϕ(n) .

Beispiel. ϕ(4·5) = ϕ(4)·ϕ(5) = 2·4 = 8. Tatsächlich sind die zu 20 teilerfremden Zahlen

in {1, . . . , 20} genau die Zahlen
{1, 3, 7, 9, 11, 13, 17, 19} .

Beweis.
Für die erste Aussage werden wir die folgende äquivalente Aussage zeigen:
n
P
d|n ϕ d = n.

Hierzu teilen wir die Menge {1, . . . , n} wie folgt auf: Für jeden Teiler d von n sei
Sd = {k ∈ {1, . . . , n} : ggT(k, n) = d} .

Je zwei solcher Mengen sind offenbar disjunkt und für die Vereinigung all dieser Mengen
S
gilt d|n Sd = {1, . . . , n}.

n


Behauptung: |Sd | = ϕ d
für jeden Teiler d von n.
108 2. DISKRETE MATHEMATIK

Ist eine Zahl k in einer Menge Sd enthalten, dann gilt k = md mit einer Zahl m ∈
{1, . . . , nd }, die teilerfremd zu nd ist. Also ist |Sd | = ϕ( nd ). Insgesamt ergibt sich
X n [ [
ϕ = |Sd | = Sd = n .
d
d|n d|n d|n

Ql f
Für die zweite Aussage betrachte die Primzahldarstellungen m = j=1 qj j und n =
Qr ei
i=1 pi mit den paarweise verschiedenen Primteilern q1 , . . . , ql , p1 , . . . , pr . Aus der zwei-
maligen Anwendung von Satz 4.3(3) folgt dann

l   r  
Y 1 Y 1
ϕ(mn) = mn 1− 1−
j=1
q j i=1
pi
l  ! r  !
Y 1 Y 1
= m 1− · n 1−
j=1
q j i=1
pi
= ϕ(m) · ϕ(n) .


Bemerkung. Zu einem späteren Zeitpunkt - im Rahmen der Behandlung des Chinesi-

schen Restsatzes – werden wir diese Multiplikativitätsaussage von einem etwas höheren
Standpunkt aus betrachten.

Anmerkungen. R. D. Carmichael stellte im Jahr 1922 die Vermutung auf, dass die
Gleichung ϕ(x) = n für kein n nur eine einzige Lösung besitzt. Mit anderen Worten: Für
jedes x ∈ N existiert mindestens ein y 6= x mit ϕ(x) = ϕ(y). (Tatsächlich hatte Carmichael
im Jahr 1907 zunächst einen – falschen – Beweis für diese Aussage veröffentlicht.)

Unter massivem Computereinsatz zeigten A. Schlafly und S. Wagon (1994), dass die Aus-
7
sage zumindestens bis zu der (extrem großen) Zahl von 1010 richtig ist. Durch Erweite-
10
rung dieses Resultats verbesserte K. Ford diese untere Schranke auf 1010 (Ann. Math.
150:283–311, 1999).

Tabelle der ersten Werte von ϕ(n) (beispielsweise hat der ϕ-Wert 2 die Vielfachheit 3,
da ϕ(3) = ϕ(4) = ϕ(6) = 2 und keine weitere Zahl den ϕ-Wert 2 hat); ungerade Zahlen
größer als 1 haben Vielfachheit 0, da ϕ(x) für x > 2 gerade ist.

ϕ-Wert 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48
Vielfachheit 2 3 4 4 5 2 6 0 6 4 5 2 10 0 2 2 7 0 8 0 9 4 3 2 11
 4. DIE EULERSCHE ϕ-FUNKTION 109

Eine Zahl n heißt perfekt, wenn die Summe aller ihrer Teiler, welche kleiner als n sind, die
Zahl n ergibt. Beispiel: 6 = 1 + 2 + 3 ist perfekt. Es ist keine einzige ungerade perfekte
Zahl bekannt, aber niemand kann beweisen, dass es tatsächlich keine gibt.
110 2. DISKRETE MATHEMATIK

5. Der euklidische Algorithmus

Der euklidische Algorithmus zur Berechnung größter gemeinsamer Teiler gehört zu den
ältesten Rechenverfahren. Er war schon Eudoxus (375 v. Chr.) bekannt und ist im Band 7
der „Elemente“ von Euklid (300 v. Chr.) beschrieben. Er ist von fundamentaler Bedeutung
und kommt in vielen Rechenprozeduren zur Anwendung.

Im Allgemeinen ist sehr aufwändig, eine Zahl in ihre Primfaktoren zu zerlegen (vgl. den
Abschnitt über kryptographische Protokolle). Daher ist es vom algorithmischen Stand-
punkt nicht zweckmäßig, bei der Berechnung des größten gemeinsamen Teilers zweier
Zahlen a und b auf die Primfaktorzerlegungen zurückzugreifen. Beim euklidischen Algo-
rithmus wird anders vorgegangen; der Algorithmus beruht auf der Division mit Rest. Wie
bereits aus Abschnitt 3 bekannt, gibt es zu ganzen Zahlen a, b 6= 0 Zahlen m, r ∈ Z mit
a = mb + r und 0 ≤ r < |b| .

Euklidischer Algorithmus:

Eingabe: a, b ∈ Z \ {0} .
Ausgabe: rj−1 = ggT(a, b).
Verfahren: Setze r−1 = a, r0 = b. Bestimme durch Division mit Rest sukzessive
r1 , . . . , rj−1 mit |b| > r1 > · · · > rj−1 > rj = 0, bis kein Rest mehr bleibt. ri+1 sei
also der Rest, der bei Division von ri−1 durch ri entsteht:

r−1 = m1 r0 + r1 ,
r0 = m2 r1 + r2 ,
..
.
ri−1 = mi+1 ri + ri+1 ,
..
.
rj−3 = mj−1 rj−2 + rj−1 ,
rj−2 = mj rj−1 ,

mit m1 , . . . , mj ∈ Z.

Termination: Da die Divisionsreste ri strikt fallen, bricht das Verfahren nach endlich
vielen Schritten ab.

Korrektheit: rj−1 teilt der Reihe nach rj−2 , rj−3 , . . . , r0 = b und r−1 = a, wie sich
sukzessive aus den Gleichungen ri−1 = mi+1 ri + ri+1 ergibt; also ist rj−1 ein Teiler von a
und b.
 5. DER EUKLIDISCHE ALGORITHMUS 111

Teilt umgekehrt z sowohl a als auch b, so teilt z der Reihe nach r1 , . . . , rj−1 wie aus den
Gleichungen ri+1 = ri−1 − mi+1 ri folgt; also ist rj−1 der größte unter den Teilern von a
und b.

Beispiel. Für a = 9876, b = 3456 ergibt sich

9876 = 2 · 3456 + 2964 ,

3456 = 1 · 2964 + 492 ,
2964 = 6 · 492 + 12 ,
492 = 41 · 12 (+ 0) .

D.h. ggT(9876, 3456) = 12.

Der größte gemeinsame Teiler der Zahlen a1 , . . . , an lässt sich als ganzzahlige Linearkom-
bination der Zahlen schreiben. Diese Darstellung geht auf Étienne Bézout (1730–1783)
zurück.

Satz 5.1 (Bézout). Zu a1 , . . . , an ∈ Z \ {0} gibt es λ1 , . . . , λn ∈ Z mit

ggT(a1 , . . . , an ) = λ1 a1 + · · · + λn an .

Beweis. Im euklidischen Algorithmus ist rj−1 eine ganzzahlige Linearkombination von

rj−2 und rj−3 . Durch sukzessive Betrachtung der Schritte j, j − 1, . . . , 1 des euklidischen
Algorithmus ergibt sich weiter, dass rj−1 damit auch eine Linearkombination von r−1 und
r0 ist.

Den Fall n > 2 kann man induktiv abhandeln: Sei d0 = λ01 a1 + · · · + λ0n−1 an−1 der ggT von
a1 , . . . , an−1 und d = µ1 d0 + µ2 an der ggT von d0 und an . Dann ist d der ggT von a1 , . . . , an
und als ganzzahlige Linearkombination von a1 , . . . , an darstellbar. 

Durch Erweiterung des euklidischen Algorithmus kann man gleichzeitig mit dem ggT
zweier Zahlen a und b auch eine Darstellung nach dem Satz von Bézout gewinnen. Man
bestimmt dazu ganze Zahlen

s−1 = 1 , s0 = 0 , t−1 = 0 , t0 = 1 ,
si−1 = mi+1 si + si+1 , ti−1 = mi+1 ti + ti+1 ,

unter Benutzung der vom euklidischen Algorithmus gewonnenen ganzen Zahlen m1 , . . . , mj .

Dann gilt
ggT(a, b) = rj−1 = asj−1 + btj−1 .
112 2. DISKRETE MATHEMATIK

Beweis. Es gilt sogar ri = asi + bti für alle −1 ≤ i < j. Für i = −1, 0 folgt dies aus der
Wahl von s−1 , s0 , t−1 , t0 , und der Induktionsschritt folgt aus

ri+1 = ri−1 − mi+1 ri

= asi−1 + bti−1 − mi+1 (asi + bti )
= asi+1 + bti+1 .

Beispiel. a = 9876, b = 3456.

i ri−1 ri mi+1 si−1 si ti−1 ti

0 9876 3456 2 1 0 0 1
/ /
1 3456 2964 1 0 1 1 −2
2 2964 492 6 1 −1 −2 3
3 492 12 41 −1 7 3 −20

Also ggT(9876, 3456) = 12 = 7 · 9876 − 20 · 3456.

Geschicktes Tabellieren mittels Rückwärtsrekursion. Wir stellen hier eine wei-

tere Möglichkeit vor, die Koeffizienten der ganzzahligen Linearkombination des größten
gemeinsamen Teiler zu bestimmen. Im Gegensatz zu der zuvor vorgestellten Vorwärtsme-
thode leitet es sich aus dem rückwärtigen Einsetzen von unten nach oben in der Tabelle
ab.

Wir verwenden wieder die Rekursionsbeziehung

ri−1 = mi+1 ri + ri+1 .

Ausgehend von der am Ende des Algorithmus ablesbaren Beziehung ggT(a, b) = rj−1 =
rj−3 − mj−1 rj−2 kann man durch Einsetzen der analogen Rekursionsbeziehung für rj−2
eine ganzzahlige Linearkombination für rj−1 in Abhängigkeit von rj−3 und rj−4 gewinnen,
usw. Wir setzen yj = 0 sowie yj−1 = 1 und bestimmen rekursiv

yi−1 = yi+1 − mi yi für i = j − 2, . . . , 0 .

Lemma 5.2. Es gilt

yi+1 ri−1 + yi ri = rj−1 = ggT(a, b)

für i = 0, . . . , j − 1.
 5. DER EUKLIDISCHE ALGORITHMUS 113

Beweis. Für i = j − 1 ist die Aussage klar. Bei Betrachtung der Rückwärtsreihenfolge
i = j − 1, . . . , 0 ergibt sich der Induktionsschritt aus

yi · ri−2 + yi−1 ri−1 = yi ri−2 + (yi+1 − mi yi )ri−1

= yi (ri−2 − mi ri−1 ) + yi+1 ri−1
= yi ri + yi+1 ri−1
Ind.-Annahme
= rj−1 = ggT(a, b) .

Für den Index i = 0 ergibt sich insbesondere die gesuchte Linearkombination

ay1 + by0 = rj−1 = ggT(a, b) .

Beispiel. a = 9876, b = 3456. Wir notieren die Reste sowie die Multiplikatoren und
bestimmen dann die Folge der yi in der Reihenfolge yj ( = 0), yj−1 ( = 1), yj−2 , . . . , y0 ,
also von unten nach oben. In der tabellarischen Bestimmung führen wir eine Spalte yi+1
links von der Spalte yi mit (man muss yi+1 auch gar nicht explizit aufführen). Anmerkung:
Bei der hier beschriebenen Methode wird der unterste Multiplikator mi+1 (also mj ) gar
nicht verwendet.
i ri−1 ri mi+1 yi+1 yi
0 9876 3456 2 7 -20 (da − 6 − 2 · 7 = −20)
1 3456 2964 1 −6 7 (da 1 − 1 · (−6) = 7)
2 2964 492 6 1 −6 (da 0 − 6 · 1 = −6)
3 492 12 41 0 1
Es ergibt sich die ganzzahlige Linearkombination des ggT als

7 · 9876 − 20 · 3456 = 12.

Bei der Berechnung eines Tabelleneintrags yi werden in der Rekursionsbeziehung yi =

yi+2 − mi+1 yi+1 die beiden y-Einträge der Zeile darunter (also yi+2 und yi+1 ) verwendet
sowie der Multiplikator in der Zeile des zu bestimmenden Eintrags.

Führt man die yi+1 -Spalte gar nicht auf, dann werden bei der Berechnung eines Tabellen-
eintrags yi die beiden y-Einträge darunter verwendet sowie der Multiplikator in der Zeile
des zu bestimmenden Eintrags. Eine Merkregel für die Rekursion ist dann:

„Unterunternachbar − Multiplikator · Unternachbar“

114 2. DISKRETE MATHEMATIK

Zu Beginn wird in die unterste Zeile (in der in der Spalte ri der ggT steht) eine 1 geschrie-
ben und darunter findet sich eine gedachte Null.

Das hier beschriebene Rechenschema benötigt (ausgehend von den zuvor bestimmten Mul-
tiplikatoren) beim Ausrechnen per Hand nur etwa den halben Aufwand verglichen mit der
zuerst vorgestellten Vorwärtsmethode.

Laufzeit des euklidischen Algorithmus. Der euklidische Algorithmus ist effizient in

dem Sinne, dass die Anzahl der benötigten Divisionen logarithmisch in den Eingabezahlen
a und b beschränkt ist.
Satz 5.3. Der euklidische Algorithmus benötigt bei der Eingabe a > b > 0 höchstens
log2 a + log2 b viele Divisionen.

Beweis. Wir behaupten, dass während jeder Iteration gilt

1
ri+1 < ri−1 .
2
Denn da die Reste ri strikt fallen, gilt (in der Division mit Rest ri−1 = mi+1 ri + ri+1 ),
dass mi+1 ≥ 1 und 0 ≤ ri+1 < ri , so dass ri−1 ≥ ri + ri+1 > 2ri+1 .

Bezeichnet j wieder die Anzahl der benötigten Divisionen des Algorithmus, dann folgt
wegen ri ri+1 < 12 ri−1 ri , dass
1 1
2 ≤ rj−2 rj−1 < r−1 r0 = ab.
2j−1 2j−1
Also 2j < ab, so dass nach Logarithmieren zur Basis 2 folgt: j < log2 a + log2 b. 

Die Laufzeit des Algorithmus kann präziser abgeschätzt werden, indem Eingaben a und
b betrachtet werden, für die besonders viele Divisionen anfallen. Ohne Einschränkung sei
a > b > 0; im Fall b > a > 0 werden a und b im ersten Schritt vertauscht.

Wir betrachten die durch

(a1 , b1 ) ≤ (a2 , b2 ) ⇐⇒ b1 < b2 oder (b1 = b2 und a1 ≤ a2 )
gegebene vollständige Ordnung auf Paaren natürlicher Zahlen (hierbei bedeutet „vollstän-
dig“, dass für je zwei gegebene Paare (a1 , b1 ) und (a2 , b2 ) mindestens eine der beiden Be-
ziehungen „≤“ oder „≥“ gilt). Das bezüglich dieser Ordnung kleinste Paar (a, b), für das j
Divisionen benötigt werden, ergibt sich, wenn man rj−1 und die mi möglichst klein wählt:
m1 = · · · = mj−1 = 1, mj = 2 und rj−1 = 1. Die Möglichkeit mj = 1 ist ausgeschlossen,
da mit rj = 0 dann rj−1 = rj−2 folgen würde. Die Gleichungen
rj−1 = 1 , rj−2 = 2 , ri−1 = ri + ri+1 für i = j − 2, . . . , 0
 5. DER EUKLIDISCHE ALGORITHMUS 115

bestimmen r−1 = a und r0 = b eindeutig.

Für das kleinste Paar (a, b), für das j Iterationen benötigt werden, gilt also der durch
folgende Tabelle beschriebene Zusammenhang:

j 1 2 3 4 5 6
a 2 3 5 8 13 21
b 1 2 3 5 8 13

Bezeichnet f0 = 0, f1 = 1, fi+2 = fi+1 + fi die als Fibonacci-Zahlen bekannte Zahlenfolge,

dann ist induktiv sofort ersichtlich, dass der euklidische Algorithmus bei Eingabe fj+2
und fj+1 genau j Divisionen benötigt.
Satz √5.4. Der euklidische Algorithmus
√
benötigt bei der Eingabe a > b > 0 höchstens
1+ 5 −1
c ln(b 5) Divisionen, mit c = (ln 2 ) ≈ 2.08.

Beweis. Aufgrund der Charakterisierung der worst-case Paare √ genügt es zu zeigen, dass
bei Eingabe a = fj+2 und b = fj+1 mit j ∈ N höchstens c ln(b 5) Divisionen erforderlich
sind.

Für die Eingabe a = fj+2 und b = fj+1 werden wie zuvor beschrieben j Divisionen
benötigt. Mit der Darstellung
√ !j √ !j
 
1 1+ 5 1− 5 
fj = √  −
5 2 2
√  √ j
1+ 5
(siehe Übungen) folgt wegen (1− 5)/2 ≈ −0.618 zunächst √1 ≤ fj +1 ≤ fj+1 =
5 2
√ √
b und damit j ln 1+2 5 ≤ ln(b 5). 

Wir können nun auch die in Satz 3.1 aufgeschobene Eindeutigkeit der Primfaktorzerlegung
nachweisen.
Lemma 5.5. (Euklid.) Wenn eine Primzahl p das Produkt ab zweier ganzer Zahlen a, b
teilt, dann teilt sie mindestens einen der beiden Faktoren.

Beweis. Wir nehmen an, dass p kein Teiler von a ist.

Zu zeigen: p | b.

Da p prim ist, gilt ggT(p, a) = 1. Nach dem Satz von Bézout existieren daher s, t ∈ Z mit
sp + ta = 1. Es folgt
spb + t(ab) = b .
116 2. DISKRETE MATHEMATIK

Da p die beiden Summanden auf der linken Seite teilt, folgt p | b. 

Induktiv ergibt sich daraus unmittelbar: Ist ein Produkt ri=1 ai von r > 2 ganzen Zahlen
Q

durch die Primzahl p teilbar, so ist mindestens ein Faktor durch p teilbar.

Beweis der Eindeutigkeit der Primfaktorzerlegung in Satz 3.1. Wir nehmen

an, dass es eine kleinste natürliche Zahl n mit zwei verschiedenen Primfaktorzerlegungen
n = p1e1 pe22 · · · pekk = q1f1 q2f2 · · · qlfl
und p1 < · · · < pk , q1 < · · · < ql gibt. Nach dem voranstehenden Lemma teilt jede
Primzahl pi als Teiler des rechten Produkts auch eine der Primzahlen qj , ist also gleich
dieser Primzahl. Ebenso ist jede der Primzahlen qj identisch mit einer der Primzahlen pi .
Es folgt die Gleichheit der Mengen
{pi : 1 ≤ i ≤ k} = {qj : 1 ≤ j ≤ l} .
Da die Zahlen pi und die Zahlen qj der Größe nach sortiert sind, erhalten wir r = s und
pi = qi (1 ≤ i ≤ k).

Annahme: Es existiert ein i mit ei 6= fi .

Qt
Sei t ein minimales solches i und ohne Einschränkung et < ft . Division durch n0 := i=1 pei i
liefert eine Zahl
k k
n Y Y f
n00 := 0 = pei i = pft t −et · pj j ,
n i=t+1 j=t+1
mit zwei verschiedenen Primfaktorzerlegungen. Wegen n00 < n ist dies ein Widerspruch
zur Minimalität von n.

Die Primfaktorzerlegung jeder Zahl n ist daher (bis auf die Reihenfolge der Faktoren)
eindeutig. 

Eine Division mit Rest hat man nicht nur für die ganzen Zahlen, sondern auch für wich-
tige andere Strukturen (z.B. Polynome in der Variablen x mit Koeffizienten aus einem
gegebenen Körper).
 6. MODULARE ARITHMETIK 117

6. Modulare Arithmetik

Beim Rechnen mit ganzen Zahlen ist es häufig von Vorteil, nicht mit den Zahlen selbst zu
operieren, sondern mit den Resten, die beim Teilen der Zahl durch einen fest vorgegebenen
Modul m ≥ 2 übrigbleiben.
Definition 6.1. Sei m ≥ 2 und a, b ∈ Z.

i) a und b heißen kongruent modulo m, falls m|(b − a), falls also a und b denselben
Rest bei Division durch m haben. Schreibweise: a ≡ b (mod m).
ii) Die Menge a := a + mZ = {a + mz : z ∈ Z} heißt Restklasse von a modulo m.
Die Menge aller Restklassen wird mit Zm oder Z/mZ bezeichnet.

Beispiel. Beispielsweise gilt also

3 ≡ 15 (mod 6) .
Die Restklasse von 3 modulo 6 ist
3 = 3 + 6Z = {. . . , −9, −3, 3, 9, 15, 21, . . .} .

Jede Restklasse besitzt einen Vertreter in der Menge {0, . . . , m − 1}.

Äquivalenzrelationen. Für den Umgang mit dem eben eingeführten Begriff der Kon-
gruenz ist es nützlich, die Eigenschaft „ist kongruent zu“ als Spezialfall einer in den nach-
folgenden Grundlagenbetrachtungen definierten Äquivalenzrelation zu erfassen.

Eine binäre Relation R (kurz: Relation) zwischen zwei Mengen A und B ist eine Teilmenge
des kartesischen Produkts A × B. Im Falle A = B spricht man von einer Relation auf der
Menge A. Beispielsweise wird auf der Menge R der reellen Zahlen durch
(a, b) ∈ R :⇐⇒ a < b
eine Relation definiert. Immer dann, wenn die Relation durch einen zweistelligen Operator
(wie hier „<“) definiert ist, können wir die Betrachtung einer Relation als Teilmenge mit
dieser Betrachtung mittels eines Operators identifizieren.

Eine Relation R auf einer Menge A heißt

• reflexiv, wenn für alle a ∈ A gilt (a, a) ∈ R;

• symmetrisch, wenn für a, b ∈ A mit (a, b) ∈ R stets folgt, dass (b, a) ∈ R.
• transitiv, wenn für a, b, c ∈ A mit (a, b) ∈ R und (b, c) ∈ R stets folgt, dass
(a, c) ∈ R.
118 2. DISKRETE MATHEMATIK

Eine Relation auf einer Menge A heißt Äquivalenzrelation, falls sie reflexiv, symmetrisch
R
und transitiv ist. In diesem Fall schreiben wir für (a, b) ∈ R auch a ∼ b oder kurz a ∼ b ,
wenn R aus dem Zusammenhang klar ist.

Für einen gegebenen Modul m ≥ 2 definiert die Relation „ist kongruent zu“ eine Äquiva-
lenzrelation auf der Menge Z, denn die Relation ist reflexiv, symmetrisch und transitiv.
Wir haben bereits gesehen, dass wir beim Umgang mit Resten entweder mit den Rest-
klassen oder mit Vertretern arbeiten können. Allgemein liegt die Bedeutung einer Äquiva-
lenzrelation R auf einer Menge A darin, dass immer dann, wenn eine Äquivalenzrelation
vorliegt, eine derartige Aufteilung der zu Grunde liegenden Menge A in paarweise dis-
junkte Teilmengen (Klassen) möglich ist. Für jedes a ∈ A ist die Äquivalenzklasse von a
definiert als die Menge aller Elemente in A, die mit a in Relation stehen:
R
[a] := {b ∈ A : a ∼ b} .

a heißt Repräsentant oder Vertreter der Klasse [a] . Man beachte, dass jedes b ∈ A mit
R
a ∼ b als Repräsentant für [a] Verwendung finden kann.

Wir kehren nun zurück zur Kongruenzrelation modulo m mit einer Zahl m ≥ 2. Die
Äquivalenzklassen dieser Äquivalenzrelation sind gerade die Restklassen modulo m. Jede
Äquivalenzklasse besitzt einen Vertreter in der Menge {0, . . . , m − 1}.

Wir betrachten nun Operationen auf den Restklassen. Für Restklassen a, b sei

a + b := a + b ,
a · b := a · b .

In dieser Definition ist zunächst die Wohldefiniertheit zu klären. Zu einer gegebenen Rest-
klasse modulo m gibt es unendlich viele Vertreter, so dass die angegebene Definition nur
dann sinnvoll ist, wenn sie unabhängig von der Wahl des Vertreters ist.

Beispiel. Sei m = 6. Die Restklasse

3 + 6Z = {. . . , −9, −3, 3, 9, 15, 21, . . .}

kann beispielsweise Restklasse zu a = 3 oder etwa auch als Restklasse zu a0 = 21 inter-

pretiert werden. Die Restklasse

4 + 6Z = {. . . , −8, −2, 4, 10, 16, 22, . . .}

kann beispielsweise als Restklasse zu b = 4 oder zu b0 = −8 interpretiert werden.

 6. MODULARE ARITHMETIK 119

Es gilt

a + b = (3 + 4) + 6Z ,
a0 + b0 = (21 + (−8)) + 6Z = 13 + 6Z .

Diese beiden Mengen stimmen überein.

Das nachfolgende Lemma besagt, dass sowohl die Addition als auch die Multiplikation
von Restklassen stets unabhängig von den gewählten Vertretern und damit wohldefiniert
ist.

Lemma 6.2. Sei m ≥ 2. Für a, a0 , b, b0 ∈ Z gilt

a ≡ a0 , b ≡ b 0 (mod m) =⇒ a + b ≡ a0 + b0 , ab ≡ a0 b0 (mod m) .

Folglich sind die angegebenen Vernüpfungen in Zm wohldefiniert.

Beispiel. Um beispielsweise die zwei Restklassen 3 und 5 in Z6 zu multiplizieren, genügt

es, beliebige Vertreter zu wählen, diese zu multiplizieren und die zugehörige Restklasse zu
betrachten. Bei Wahl der Vertreter 3 und 5 ergibt sich

3 · 5 + 6Z = 3 + 6Z .

Bei Wahl anderer Vertreter, etwa 9 und 11 ergibt sich die gleiche Restklasse, da

9 · 11 + 6Z = 3 + 6Z .

Beweis. Nach Voraussetzung gilt m|(a − a0 ) und m|(b − b0 ). Es folgt m|(a + b − (a0 + b0 )),
so dass
a + b ≡ a0 + b 0 (mod m) .
Wegen ab − a0 b0 = a(b − b0 ) + (a − a0 )b0 gilt auch m|(ab − a0 b0 ) ; folglich ist

a · b ≡ a0 · b 0 (mod m) .

Satz 6.3. Sei m ≥ 2. Die Menge Zm bildet mit den Operationen + und · einen kommu-
tativen Ring mit Einselement, der als Restklassenring modulo m bezeichnet wird. Hierbei
ist die Restklasse 0 von 0 das neutrale Element bezüglich der Addition und die Restklasse
1 von 1 das neutrale Element bezüglich der Multiplikation.
120 2. DISKRETE MATHEMATIK

Beweis. Die Rechenregeln eines Rings übertragen sich von Z unmittelbar auf Zm , z.B.
a + (b + c) = a + b + c = a + (b + c) = (a + b) + c = (a + b) + c .
Das Nullelement ist 0, das Einselement ist 1. 

ai 10i und b = bi 10i ganze Zahlen in Dezi-

P P
Beispiel 6.4. (Neunerprobe.) Seien a =
maldarstellung und c = ci 10i ihr Produkt. Dann gilt wegen 10 ≡ 1 (mod 9)
P
X X X
ai bi ≡ ab ≡ c ≡ ci (mod 9) .
Die Neunerprobe zur Kontrolle von Multiplikationen (bei der jede Zahl durch die Summe
ihrer Ziffern aus ihrer Dezimaldarstellung ersetzt wird) beruht auf dieser Feststellung.

Die Restklassenringe Zm haben Besonderheiten, wie man sie von Z nicht kennt.

Nullteiler: Im Gegensatz zu Z kann Zm Nullteiler enthalten, z.B. 2 · 3 = 0 in Z6 .

Genauer gilt für m ≥ 2: Zm enthält Nullteiler ⇐⇒ m ist keine Primzahl.
Einheiten: Sind a und m teilerfremd, dann gibt es ein b ∈ Zm mit a · b = 1 in Zm ,
d.h., a · b ≡ 1 (mod m). Diese Eigenschaft folgt unmittelbar aus dem Satz von
Bézout, der eine Darstellung der Form sa + tm = 1 mit s, t ∈ Z garantiert, d.h.
für b := s gilt ab ≡ 1 (mod m). Elemente in Zm , die bezüglich der multiplikativen
Operation invertiert werden können, heißen Einheiten.

Ein kommutativer Ring (R, ⊕, ) mit Einselement definiert einen Körper, wenn R \ {0}
bezüglich der multiplikativen Operation eine abelsche Gruppe bildet. Endliche Gruppen
werden im nächsten Abschnitt im Detail besprochen. Wir halten jedoch bereits fest.
Satz 6.5. Sei p ≥ 2. Zp ist genau dann ein Körper, wenn p prim ist.

Beweis. Siehe Übungen. 

Anmerkungen. Als Konsequenz aus den Operationen + und · auf Zm sind beispiels-
weise auch modulare Quadratwurzeln, also Lösungen von Gleichungen der Form
x2 ≡ a (mod m) ,
oder modulare Logarithmen, also Lösungen von Gleichungen der Form
ax ≡ b (mod m)
sinnvolle – und tatsächlich sehr wichtige – Konzepte.
 7. ENDLICHE GRUPPEN 121

7. Endliche Gruppen

In einem früheren Abschnitt haben wir uns bereits mit dem Konzept einer Gruppe befasst.
Zur Erinnerung: Eine nichtleere Menge G mit einer Verknüpfung ◦ : G × G → G heißt
Gruppe, wenn folgende Bedingungen erfüllt sind.

i) ∀a, b, c ∈ G : (a ◦ b) ◦ c = a ◦ (b ◦ c) (Assoziativität) ,
ii) ∃e ∈ G ∀a ∈ G : e ◦ a = a ◦ e = a (neutrales Element) ,
iii) ∀a ∈ G ∃b ∈ G a ◦ b = b ◦ a = e (inverses Element; Schreibweise a−1 ) .

Gilt darüber hinaus Kommutativität (d.h. a ◦ b = b ◦ a ∀a, b ∈ G), dann heißt G abelsch.

Beispielsweise bilden (Z, +) oder (Zn , +) für n ≥ 2 eine Gruppe. Beachte, dass beispiels-
weise (N, +) und (Z, ·) keine Gruppe bilden, denn die Mengen sind nicht bezüglich der
Inversenbildung abgeschlossen.

Definition 7.1. Eine Gruppe heißt endlich, wenn die zu Grunde liegende Menge G endlich
ist.

Unser Ziel ist es, einige zentrale Konzepte endlicher Gruppen zu behandeln. Als einen
Ausgangspunkt betrachten wir die Multiplikation im Restklassenring Zn (n ≥ 2). Aufgrund
der Eigenschaft 0 · x = 0 (mod n) für alle x ∈ Zn bildet Zn bezüglich der Multiplikation
offensichtlich keine Gruppe; denn wegen 0 · 0 müsste 0 das neutrale Element sein, was aber
im Widerspruch zu 0 · x = 0 (mod n) für x 6= 0 steht.

Wir fragen nun, ob eventuell Zn \ {0} bezüglich der Multiplikation eine Gruppe bildet?
Wegen 1 · x ≡ x (mod n) für alle x ∈ Zn \ {0} kommt 1 als neutrales Element in Frage.
Um die Frage nach der Existenz inverser Elemente zu klären, betrachten wir zunächst
zwei Beispiele.

Beispiel. a) Die Multiplikation auf Z5 \{0} ist durch folgende Verknüpfungstafel gegeben:

· 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1

Aus der Verknüpfungstafel ist ersichtlich, dass jedes Element ein inverses Element besitzt.
Z5 \ {0} definiert daher eine Gruppe bezüglich der Multiplikation.

b) Die Multiplikation auf Z6 \ {0} ist durch folgende Verknüpfungstafel gegeben:

122 2. DISKRETE MATHEMATIK

· 1 2 3 4 5
1 1 2 3 4 5
2 2 4 0 2 4
3 3 0 3 0 3
4 4 2 0 4 2
5 5 4 3 2 1
Offensichtlich ist die Operation nicht abgeschlossen, da beispielsweise
2·3≡0 (mod 6) .
Folglich kann Z6 \ {0} bezüglich der Multiplikation keine Gruppe definieren.

Aus dem Beispiel mit Z6 ist ersichtlich, dass im Allgemeinen die Multiplikation in Zn \ {0}
nicht abgeschlossen ist. Wie im nächsten Satz präzisiert passiert dies immer dann, wenn
n eine zusammengesetzte Zahl der Form n = n1 · n2 mit n1 , n2 ≥ 2 ist. In diesem Fall gilt
n1 · n2 ≡ 0 (mod n). Tatsächlich liegt jedoch eine Gruppenstruktur vor, wenn wir uns auf
die Elemente in Zn beschränken, die relativ prim zu n sind.

Für n ≥ 2 verwendet man die Bezeichnung

Z∗n := {x ∈ Zn \ {0} : ggT(x, n) = 1} .
Z∗n heißt die prime Restklassengruppe modulo n. Aus Abschnitt 4 wissen wir, dass |Z∗n | =
ϕ(n), wobei ϕ(n) die Eulersche ϕ-Funktion bezeichnet.
Satz 7.2. Für n ≥ 2 definiert Z∗n bezüglich der Multiplikation modulo n eine Gruppe.

Beweis. Die Abgeschlossenheit der multiplikativen Operation ergibt sich dadurch, dass
für x, y ∈ Zn \ {0} mit ggT(x, n) = 1 und ggT(y, n) = 1 auch ggT(xy, n) = 1 folgt. Wir
wissen bereits, dass die Multiplikation modulo n assoziativ ist, und offensichtlich ist 1 das
neutrale Element.

Es verbleibt, die Existenz der inversen Elemente zu zeigen. Betrachte hierzu ein x ∈
Zn \ {0} mit ggT(x, n) = 1. Nach dem Satz von Bézout existieren s, t ∈ Z, so dass
die ganzzahlige Gleichung sx + tn = 1 erfüllt ist. Modulo n betrachtet bedeutet diese
Gleichung
sx ≡ 1 (mod n) ,
so dass s das inverse Element zu x modulo n ist.

Insgesamt folgt, dass Z∗n bezüglich der Multiplikation modulo n eine Gruppe definiert. 

Wir betrachten nun allgemeine Eigenschaften (endlicher) Gruppen.

 7. ENDLICHE GRUPPEN 123

Satz 7.3. Sei (G, ◦) eine Gruppe und a ∈ G ein fest gewähltes Element. Dann sind die
beiden Abbildungen
La : G → G , x 7→ a ◦ x (Linkstranslation)
und Ra : G → G , x →7 x◦a (Rechtstranslation)
bijektiv.

Beweis. Sei a ∈ G fest gewählt. Aus Symmetriegründen genügt es, die Linkstranslation
La zu betrachten.

Zeige: La ist surjektiv.

Sei y ∈ G. Dann ist a−1 ◦ y ein Urbild von y unter La , denn

La (a−1 ◦ y) = a ◦ a−1 ◦ y = y .

Zeige: La ist injektiv. Seien x, y ∈ G mit a ◦ x = a ◦ y. Dann folgt durch Multiplikation

mit a−1 von links x = y. 

Als Vorbereitung für den nächsten Beweis bemerken wir, dass in jeder Gruppe (G, ◦) die
Kürzungsregeln gelten:
a ◦ b = c ◦ b ⇒ a = c,
b ◦ a = b ◦ c ⇒ a = c.
Denn die erste Regel ergibt sich unmittelbar durch Multiplikation beider Seiten der Glei-
chung a◦b = c◦b mit b−1 von rechts und die zweite Regel entsprechend durch Multiplikation
der Gleichung b ◦ a = b ◦ c mit b−1 von links.

Von fundamentaler Bedeutung ist der Satz von Euler. Für eine Gruppe G bezeichnet |G|
die Anzahl der Elemente in G. Wir schreiben wie üblich an := a
| ◦ .{z
. . ◦ a}.
n−mal

Satz 7.4. Sei G eine endliche abelsche Gruppe. Für alle a ∈ G gilt a|G| = e.

Für den Fall der primen Restklassengruppen (Z∗m , ·) bedeutet das:

Korollar 7.5. (Satz von Euler.) Für alle a ∈ Z∗m gilt aϕ(m) = 1.

Beweis von Satz 7.4. Sei n := |G| und G = {a1 , . . . , an }. Ferner sei a ∈ G beliebig.
Aus der Bijektivität der Linkstranslation L : G → G, x 7→ a ◦ x folgt, dass dann auch {a ◦
a1 , . . . , a ◦ an } = G. Multiplikation jeweils aller Elemente dieser beiden Vertretersysteme
liefert
a1 ◦ · · · ◦ an = a ◦ a1 ◦ · · · ◦ a ◦ an
124 2. DISKRETE MATHEMATIK

und nach Kürzen an = e. 

Korollar 7.6. (Kleiner Satz von Fermat.) Sei p eine Primzahl. Dann gilt für jedes a ∈ Z
ap ≡ a (mod p) .

Beweis. Für a ≡ 0 (mod p) ist die Aussage offensichtlich, und für a 6= 0 gilt wegen
|Z∗p | = ϕ(p) = p − 1 die Kongruenz ap−1 ≡ 1 (mod p). 
 8. DIE ORDNUNG VON GRUPPENELEMENTEN 125

8. Die Ordnung von Gruppenelementen

Ein zentrales Konzept in einer endlichen Gruppe ist das der Ordnung eines Elements.
Es gibt eine quantitative Antwort auf die Frage, wie oft ein Element mit sich selbst zu
verknüpfen ist, bis man zum neutralen Element gelangt.

Definition 8.1. Sei G eine endliche Gruppe und a ∈ G. Das kleinste k ∈ N mit ak = e
heißt Ordnung von a.

Wir beobachten zunächst, dass jedes Element einer endlichen Gruppe G überhaupt eine
endliche Ordnung besitzt. (Im Falle unendlicher Gruppen ist dies i.A. nicht gegeben; für
den Fall endlicher abelscher Gruppen ist dies bereits aus dem Satz 7.4 von Euler klar.)
Sei hierzu a ∈ G. Dann existiert wegen der Endlichkeit von G ein minimales m ∈ N, so
dass in der Folge
e, a, a2 , a3 , . . . , am
nicht alle Elemente verschieden sind. Sei etwa aj = am mit 0 ≤ j < m. Durch Multiplika-
tion mit a−j folgt
(4) e = am−j .
Wegen m − j ∈ N ist die Gruppenordnung also insbesondere endlich und durch m − j
nach oben beschränkt. Aufgrund der Eigenschaft (4) sowie der Minimalität von m folgt
tatsächlich sogar j = 0, so dass also gilt ord(a) = m.

Beispiel. Wir betrachten die Gruppe Z8 bezüglich der Addition.

a 0 1 2 3 4 5 6 7
ord(a) 1 8 4 8 2 8 4 8

Wir stellen einige Eigenschaften der Gruppenordnung zusammen.

Lemma 8.2. Sei G eine endliche Gruppe und a ∈ G. Dann gilt für k ∈ N:
ak = e ⇐⇒ ord(a) | k .

Beweis. „⇐=“: klar.

„=⇒“: Nach Definition ist ord(a) die kleinste natürliche Zahl l mit al = e. Folglich gilt
k ≥ ord(a). Aufgrund der Division mit Rest existieren daher m ∈ N und 0 ≤ t < ord(a)
mit
k = m · ord(a) + t .
126 2. DISKRETE MATHEMATIK

Wegen
e = ak = am·ord(a) ◦ at = e ◦ at = at
folgt aus der Minimalität von ord(a), dass t = 0. 

Im Fall endlicher abelscher Gruppen gibt es die nachstehenden Strukturaussagen.

Lemma 8.3. Sei G eine endliche abelsche Gruppe. Für a, b ∈ G mit teilerfremden Ord-
nungen gilt
ord(a ◦ b) = ord(a) · ord(b) .

Beweis. Sei n := ord(a) und m := ord(b), r := ord(a ◦ b).

Zeige: r | mn.

Aufgrund der Kommutativität gilt

(a ◦ b)mn = (an )m ◦ (bm )n = e ◦ e = e,
so dass sich mit Lemma 8.2 die Behauptung ergibt.

Zeige: mn | r.

Aus e = (ab)r = ar br folgt ar = b−r und

arm = b−rm = (bm )−r = e,
so dass Lemma 8.2 dann n | rm impliziert. Die Teilerfremdheit von n und m liefert n | r.
In gleicher Weise ergibt sich m | r. Es folgt mn | r.

Aus den beiden Teilbarkeitsrelationen ergibt sich die Behauptung. 

Lemma 8.4. Sei G eine endliche abelsche Gruppe, und sei

m = max{ord(a) : a ∈ G} .
Dann gilt am = e für alle a ∈ G.

Nach Satz 7.4 und Lemma 8.2 gilt ord(a) | |G| für alle a ∈ G. Daher kann Lemma 8.4 als
eine Verschärfung von Satz 7.4 betrachtet werden.

Beweis. Sei a ∈ G und n := ord(a). Sei b ∈ G so, dass ord(b) = m.

Es genügt zu zeigen: n | m.
 8. DIE ORDNUNG VON GRUPPENELEMENTEN 127

Annahme: Es existiert eine Primzahlpotenz pi mit i ≥ 0 und pi | m, pi+1 6 | m, aber

pi+1 | n.
i+1 i
Sei a0 := an/p , b0 := b(p ) . Dann gilt ord(a0 ) = pi+1 und ord(b0 ) = m/pi . Wegen der
Teilerfremdheit von ord(a0 ) und ord(b0 ) folgt nach dem voranstehenden Lemma ord(a0 ◦
b0 ) = ord(a0 )ord(b0 ). Also gilt ord(a0 ◦ b0 ) = pm, im Widerspruch zur Maximalität von m.

128 2. DISKRETE MATHEMATIK

9. Der Chinesische Restsatz

Mit Hilfe des nachfolgend diskutierten Chinesischen Restsatzes ist es möglich, Berech-
nungsprobleme in kleinere Probleme aufzuteilen. Hierzu wird eine ganze Zahl a durch
ein Zahlentupel (a1 , . . . , ak ) ersetzt, das man dadurch erhält, dass man a modulo k vor-
gegebener, paarweise teilerfremder Moduln m1 , . . . , mk betrachtet. Da sich das Rechnen
mit a auf kanonischer Weise auf die ai überträgt, kann daher mit den Resten modulo mi
gearbeitet werden.

Diese Strategie setzt voraus, dass man am Ende einer Rechnung eine Zahl wieder aus den
Resten zurückgewinnen kann. Eine Antwort auf diese Frage der Rekonstruierbarkeit wird
durch den Chinesischen Restsatz gegeben, der in einem speziellen Fall bereits Sun Tsu
etwa 300 n. Chr. bekannt war.

Satz 9.1. Seien m1 , . . . , mk ∈ N paarweise teilerfremd und a1 , . . . , ak ∈ Z. Dann existiert

eine Lösung a des Systems von Kongruenzen

x ≡ a1 (mod m1 ), x ≡ a2 (mod m2 ), ..., x ≡ ak (mod mk ) ,

und sie ist modulo m := m1 · . . . · mk eindeutig.

Beweis. Eindeutigkeit: Sind x und x0 Lösungen, d.h. x ≡ x0 ≡ ai (mod mi ), so gilt

mi | (x − x0 ) für alle i. Aus der Eindeutigkeit der Primfaktorzerlegung und der paarweisen
Teilerfremdheit der mi folgt m | (x − x0 ), d.h. x ≡ x0 (mod m).

Existenz: Der nachfolgende Existenzbeweis liefert gleichzeitig ein algorithmisches Verfah-

ren zur Bestimmung von x. Seien ei , 1 ≤ i ≤ k, Lösungen des Gleichungssystems für den
speziellen Fall ai = 1, aj = 0 für j 6= i („Basislösungen“). Setze
Y m
m0i := mj = .
j6=i
mi

Da die Moduln m1 , . . . , mk paarweise teilerfremd sind, gilt ggT(mi , m0i ) = 1. Nach dem
Satz von Bézout existieren daher ganze Zahlen si , ti , so dass 1 = mi si + m0i ti , und die-
se Zahlen können mit dem erweiterten euklidischen Algorithmus berechnet werden. Wir
setzen nun
ei := m0i ti = 1 − mi si .
Dann gilt nach Definition von m0i wie gewünscht
(
1 (mod mi ) ,
ei ≡
0 (mod mj ) für j 6= i .
 9. DER CHINESISCHE RESTSATZ 129

Aus den Basislösungen können wir nun eine Lösung

k
X
x = ai e i
i=1
für das Ausgangssystem zusammensetzen. 

Als Abbildung ausgedrückt bedeutet das:

Korollar 9.2. Seien m1 , . . . , mk ∈ N paarweise teilerfremd und m := m1 · . . . · mk . Dann
ist die Abbildung
Zm → Zm1 × · · · × Zmk , a mod m 7→ (a mod m1 , . . . , a mod mk )
bijektiv.

Beweis. Die Injektivität folgt aus der Eindeutigkeitssaussage. Die Surjektivität folgt al-
ternativ aus der im Beweis angegebenen Berechnungsmethode oder aus der Tatsache, dass
Zm und Zm1 × · · · × Zmk gleichmächtig sind (und damit die Injektivität unmittelbar die
Surjektivität impliziert). 

Beispiel. Gesucht ist eine Lösung des Systems

x≡2 (mod 3), x≡3 (mod 5), x≡4 (mod 7) .
Es gilt m01 = 5 · 7 = 35, m02 = 3 · 7 = 21, m03 = 3 · 5 = 15. Aus
1 = (3, 35) = 12 · 3 − 1 · 35 ,
1 = (5, 21) = −4 · 5 + 1 · 21 ,
1 = (7, 15) = −2 · 7 + 1 · 15
erhalten wir die Basislösungen e1 = −35, e2 = 21, e3 = 15. Folglich ist
2 · (−35) + 3 · 21 + 4 · 15 = 53
Lösung der Kongruenz.
130 2. DISKRETE MATHEMATIK

10. Das RSA-Kryptographieschema

Wir betrachten die Situation, dass eine Person A eine geheime Nachricht an eine Person
B übermitteln möchte. Hierbei Wir nehmen wir an, dass Nachrichten als binäre Folgen
der Länge n vorliegen, d.h. N = {0, 1}n . A codiert die Nachricht zur Geheimhaltung mit
einer injektiven Codierabbildung
E : N → K,
wobei wir auch K = {0, 1}n annehmen können. Anstelle der Nachricht a ∈ N sendet A
die chiffrierte Nachricht E(a). Der Empfänger decodiert mittels der inversen Abbildung
D = E −1 : K0 → N ,
wobei K0 := E(N ) ⊆ K. Ein bekanntes Verfahren beruht auf der Addition modulo 2. Wir
fassen die Nachrichten als Vektoren der Länge n über dem Körper Z2 auf. Zum Codieren
wird ein binärer String k = k1 k2 · · · kn verwendet. Wir setzen
E(a) := a + k ,
die beiden binären Folgen a und k werden also komponentenweise modulo 2 addiert. Es
gilt D = E, denn E + E bildet auf die nur aus Nullen bestehenden Folge ab. Nachrichten
werden daher nach dem gleichen Verfahren decodiert. Dieses klassische Verfahren hat den
Namen ‘One-time-pad’.

Es gilt a + E(a) = k. Gelingt es daher, eine codierte Nachricht E(a) zu entschlüsseln,

so kennt man k und damit bereits die vollständige Codier- und Decodiervorschrift. Ist
k zufällig aus {0, 1}n gewählt, so gilt dies auch für E(a). Dies bedeutet, dass das Ver-
fahren im folgenden Sinne sicher ist: Ein Unbefugter hat keine Chance, eine Nachricht
zu dechiffrieren, wenn er auf k keinen Zugriff hat. Denn die gesendeten Nachrichten sind
gleichverteilt auf {0, 1}n .

Das RSA-Schema. Für die klassischen Chiffrierverfahren besteht ein Sicherheitsproblem

darin, dass man die Codiervorschrift- und Decodiervorschrift geheimhalten muss (beim
One-time-pad also k) und zuvor vereinbaren muss. Diffie und Hellman haben 1976 den
(damals völlig neuartigen) Vorschlag der sogenannten Public-key-Kryptographie gemacht.
Jeder Teilnehmer des Systems besitzt einen öffentlichen Schüssel k und einen geheimen
Schlüssel k 0 . D und E müssen die Eigenschaft haben, dass E leicht berechnet werden
kann, D ohne Kenntnis von k 0 sehr “schwer” berechenbar ist, mit Kenntnis von k 0 jedoch
leicht (Trapdoor-Funktion).

Das bekannteste öffentliche Chiffriersystem ist das 1978 von Rivest, Shamir und Adleman
vorgeschlagene RSA-Schema. Es beruht darauf, dass es schwer ist, eine Zahl m in ihre
Primfaktoren zu zerlegen.
 10. DAS RSA-KRYPTOGRAPHIESCHEMA 131

Erzeugen eines Schlüsselspaares: Seien p, q sehr große Primzahlen (z.B. 2048

Bits), N := pq. Sei e ∈ Z∗ϕ(N ) , d.h. ggT(e, ϕ(N )) = 1, d = e−1 (mod ϕ(N )).
Öffentlicher Schlüssel: (N, e).
Geheimer Schlüssel: d.
Codieren: Aufteilen von Nachrichten in Blöcke der Bitlänge ≤ log2 N und Be-
trachtung jedes Blockes als Zahl in ZN . E : ZN → ZN , E(x) = xe (mod N ).
Decodieren: D : ZN → ZN , D(y) = y d (mod N ).

Beispiel. Sei p = 41, q = 19. Dann ist N = 41 · 19 = 779 und ϕ(N ) = 40 · 18 = 720.
Wird als Codierexponent e etwa e = 103 gewählt, dann ist d = 7 (da d · e = 721 ≡ 1
(mod ϕ(N ))).

Wir verschlüsseln nun einen durch die Zahl 5 gegebenen Nachrichtenblock lautet. Das
Exponentieren erfolgt zweckmäßigerweise durch das Herausziehen von Zweierpotenzen
und sukzessives Quadrieren,
5103 = 564 · 532 · 54 · 52 · 51 .
Wegen 54 = 625, 58 = 6252 ≡ 346 (mod 779), 516 = (58 )2 ≡ 3462 ≡ 529 (mod 779),
532 = (516 )2 ≡ 5292 ≡ 180 (mod 779), 564 = (532 )2 ≡ 1802 ≡ 461 (mod 779) ergibt sich
5103 ≡ 461 · 180 · 625 · 25 · 5
≡ 207 (mod 779) .

Entschlüsselt man die Zahl 207 wieder, ergibt sich

2077 ≡ (2074 ) · (2072 ) · 207
≡ 16 · 4 · 207
≡ 5 (mod 779) .

Das nachstehende Lemma formalisiert, dass die Decodierfunktion die Inverse der Codier-
funktion ist:
Lemma 10.1. (xe )d ≡ (xd )e ≡ x (mod N ).

Beweis. Nach Konstruktion von e und d gilt

e · d = 1 + νϕ(N ) mit ν ∈ Z .
Falls x ∈ Z∗N , dann gilt nach dem Satz von Euler
xed = x1+νϕ(N ) ≡ x (mod N ) .
132 2. DISKRETE MATHEMATIK

Es verbleibt, die Ausage für x 6∈ Z∗N zu zeigen. Nach dem Chinesischen Restsatz ist die
Abbildung
ZN → Zp × Zq
x 7→ (x mod p, x mod q)
bijektiv. Es genügt daher zu zeigen, dass

xed ≡ x (mod p) und xed ≡ x (mod q) .

Im Fall x = 0 ist das klar, so dass nur noch die Fälle x ≡ 0 (mod p) bzw. x ≡ 0 (mod q)
zu behandeln sind. Gilt o.B.d.A. x ≡ 0 (mod p) und x 6≡ 0 (mod q), dann folgt xed ≡ 0
(mod p) sowie aus dem kleinen Satz von Fermat xed ≡ x (mod q), mit dem Chinesischen
Restsatz also xed ≡ x (mod N ). 

Analyse: Die Kenntnis von ϕ(N ) = (p − 1)(q − 1) ist praktisch äquivalent zur Kenntnis
der Faktorisierung von N , denn wegen (o.B.d.A. p > q)

ϕ(N ) = (p − 1)(q − 1) =⇒ p + q = N − ϕ(N ) + 1

p p
p−q = (p + q)2 − 4pq = (N − ϕ(N ) + 1)2 − 4N

ist die Bestimmung von ϕ(N ) etwa genau so schwierig wie die Primfaktorzerlegung von N
– und Faktorisierungsalgorithmen brauchen sehr viel Zeit. Ist also nur N , nicht aber die
Faktorisierung bekannt, so kann man d (= e−1 (mod ϕ(N )) praktisch nicht bestimmen.
Ein offenes Problem ist, ob die Decodierung auch ohne Kenntnis von d möglich ist.

Das asymmetrische RSA-Verfahren ist oft im Zusammenspiel mit symmetrischen Co-

dierverfahren im Einsatz. Da symmetrische Codierverfahren in der Regel schneller sind,
wird das asymmetrische RSA-Verfahren dazu verwendet, um eine sicher Übertragung der
Schlüssel für ein symmetrisches Codierverfahren zu gewährleisten und dann wird das sym-
metrische Codierverfahren verwendet.

Signaturschema: Das RSA-System kann auch zur Beglaubigung von Nachrichten ver-
wendet werden (Digitale Unterschrift). Jeder Teilnehmer A und B besitzt einen öffentli-
chen Schüssel (NA , eA ) bzw. (NB , eB ) sowie einen geheimen dA bzw. dB .

Nachricht von A an B: x 7→ EB (x) = xeB

Entschlüsselung durch B: DB (EB (x)) = (xeB )dB = x (mod NB )
−1
Unterschrift von A: durch Mitteilung von c := DA (x) = xdA (mod NA )
Verifikation der Unterschrift durch B: durch Überprüfung, dass
x = ceA (mod NA ).
 10. DAS RSA-KRYPTOGRAPHIESCHEMA 133

Beispiel. In obigem Beispiel mit N = 779, e = 103, d = 7 soll die Nachricht 3 signiert
werden. Der Teilnehmer berechnet
37 ≡ 629 (mod 779) .
Zur Verifikation der berechneten Unterschrift 629 überprüft man, dass 629103 modulo 779
wieder mit der Nachricht übereinstimmt:
629103 ≡ 3 (mod 779) .

Um ein Gefühl für die Schwierigkeit des Faktorisierens großer Zahlen zu vermitteln, dienen
die folgenden historischen Anhaltspunkte. Im Jahr 1977 wurde in der Zeitschrift Scientific
American eine 129-stellige Dezimalzahl (Bitlänge 429) als Herausforderung für das RSA-
System veröffentlicht (und ein Preisgeld von $100 ausgeschrieben). Diese Zahl wurde erst
1994 faktorisiert (unter Beteiligung von 600 Freiwilligen und einem Rechenaufwand von
ca. 5000 MIPS-Jahren). Es folgten größere Herausforderungen und höhere Preisgelder. Im
Jahr 2003 wurde mit 5-monatiger Rechenleistung auf 120 Maschinen die Zahl RSA-576
der Bitlänge 576 faktorisiert (Preisgeld $10.000), und im Jahr 2005 wurden die Zahlen
RSA-640 der Bitlänge 640 faktorisiert (Preisgeld $20.000). Der Wettbewerb wurde 2007
offiziell beendet, aber die von der Firma RSA gelisteten Zahlen (bis zur Länge von 617
Dezimalstellen (also 2048 Bits)) wurden und werden weiterhin von Wissenschaftlern als
Herausforderung für Faktorisierungstechniken genutzt.

Die aktuell größte dieser RSA-Zahlen, deren Faktorisierung bekannt ist, hat 829 Bits (250
Dezimalstellen, „RSA-250“), und im Jahr 2020 wurden dafür etwas 2700 CPU-Jahre an
Rechenzeit benötigt.

Vom Bundesamt für Sicherheit in der Informationstechnik werden für die Größe des Mo-
duls aktuell (Stand Anfang 2024) mindestens 3000 Bits empfohlen.

Für das Faktorisierungsproblem, auf dem die Sicherheit des RSA-Schemas beruht, ist in
konventionellen Rechnermodellen kein Polynomialzeit-Algorithmus bekannt. Nach einem
theoretischen Resultant von Peter Shor (1994) lassen sich auf Quantencomputern Zahlen
in Polynomialzeit faktorisieren. Es ist jedoch ein offenes Problem im Bereich des Quantum
Computing, ob es in absehbarer Zeit technisch möglich sein wird, Quantencomputer mit
genügend vielen „Qubits“ zu bauen, um Zahlen von praktischer Relevanz darauf faktori-
sieren zu können.
134 2. DISKRETE MATHEMATIK

11. Primalitätstests

Für das RSA-Schema benötigt man große zufällige Primzahlen. Da die Primzahlen ≤ N
etwa die Dichte ln1N haben, genügt ein effektiver Primalitätstest. Naive Verfahren (etwa
√
„Dividiere einen Kandidaten N durch alle Primzahlen p ≤ N “) sind für die relevanten
Größenordnungen nicht praktikabel.

Wie nachstehend beschriebend ist die Entscheidung der Primalität einer Zahl einfacher als
das Faktorisierungsproblem. Viele Primalitätstests beruhen auf Ideen des kleinen Satzes
von Fermat. Nach diesem gilt: Sei N ∈ N. Falls ein a ∈ N, 0 < a < N mit aN −1 6≡
1 (mod N ) existiert, dann ist N keine Primzahl.

Definition 11.1. Sei N eine zusammengesetzte Zahl. N heißt pseudoprim zur Basis a,
falls N die Eigenschaft aN −1 ≡ 1 (mod N ) erfüllt. N heißt Carmichael-Zahl, falls N
pseudoprim für alle a ∈ Z∗N ist.

Ob eine Zahl N Carmichael-Zahl ist, kann man probabilistisch einfach testen. Die a ∈ Z∗N ,
welche die Fermat-Identität erfüllen, bilden eine Untergruppe von Z∗N , also eine Gruppe,
die in Z∗N enthalten ist. Die Kardinalität dieser Untergruppe ist entweder ϕ(N ) oder
höchstens ϕ(N )/2. Dies kann man wie folgt sehen: Seien a1 , . . . , ak ∈ N alle Elemente aus
−1
Z∗N mit aN i ≡ 1 (mod N ). Gibt es ein a ∈ Z∗N mit aN −1 6≡ 1 (mod N ), dann gilt für
bi := a · ai (Linkstranslation):

biN −1 = aN −1 aN
i
−1
6≡ 1 (mod N ) ,

es gibt daher mindestens ebenso viele Elemente in Z∗N , die die Fermatsche Identität nicht
erfüllen. D.h. k ≤ ϕ(N )/2.

Korollar 11.2. (r-facher Fermat-Test.) Gibt es zu N ∈ N ein a ∈ Z∗N mit aN −1 6≡

1 (mod N ), dann gilt für zufällige, unabhängige a1 , . . . , ar ∈ Z∗N
−1
Ws aN ≡ 1 (mod N ) für 1 ≤ i ≤ r ≤ 2−r .


i

Der r-fache Fermat-Test kann die Zusammengesetztheit einer Nicht-Carmichael-Zahl mit

Wahrscheinlichkeit ≥ 1 − 2r erkennen und nachweisen. Die Zusammengesetztheit von
Carmichael-Zahlen kann er nicht erkennen. Für viele praktische Anwendungen ist der
Fermat-Test jedoch bereits ausreichend, da Carmichael-Zahlen nur selten vorkommen. Die
kleinste Carmichael-Zahl ist 561 = 3 · 11 · 17. Bis Anfang der 90er Jahre war unbekannt,
ob es überhaupt unendlich viele Carmichael-Zahlen gibt.

Satz 11.3. (Alford, Granville, Pomerance; Annals of Mathematics, 1994). Es existieren

unendlich viele Carmichael-Zahlen.
 11. PRIMALITÄTSTESTS 135

Die Anzahl C(x) der Carmichael-Zahlen kleiner oder gleich x ist für hinreichend große x
beschränkt durch x2/7 < C(x) < x1−(ln ln ln x)/(ln ln x) .

Bei Kenntnis der Primfaktorisierung einer gegebenen Zahl n lässt sich mit dem folgenden
(ohne Beweis angegebenen) Kriterium effizient überprüfen, ob n eine Carmichael-Zahl ist.

Satz 11.4. (Korselt-Kriterium.) Eine zusammengesetzte Zahl n ∈ N ist genau dann eine
Carmichael-Zahl ist, wenn gilt:

(1) n ist quadratfrei (d.h., n hat die Form n = p1 · · · pk mit paarweise verschiedenen
Primzahlen p1 , . . . , pk ).
(2) (p − 1) | (n − 1) für jeden Primteiler p von n.

Beispiel. Die Zahl 561 = 3 · 11 · 17 ist eine Carmichael-Zahl. Das kann man entweder
mit der Definition der Carmichael-Zahlen und der Nutzung des Chinesischen Restsatzes
zeigen oder wie folgt mit dem Korselt-Kriterium: Die Zahl n ist quadratfrei und es gilt
(3 − 1) = 2 teilt 560 ,
(11 − 1) = 10 teilt 560 ,
(17 − 1) = 16 teilt 560 .

Beweis. Wir begnügen uns hier damit zu zeigen, dass im Falle der Erfülltheit der Bedin-
gungen eine Carmichael-Zahl vorliegt.

Seien hierzu für eine gegebene zusammengesetzte Zahl n die beiden Eigenschaften erfüllt.
Ist a ∈ Z mit ggT(a, n) = 1, dann gilt für jeden Primteiler p von n, dass ggT(a, p) = 1 und
damit nach dem Satz von Euler (oder dem kleinen Satz von Fermat) ap−1 ≡ 1 (mod p).
Da p − 1 nach Voraussetzung ein Faktor von n − 1 ist, folgt an−1 ≡ 1 (mod p).

Es gilt also p | an−1 − 1 für alle Primteiler p von n, so dass wegen der Quadratfreiheit von
n folgt n | an−1 − 1 und damit
an−1 ≡ 1 (mod n).
Wegen der Zusammengesetztheit von n ist n also eine Carmichael-Zahl. 

Der nachstehend beschriebene Primzahltest von Miller-Rabin erweitert den Fermat-Test

auf Carmichael-Zahlen. Sei N ungerade und betrachte aN −1 für ein zufälliges a ∈ ZN \{0}.
Falls sich nicht 1 ergibt, ist die Zusammengesetztheit von N gezeigt. Anderenfalls ersetzen
wir sukzessive diese (gerade) Potenz von a durch ihre (vorabberechnete) Quadratwurzel,
bis das Resultat etwas anderes als ±1 ergibt oder bis wir bei einer ungeraden Potenz von
a angelangt sind. Falls wir eine von ±1 verschiedene Quadratwurzel von 1 erreicht haben,
136 2. DISKRETE MATHEMATIK

dann ist N zusammengesetzt (da jede Zahl a ∈ Z∗N genau zwei Quadratwurzeln in Z∗N
hat). Anderenfalls gibt der Algorithmus aus, dass N „wahrscheinlich prim“ ist, und
das ist die einzige Stelle, an der er einen Fehler gemacht haben könnte.

Primalitäststest von Miller-Rabin:

Eingage: Eine ungerade Zahl N .

Ausgabe: zusammengesetzt oder wahrscheinlich prim.

(1) Bestimme r und R, so dass N − 1 = 2r R und R ungerade.

(2) Wähle a uniform zufällig aus ZN \ {0}.
i
(3) Für i = 0 bis r bestimme bi = a2 R .
(4) Falls aN −1 = br 6≡ 1 (mod N ), dann Ausgabe zusammengesetzt.
(5) Falls aR = b0 ≡ 1 (mod N ), dann Ausgabe wahrscheinlich prim.
(6) Sei j = max{i : bi 6≡ 1 (mod N )}.
(7) Falls bj ≡ −1 (mod N ), dann Ausgabe wahrscheinlich prim, anderenfalls
Ausgabe zusammengesetzt.

Für primes, ungerades N gibt der Algorithmus immer „wahrscheinlich prim“ aus.
Darüber hinaus kann gezeigt werden, dass der Algorithmus bei einer zusammengesetzten
Zahl N höchstens mit Wahrscheinlichkeit 1/4 die Ausgabe „wahrscheinlich prim“
erzeugt.

Satz 11.5. Sei N ∈ N zusammengesetzt und ungerade, N − 1 = 2r R mit ungeradem R.

Dann gilt für zufälliges a ∈ Z∗N :
 i
 1
Ws aR ≡ 1 (mod N ) oder ∃i ∈ {0, . . . , r − 1} a2 R ≡ −1 (mod N ) ≤ .
4

Die Zusammengesetztheit einer nicht primen, ungeraden Zahl wird also mit Wahrschein-
lichkeit 43 zertifiziert. Wiederholtes Ausführen des Algorithmus liefert einen praktikablen
probabilistischen Primzahltest.

Beispiel. Sei N = 30121, dann ist N − 1 = 30120 = 23 · 3765. Wird etwa a = 2 gewählt,
dann gilt in Z∗N
3 ·3765
a2 = 1,
22 ·3765
a = 1,
21 ·3765
a = 18537 .
Da 18537 ∈ {−1, 1} in Z∗N , ist die Zusammengesetztheit der Zahl N gezeigt. Tatsächlich
gilt die Faktorisierung 18537 = 7 · 13 · 331.
 11. PRIMALITÄTSTESTS 137

Im Jahr 2004 wurde ein deterministischer Polynomialzeit-Primalitätstest gefunden,

Satz 11.6. (Agrawal, Kayal, Saxena, 2004.) Es existiert ein Polynomialzeit-Algorithmus,
der entscheidet, ob eine gegebene natürliche Zahl eine Primzahl ist.

Da die auftretenden Konstanten in der Analyse sehr groß sind, ist der Algorithmus kein
praktikabler Algorithmus. Die derzeitigen praktikabelsten Primzahltests für „allgemeine“
Zahlen beruhen auf elliptischen Kurven. Darüber hinaus gibt es spezialisierte Tests für
Zahlen besonderer Bauart, z.B. für Fermat-Zahlen. Eine Fermat-Zahl ist eine Zahl der
n
Form 22 + 1 mit n ∈ N0 . F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537 sind prim. Bis
heute ist jedoch keine weitere Fermat-Primzahl bekannt (bisher sind die Faktorisierungen
von F5 = 641 · 6700417 bis F11 bekannt).