Mathematische Strukturen Sommersemester 2016...In vielen F allen (z.B. zum L osen von Gleichungssystemen) ben otigt man beim Rechnen etwas mehr Struktur: man braucht sogenannte Inverse

Organisatorisches Einfuhrung Grundlagen 1 Analysis Grundlagen 2 Algebraische Strukturen Kombinatorik Zusammenfassung

Vorlesung “Mathematische Strukturen”

Sommersemester 2016

Prof. Barbara KonigUbungsleitung: Christine Mika & Dennis Nolte

Barbara Konig Mathematische Strukturen 1


Monoide, Gruppen, Korper

Wir betrachten nun grundlegende “Rechenstrukturen”. Das sindStrukturen, mit denen man rechnen kann wie mit(naturlichen/rationalen/reellen) Zahlen, die aber moglicherweiseandere Elemente enthalten.

Dabei beantworten u.a. wir folgende Fragen:

Welche (gemeinsamen) Eigenschaften haben Addition undMultiplikation?

Wie unterscheiden sich N0 und Z?

Kann man auch mit endlichen Mengen von Objekten rechnen?

Was sind mogliche Anwendungen in der Kryptographie?




Monoid

Gegeben sei eine Menge M und eine zweistellige Abbildung◦ : M ×M → M. Wir benutzen meist die Infix-Schreibweise:◦((m1,m2)) = m1 ◦m2 und bezeichnen ◦ als zweistelligenOperator.

(M, ◦) heißt Monoid, falls folgendes gilt:

◦ ist assoziativ, d.h., es gilt m1 ◦ (m2 ◦m3) = (m1 ◦m2) ◦m3

fur alle m1,m2,m3 ∈ M.

Es gibt ein neutrales Element e ∈ M, fur das gilt:e ◦m = m ◦ e = m fur alle m ∈ M.




(Gegen-)Beispiele fur Monoide

(N0,+), (Z,+), (Q,+), (R,+) sind Monoide(neutrales Element: 0)

(N0, ·), (Z, ·), (Q, ·), (R, ·) sind Monoide(neutrales Element: 1)

(Z,−) ist kein Monoid(fehlende Assoziativitat)




Modulo-Rechnen

Wir definieren Zn = {0, 1, . . . , n − 1} mit folgender Addition +n

und Multiplikation ·n. Seien k , ` ∈ Zn, dann gilt:

k +n ` = (k + `) mod n k ·n ` = (k · `) mod n

(Zn,+n) und (Zn, ·n) sind Monoide(mit neutralen Elementen 0 bzw. 1)

Sie spielen eine große Rolle u.a. in der Kryptographie undKodierungstheorie.




Bemerkungen:

Man kann Addition/Multiplikation und Modulo-Rechnung beliebigtauschen. Es gilt:

Modulo-Gesetze

(a + b) mod n = ((a mod n) + (b mod n)) mod n

(a · b) mod n = ((a mod n) · (b mod n)) mod n

ak mod n = (a mod n)k mod n

Statt (x mod n) = (a mod n) schreibt man oft auch:

x ≡ a (mod n).




Additions-/Multiplikationstabellen fur Z5:

+n 0 1 2 3 4

0 0 1 2 3 41 1 2 3 4 02 2 3 4 0 13 3 4 0 1 24 4 0 1 2 3

·n 0 1 2 3 4

0 0 0 0 0 01 0 1 2 3 42 0 2 4 1 33 0 3 1 4 24 0 4 3 2 1




In vielen Fallen (z.B. zum Losen von Gleichungssystemen) benotigtman beim Rechnen etwas mehr Struktur: man braucht sogenannteInverse.

Gruppe

Ein Monoid (G , ◦) mit neutralem Element e heißt Gruppe, wennzusatzlich zu den Monoid-Eigenschaften noch folgendes gilt:

fur jedes g ∈ G gibt es ein g−1 ∈ G mit g ◦ g−1 = e.

Dabei heißt g−1 das Inverse von g .

(G , ◦) heißt kommutative Gruppe (oder abelsche Gruppe), fallsaußerdem g1 ◦ g2 = g2 ◦ g1 fur alle g1, g2 ∈ G gilt.

Bemerkung: In jeder Gruppe gilt nicht nur g ◦ g−1 = e, sondernauch g−1 ◦ g = e fur alle g ∈ G .




(Gegen-)Beispiele fur Gruppen

(Z,+), (Q,+), (R,+) sind Gruppen(Inverses zu x ist −x)

(N0,+) ist keine Gruppe(fehlende Inverse)

(Q\{0}, ·), (R\{0}, ·) sind Gruppen(Inverses zu x ist 1

x )

(Q, ·), (R, ·) sind keine Gruppen(0 hat kein Inverses)

(Z, ·), (Z\{0}, ·) sind keine Gruppen(fehlende Inverse)




(Gegen-)Beispiele fur Gruppen (Fortsetzung)

(Zn,+n) ist eine Gruppe

(Zn, ·n) ist keine Gruppe(0 hat kein Inverses)

(Zn\{0}, ·n) ist genau dann eine Gruppe, wenn n einePrimzahl ist.(Ein Element m ∈ Zn hat genau dann ein Inverses, wenn m, nteilerfremd sind.)




Am Beispiel Z4 (n = 4):

Es gilt n = 4 = 2 · 2, d.h., 4 ist keine Primzahl.

m = 2 hat kein multiplikatives Inverses in Z4, dennggT (2, 4) = 2 6= 1.

Insbesondere hat die Gleichung 2 ·4 x = (2 · x) mod 4 = 1 keineLosung: 2 · x ist fur alle x ∈ Z eine gerade Zahl und (2 · x) mod 4ist daher ebenfalls eine gerade Zahl. D.h., man kann niemals dasErgebnis 1 erhalten.

Die Zahlen 1 und 3 sind allerdings teilerfremd zu n und besitzenmultiplikative Inverse in Z4.




Inversenbildung in (Zn,+n)

Das Inverse zu m ∈ Zn bezuglich der Addition +n ist−nm = (−m) mod n = (n −m) mod n. Es gilt:

m +n (−nm) = (m + (−m)) mod n = 0 mod n = 0




Fur die Bildung von multiplikativen Inversen in Zn benotigen wirfolgenden Satz:

Satz von Euler-Fermat

Fur teilerfremde Zahlen m, n ∈ N0 mit n > 1 gilt:

mϕ(n) mod n = 1

Eulersche ϕ-Funktion




Inversenbildung in (Zn, ·n) (Methode 1)

Mit dem Satz von Euler-Fermat:

m−1 = mϕ(n)−1 mod n

Denn es gilt

m ·n m−1 = (m ·mϕ(n)−1) mod n = mϕ(n) mod n = 1

Bemerkung: Inversenbildung funktioniert nur dann, wenn m, nteilerfremd sind. (Ansonsten hat m kein multiplikatives Inverses.)Diese Bedingung ist immer erfullt, falls m 6= 0 und n eine Primzahlist.




Beispiel: Wir berechnen das multiplikative Inverse von 3 in Z5.

3−1 = 3ϕ(5)−1 mod 5 = 33 mod 5 = 27 mod 5 = 2

Test: 3 ·5 2 = (3 · 2) mod 5 = 6 mod 5 = 1.




Inversenbildung in (Zn, ·n) (Methode 2)

Das Inverse zu m ∈ Zn bezuglich der Multiplikation ·n kann auchfolgendermaßen bestimmt werden:

Diophantische Gleichung m · x + n · y = 1 losen.

Bestimme Inverses m−1 = x mod n.

Denn es gilt:

m ·nm−1 = m ·n (x mod n) = (m ·x) mod n = (1−n ·y) mod n = 1

Diese Methode funktioniert auch dann, wenn der Wert ϕ(n) nichteinfach berechnet werden kann (z.B. wenn n sehr groß ist).




Beispiel: Wir berechnen wieder das multiplikative Inverses von 3 inZ5.

Lose 3 · x + 5 · y = 1:

ggT (3, 5) = ggT (5, 3) = ggT (2, 3) = ggT (3, 2) = ggT (1, 2)

= ggT (2, 1) = ggT (1, 1) = ggT (0, 1) = 1

Ruckwarts einsetzen: 1 = 3− 2 = 3− (5− 3) = 3 · 2 + 5 · (−1)

Wir erhalten die Losungen x = 2, y = −1

Bestimme m−1 = x mod n = 2 mod 5 = 2.




Tabelle der Inversen in (Z5\{0}, ·5):

m 1 2 3 4

m−1 1 3 2 4




Nun betrachten wir noch eine Rechenstruktur, die zwei(miteinander kompatible) Operationen (normalerweise + und ·)vereint.

Korper

Sei (K ,+, ·) ein Tupel, das aus einer Menge K und zweizweistelligen Operationen + und · auf K besteht.

(K ,+, ·) heißt Korper, falls folgendes gilt:

(K ,+) ist eine kommutative Gruppe mit neutralem Element 0.

(K\{0}, ·) ist eine kommutative Gruppe mit neutralemElement 1.

Das Distributivgesetz gilt: das heißt, fur alle a, b, c ∈ K gilt:a · (b + c) = a · b + a · c .




Korperaxiome (Zusammenfassung, Teil 1)

Fur einen Korper (K ,+, ·) muss gelten:

+: K × K → K und · : K × K → K sind zweistelligeOperationen auf K .

+ und · sind assoziativ, d.h., es gilt fur alle x , y , z ∈ K :

(x + y) + z = x + (y + z) und (x · y) · z = x · (y · z)

+ hat ein neutrales Element, welches mit 0 bezeichnet wirdund · hat ein neutrales Element, welches mit 1 bezeichnetwird.




Korperaxiome (Zusammenfassung, Teil 2)

Jedes Element hat ein additives Inverses und jedes Element,außer 0, hat ein multiplikatives Inverses.

+ und · sind kommutativ, d.h., es gilt fur alle x , y ∈ K :

x + y = y + x und x · y = y · x

Es gilt das Distributivgesetz, d.h., fur alle x , y , z ∈ K gilt

x · (y + z) = x · y + x · z und (x + y) · z = x · z + y · z

(Das zweite Distributivgesetz folgt aus dem ersten aufgrundder Kommutativitat von ·.)




(Gegen-)Beispiele fur Korper

(Q,+, ·), (R,+, ·) sind Korper

(Zn,+n, ·n) ist ein Korper, falls n eine Primzahl ist

Weitere Beispiele fur Korper (auf die wir nicht mehr weitereingehen): komplexe Zahlen, endliche Korper (mit 4, 8, 9, . . .Elementen), . . .



Anwendungsbeispiel: RSA

Wir betrachten eine Anwendung im Bereich der asymmetrischenVerschlusselung (public-key cryptography).

Das sogenannte RSA-Verfahren (benannt nach Rivest, Shamir,Adleman) ist die Grundlage von wichtigenKommunikationsprotokollen im Internet. Außerdem bildet es dieBasis von elektronischen Signaturen.

Alice

SenderVersenden

einer

verschlusseltenNachricht M

Bob

Empfanger

Alice will eine Nachricht M an Bob verschicken.

Alice verwendet den offentlichen Schlussel von Bob zumVerschlusseln.

Bob verwendet seinen privaten Schlussel zum Entschlusseln.




1. Schritt: Schlusselerzeugung

Bob generiert zwei große Primzahlen p, q mit p 6= q und setztn = p · q.

Bob bestimmt ϕ(n)(in diesem Fall gilt ϕ(n) = (p − 1) · (q − 1)).

Bob bestimmt d , e mit (d · e) mod ϕ(n) = 1(d.h., d , e sind in Zϕ(n) zueinander multiplikativ invers)

(e, n) ist der offentliche Schlussel, den Bob bekanntgibt.

(d , n) ist der private Schlussel, den Bob geheimhalt.




2. Schritt: Verschlusselung

Alice will eine Nachricht M an Bob verschlusseln. Sie kodiertdiese Nachricht als eine Zahl m ∈ Zn (z.B. durchBinarkodierung).

Alice rechnet c = me mod n und schickt c an Bob.

Hier wird also in Zn gerechnet.

3. Schritt: Entschlusselung

Bob empfangt c.

Er rechnet m = cd mod n und erhalt damit wieder dieursprungliche Nachricht.

Wie bei der Verschlusselung wird hier wieder in Zn gerechnet.




Rechenbeispiel RSA

p = 5, q = 11, n = 5 · 11 = 55

ϕ(n) = (p − 1) · (q − 1) = 4 · 10 = 40

Wahle e = 3 und berechne das Inverse (Methode 2):

Lose 3 · x + 40 · y = 1, ergibt Losungen x = −13, y = 1Setze d = x mod 40 = (−13) mod 40 = 27

Nachricht m = 9 soll ubertragen werden. Alice berechnet dieKodierung c = 93 mod 55 = 729 mod 55 = 14.

Code c = 14 kommt an. Bob rechnet

1427 mod 55 = (143 mod 55)9 mod 55

= (2744 mod 55)9 mod 55 = 499 mod 55

= (493 mod 55)3 mod 55 = (117649 mod 55)3 mod 55

= 43 mod 55 = 64 mod 55 = 9 = m




Warum funktioniert RSA?

Korrektheit: Warum erhalt Bob wieder die ursprungliche Nachricht?

Das kann mit dem Satz von Euler-Fermat nachgewiesen werden.

Es gilt (e · d mod ϕ(n)) = 1 und damit gibt es eine Zahl z mite · d = z · ϕ(n) + 1. Also entsteht beim Verschlusseln undanschließenden Entschlusseln:

(me mod n)d mod n = me·d mod n = mz·ϕ(n)+1 mod n

= (m · (mϕ(n))z) mod n = m · 1z mod n = m mod n = m

Diese Argumentation funktioniert nicht, falls m, n nicht teilerfremdsind. In diesem Fall kann man aber anders nachweisen, dass mandennoch das richtige Ergebnis erhalt.




Warum funktioniert RSA? (Fortsetzung)

Sicherheit: Warum ist es fur andere Teilnehmer (außer Bob)schwierig, die Nachricht zu entschlusseln?

Das liegt daran, dass man d nur dann leicht aus e berechnen kann,wenn man ϕ(n) kennt. Um ϕ(n) zu berechnen, musste man diePrimfaktorzerlegung von großen Zahlen n (ca. 1024–2048 Bits)bestimmen, was sehr schwer ist.



Vektorraume und Matrizen

Wir betrachten nun Vektoren, die Tupel von Elementen einesKorpers sind. Mengen von Vektoren bilden einen sogenanntenVektorraum.

Vektoren sind wichtig fur die Darstellung geometrischer Objekte.Matrizen werden dazu verwendet, um (lineare) Funktionen inVektorraumen zu beschreiben. Sie spielen auch eine wichtige Rollebeim Losen von Gleichungssystemen.




Vektor

Sei n ∈ N0 eine naturliche Zahl und (K ,+, ·) ein Korper. EinVektor ~u der Dimension n uber K besteht aus n Elementenu1, . . . , un ∈ K des Korpers.

Ein Vektor wird im allgemeinen folgendermaßen dargestellt undheißt daher auch Spaltenvektor.

~u =

u1...un




Vektorraum

Die Menge aller Vektoren der Dimension n uber K heißtn-dimensionaler Vektorraum uber K und wird mit Kn bezeichnet.

Hinweis: es gibt noch allgemeinere Definitionen eines Vektorraums(ahnlich zu den Definitionen von Monoid, Gruppe, Korper), die wirhier aber nicht betrachten.

Die Operationen auf einem Vektorraum sind Addition von Vektorenund Skalarmultiplikation, die im Folgenden betrachtet werden.




Klassisches Beispiel: Sei n = 2 und K = R, d.h., wir betrachtenden Vektorraum R2.

Dann handelt es sich bei den Vektoren um Punkte imzweidimensionalen Raum. Diese werden auch durch Pfeile –ausgehend vom Ursprung des Koordinatensystems – dargestellt.

0 1 2−1−2

1

3

2

x

y (1, 52, 5

)(−22

)

Die erste Koordinate bezeichnet man dabei – wie ublich – alsx-Koordinate, die zweite als y -Koordinate.




In Vektorraumen sind verschiedene Operationen definiert:

Addition von Vektoren

Die Addition auf Vektoren ist eine zweistelligen Operation+: Kn × Kn → Kn, die folgendermaßen definiert ist:

u1...un

+

v1...vn

=

u1 + v1

...un + vn

Dabei werden die einzelnen Korperelemente mit Hilfe der+-Operation des Korpers verknupft.




Vektorraum als Gruppe

Ein Vektorraum mit der Addition ist eine kommutative Gruppe.Das neutrale Element ist der Nullvektor ~0 und das additive Inversezu ~u wird mit −~u bezeichnet:

~0 =

0...0

Falls ~u =

u1...un

, dann ist − ~u =

−u1...−un

.

Dabei sind −u1, . . . ,−un die additiven Inversen im Korper.




Multiplikation mit einem Skalar

Ein Vektor ~u ∈ Kn kann mit einem einzelnen Korperelement k ∈ Kmultipliziert werden. Das Element k nennt man dann auch Skalar.

k ·

u1...un

=

k · u1...

k · un

Dabei entstehen k · u1, . . . , k · un durch dieMultiplikationsoperation im Korper.




Eigenschaften der Multiplikation mit einem Skalar

Seien ~u, ~v ∈ Kn Vektoren und k , ` ∈ K Skalare. Dann gilt:

k · (` · ~u) = (k · `) · ~uk · (~u + ~v) = k · ~u + k · ~v(k + `) · ~u = k · ~u + ` · ~u

1 · ~u = ~u

Dabei ist 1 das neutrale Element der Multiplikation im Korper.




Wir betrachten nun bestimmte Abbildungen auf Vektorraumen:sogenannte lineare Abbildungen.

Lineare Abbildung

Seien Kn,Km zwei Vektorraume. Eine Funktion ψ : Kn → Km

heißt lineare Abbildung, falls folgendes gilt:

ψ(~u + ~v) = ψ(~u) + ψ(~v) fur alle ~u, ~v ∈ Kn

ψ(k · ~u) = k · ψ(~u) fur alle ~u ∈ Kn, k ∈ K

Die Multiplikation mit einem Skalar ist eine lineare Abbildung.

Auch viele der interessanten Abbildungen in der Geometrie sindlinear (z.B. Drehungen, Spiegelungen).




Wir betrachten nun Matrizen, mit denen solche linearenAbbildungen beschrieben werden konnen:

Matrix

Seien m, n ∈ N0 und K ein Korper. Eine m×n-Matrix A uber Kbesteht aus m · n Eintragen

Ai ,j ∈ K fur i ∈ {1, . . . ,m}, j ∈ {1, . . . , n}

Sie wird folgendermaßen dargestellt:

A =

A1,1 . . . A1,n

.... . .

...Am,1 . . . Am,n




Bemerkungen:

Eine m×n-Matrix besteht also aus m Zeilen der Lange n, oder –anders ausgedruckt – aus n Spalten der Lange m.

Dabei heißt m Zeilendimension und n Spaltendimension der Matrix.

Bei einem Eintrag Ai ,j bezeichnet der erste Index i die Zeile, derzweite Index j die Spalte.

Eine Matrix, fur die m = n gilt, heißt quadratisch.




Matrizen konnen mit Vektoren mulipliziert werden.

Multiplikation einer Matrix mit einem Vektor

Sei A eine m×n-Matrix und ~u ∈ Kn ein Vektor der Dimension n.Dann ist A · ~u folgender Vektor aus Km:

A·~u =

A1,1 . . . A1,n

.... . .

...Am,1 . . . Am,n

·

u1...un

=

A1,1 · u1 + · · ·+ A1,n · un. . .

Am,1 · u1 + · · ·+ Am,n · un

Das heißt, in der i-ten Zeile des Spaltenvektors steht der Eintrag

n∑

j=1

Ai ,j · uj




Bemerkung:

Wir verwenden das Summenzeichen Σ als abkurzende Schreibweise:

n∑

j=1

aj = a1 + a2 + · · ·+ an

Rechenregeln fur Summen

n∑

j=1

(aj + bj) =n∑

j=1

aj +n∑

j=1

bj

n∑

j=1

(k · aj) = k ·n∑

j=1

aj




Beispiel: Multiplikation von Matrix und Vektor in RMultiplikation einer 2× 3-Matrix mit einem Vektor derDimension 3:

(3 4 −1−2 2 −3

)·

10, 5−2

=

(3 + 2 + 2−2 + 1 + 6

)=

(75

)




Merkregel:

Die Multiplikation einer m×n-Matrix mit einem Vektor derDimension n ergibt einen Vektor der Dimension m.

Multipliziere die Zeilen der Matrix nacheinander mit derSpalte des Vektors (und addiere jeweils dieMultiplikationsergebnisse auf).




Matrix als lineare Abbildung

Eine m × n-Matrix A uber K beschreibt eine lineare AbbildungψA : Kn → Km wie folgt:

ψA(~u) = A · ~u

Durch Nachrechnen stellt man fest, dass tatsachlich dieEigenschaften einer linearen Abbildung erfullt sind. Insbesonderegilt fur eine Matrix A, Vektoren ~u, ~v und einen Skalar k :

A · (~u + ~v) = A · ~u + A · ~v A · (k · ~u) = k · (A · ~u)

Außerdem gibt es zu jeder linearen Abbildung ψ : Kn → Km eineMatrix A mit ψ = ψA.




Beispiel: wir betrachten folgende 2× 2-Matrix als lineareAbbildung:

A =

(−1 22 1

)

Es gilt:

A ·(

0−1

)=

(−1 22 1

)·(

0−1

)=

(−2−1

), d.h.ψA(

(0−1

)) =

(−2−1

)

A ·(

10

)=

(−1 22 1

)·(

10

)=

(−12

), d.h. ψA(

(10

)) =

(−12

)

A ·(

21

)=

(−1 22 1

)·(

21

)=

(05

), d.h. ψA(

(21

)) =

(05

)




Graphische Darstellung:

y

x

−2

−1−1−2−3 1 32 4 5 6

1

2

3

5

4

Rote Punkte/Vektoren werden auf grune Punkte/Vektorenabgebildet. Darstellung der Abbildungsvorschrift durch gestricheltePfeile.




Graphische Darstellung:

−2

1 2 3 4 5 6x

1

2

3

4

5

y

−1−3 −2 −1

Lineare Abbildungen bilden Geraden auf Geraden ab. Linien werdenalso erhalten. Daher stammt der Name!




Zwei Matrizen gleicher Zeilen- und Spaltendimension konnenaddiert werden:

Addition von Matrizen

Seien A,B m × n-Matrizen. Dann hat C = A + B folgendesAussehen:A1,1 . . . A1,n

.... . .

...Am,1 . . . Am,n

+

B1,1 . . . B1,n

.... . .

...Bm,1 . . . Bm,n

=

C1,1 . . . C1,n

.... . .

...Cm,1 . . . Cm,n

mit Ci ,j = Ai ,j + Bi ,j .Die Addition erfolgt komponentenweise.




Matrizen als additive Gruppe

Die Menge aller m × n-Matrizen uber einem Korper K bildet einekommutative Gruppe bezuglich der Addition.Dabei ist die Nullmatrix N das neutrale Element und das additiveInverse zu A ist −A:

N =

0 . . . 0...

. . ....

0 . . . 0

− A =

−A1,1 . . . −A1,n

.... . .

...−Am,1 . . . −Am,n




Matrizen konnen auch miteinander multipliziert werden.

Multiplikation von Matrizen

Sei A eine m × n-Matrix und B eine n × r -Matrix. Dann istC = A · B eine m × r -Matrix und hat folgendes Aussehen:

A1,1 . . . A1,n

.... . .

...Am,1 . . . Am,n

·

B1,1 . . . B1,r

.... . .

...Bn,1 . . . Bn,r

=

C1,1 . . . C1,r

.... . .

...Cm,1 . . . Cm,r

mit

Ci ,j =n∑

`=1

Ai ,` · B`,j




Merkregel:

Multipliziere die Zeilen der ersten Matrix (A) mit den Spaltender zweiten Matrix (B).

Um in der Ergebnismatrix C den Eintrag Ci ,j zu erhalten,multipliziere die i-te Zeile der ersten Matrix (A) mit der j-tenSpalte der zweiten Matrix (B) und addiere jeweils dieMultiplikationsergebnisse auf.




Alternative Beschreibung: teile B in r (Spalten-)Vektoren auf

B =(~b1 . . . ~br

)

Multipliziere diese Spaltenvektoren dann einzeln. Die entstehendenSpaltenvektoren werden dabei von links nach rechtsnebeneinandergeschrieben.

A · B = A ·(~b1 . . . ~br

)=(A · ~b1 . . . A · ~br

)

Multiplikation einer Matrix mit einem Vektor ist daher einSpezialfall der Matrizenmultiplikation.




Beispiel: Matrixmultiplikation in RMultiplikation einer 2× 3-Matrix mit einer 3× 2-Matrix:

(3 4 −1−2 2 −3

)·

1 00, 5 −3−2 −1

=

(3 + 2 + 2 0− 12 + 1−2 + 1 + 6 0− 6 + 3

)=

(7 −115 −3

)




Merkregel Falk-Schema: Folgende “Eselsbrucke” hilft bei derMatrizenmultiplikation A · B = C

Die zweite Matrix B wird nach oben verschoben.

In dem Feld rechts von der ersten Matrix A und unterhalb derzweiten Matrix B entsteht dann die neue Matrix C .

Ein Eintrag von C entsteht dadurch, dass die entsprechendeZeile von A und Spalte von B miteinander multipliziertwerden.

(3 4 −1−2 2 −3

)·

1 00, 5 −3−2 −1

=

(7 −115 −3

)

1 00,5 -3-2 -1

3 4 -1 7 -11-2 2 -3 5 -3




Assoziativitat der Matrizenmultiplikation

Matrixmultiplikation ist assoziativ. D.h., falls A eine m × n-Matrix,B eine n × r -Matrix und C eine r × s-Matrix ist, dann gilt:

A · (B · C ) = (A · B) · C

Es macht keinen Sinn zu fragen, ob die Menge aller Matrizenbeliebiger Dimension ein Monoid oder eine Gruppe bezuglich derMultiplikation ist. Es laßt sich nicht jede Matrix mit jeder Matrixverknupfen, da die Dimensionen ubereinstimmen mussen.

Diese Frage macht nur Sinn fur quadratische Matrizen festerDimension.




Eigenschaften quadratischer Matrizen (I)

Die Menge aller quadratischen n × n-Matrizen bildet einMonoid mit der Multiplikationsoperation.

Insbesondere gibt es ein neutrales Element der Multiplikation,die sogenannte Einheitsmatrix En:

En =

1 . . . 0...

. . ....

0 . . . 1

Diese Matrix hat Einsen in der Diagonale von links oben nachrechts unten und besteht ansonsten nur aus Nullen.




Eigenschaften quadratischer Matrizen (II)

Nicht jede quadratische Matrix A hat ein multiplikativesInverses A−1. Matrizen, die kein multiplikatives Inverseshaben, heißen singular.

Matrizenmultiplikation ist außerdem nicht kommutativ.




Beispiel 1: Multiplikation mit der Einheitsmatrix

E3 ·

−2 3 10, 5 7 −31 1 0

=

1 0 00 1 00 0 1

·

−2 3 10, 5 7 −31 1 0

=

−2 + 0 + 0 3 + 0 + 0 1 + 0 + 00 + 0, 5 + 0 0 + 7 + 0 0 + (−3) + 00 + 0 + 1 0 + 0 + 1 0 + 0 + 0

=

−2 3 10, 5 7 −31 1 0

Fur jede n× n-Matrix A gilt sowohl En ·A = A, als auch A ·En = A.




Beispiel 2: Nicht-Existenz von Inversen

Die Nullmatrix, aber auch viele andere Matrizen haben keinInverses. Wir betrachten folgende Matrix A:

A =

1 0 00 0 00 0 0

Es gibt keine 3× 3-Matrix B, so dass A · B die Einheitsmatrix ist:

A · B =

1 0 00 0 00 0 0

·

B1,1 B1,2 B1,3

B2,1 B2,3 B2,3

B3,1 B3,2 B3,3

=

B1,1 B1,2 B1,3

0 0 00 0 0

6=

1 0 00 1 00 0 1

= E3




Beispiel 3: Nicht-Kommutativitat der Matrizenmultiplikation

1 2 03 1 20 3 1

·

1 −1 00 0 00 2 0

=

1 −1 03 1 00 2 0

6=

−2 1 −20 0 06 2 4

=

1 −1 00 0 00 2 0

·

1 2 03 1 20 3 1




Die Multiplikation von zwei Matrizen entspricht der Verknupfungder dazugehorigen linearen Abbildungen.

Matrixmultiplikation und Verknupfung linearer Abbildungen

Sei A eine m× n-Matrix uber und ψA : Kn → Km die dazugehorigelineare Abbildung mit ψA(~u) = A · ~u. Analog sei B einen × r -Matrix und ψB : K r → Kn die dazugehorige lineareAbbildung.

Dann beschreibt die Matrix C = A · B folgende lineare AbbildungψC : K r → Km mit

ψC (~u) = (A · B) · ~u = A · (B · ~u) = A · ψB(~u) = ψA(ψB(~u))

und damit gilt ψC = ψA·B = ψA ◦ ψB .

Das beruht im wesentlichen auf der Assoziativitat derMatrixmultiplikation.



Erzeugendensysteme und Basen

Wir betrachten nun Konzepte, mit denen man einen Vektorraumaus einigen wenigen Vektoren, sogenannten Basisvektoren erzeugenkann.

Das hat auch Beziehungen zur Berechnung von multiplikativenInversen einer Matrix und zum Losen von Gleichungssystemen.




Erzeugendensystem

Gegeben sei ein n-dimensionaler Vektorraum uber einem Korper K .Eine Menge S = {~v1, . . . , ~vm} von Vektoren heißtErzeugendensystem des Vektorraums, falls sich jeder Vektor~u ∈ Kn als Linearkombination von Vektoren aus S darstellen laßt.D.h., fur jeden Vektor ~u gibt es Skalare k1, . . . , km ∈ K , so dassgilt:

~u = k1 · ~v1 + · · ·+ km · ~vm




Beispiel 1: die Menge

S = {(

20

),

(01

),

(11

)}

ist ein Erzeugendensystem fur den Vektorraum R2. Ein Vektor ~ulaßt sich immer folgendermaßen darstellen:

~u =

(u1u2

)=

u12·(

20

)+ u2 ·

(01

)+ 0 ·

(11

)




Bemerkung: Die Beziehung

~u = k1 · ~v1 + · · ·+ km · ~vm

kann auch dargestellt werden als

~u =(~v1 . . . ~vm

)︸︷︷︸

V

·

k1...km

wobei V =(~v1 . . . ~vm

)eine Matrix ist, die aus den

Spaltenvektoren ~v1, . . . , ~vm zusammengesetzt ist.

D.h., eine Multiplikation einer Matrix mit einem Vektor ergibt eineLinearkombination der Spalten der Matrix.




Die Menge S im vorherigen Beispiel enthalt uberflussige Elemente,mindestens ein Vektor ist redundant. Beispielsweise kann der dritteVektor durch die beiden ersten dargestellt werden.

Linear unabhangige Menge

Gegeben sei ein n-dimensionaler Vektorraum uber einem Korper K .Eine Menge S = {~v1, . . . , ~vm} von Vektoren heißt linearunabhangig, falls sich kein Vektor ~v aus S als Linearkombinationder anderen Vektoren darstellen laßt.





S = {

100

,

010

}

ist linear unabhangig im R3, sie ist jedoch kein Erzeugendensystem.




Alternative Definition fur linear unabhangig:

Eine Menge S = {~v1, . . . , ~vm} von Vektoren ist linear unabhangig,wenn fur beliebige Skalare k1, . . . , km ∈ K aus

k1 · ~v1 + · · ·+ km · ~vm = ~0

immer k1 = · · · = km = 0 folgt.

Das heißt, man kann den Nullvektor nur auf eine Weise alsLinearkombination von linear unabhangigen Vektoren darstellen:indem man alle Skalare mit 0 belegt.

In Kombination mit Losungsverfahren fur Gleichungssysteme ( Gaußsches Eliminationsverfahren, wird im Anschluss behandelt),erhalt man dadurch eine Methode, um zu uberprufen, ob eineMenge von Vektoren linear unabhangig ist.




Basis

Gegeben sei ein n-dimensionaler Vektorraum uber einem Korper K .Eine Menge B = {~b1, . . . , ~bm} von Vektoren heißt Basis, falls siegleichzeitig ein Erzeugendensystem und linear unabhangig ist.




Beispiel 3: die Mengen

B1 = {

100

,

010

,

001

}

und

B2 = {

200

,

030

,

−201

}

sind beides Basen des R3.

Fur B1 ist dies relativ offensichtlich. Aus B2 kann man einfach dieElemente von B1 (die sogenannten Einheitsvektoren) bestimmenund außerdem sind die drei Vektoren linear unabhangig.





B3 = {

100

,

021

,

−221

}

ist keine Basis des R3, denn ihre Vektoren sind nicht linearunabhangig. Insbesondere kann man den dritten Vektor durchLinearkombination der anderen beiden Vektoren darstellen:

−221

= (−2) ·

100

+ 1 ·

021




Einheitsvektoren

Gegeben sei ein n-dimensionaler Vektorraum uber einem Korper Kund sei i ∈ {1, . . . , n}. Der i-te Einheitsvektor ~ei ist der Vektor,der an der i-ten Stelle eine 1 hat und sonst nur aus Nullen besteht.

~e1 =

10...0

. . . ~en =

0...01




Bemerkungen:

Wenn B eine Basis des Kn ist, dann gibt es fur jeden Vektordes Kn genau eine Moglichkeit, diesen als Linearkombinationvon Vektoren aus B darzustellen.

Die Einheitsvektoren bilden immer eine Basis des Kn. Furjeden Vektor ~u gilt:

~u =

u1...un

= u1 · ~e1 + · · ·+ un · ~en

Die Einheitsvektoren sind jedoch nicht die einzige Basis.




Weitere Bemerkungen:

Ein Erzeugendensystem des Kn besteht immer aus mindestensn Vektoren. Eine Menge, die weniger als n Vektoren enthalt,kann also kein Erzeugendensystem sein.

Eine linear unabhangige Menge im Kn besteht immer aushochstens n Vektoren. Eine Menge, die mehr als n Vektorenenthalt, ist also immer linear abhangig.




Weitere Bemerkungen:

Eine Basis des Kn besteht immer aus genau n Vektoren.

Eine linear unabhangige Menge mit n Vektoren ist immer eineBasis des Kn.

Ein Erzeugendensystem mit n Vektoren ist auch immer eineBasis des Kn.




Aus den letzten beiden Bemerkungen ergeben sich zwei einfacheVerfahren, um festzustellen, ob eine Menge B ⊆ Kn von Vektoreneine Basis des Kn ist oder nicht:

Man uberpruft, ob B genau n Vektoren enthalt und ob dieseVektoren ein Erzeugendensystem sind.

Oder: Man uberpruft, ob B genau n Vektoren enthalt und obdiese Vektoren linear unabhangig sind.

Insbesondere kann eine Menge von Vektoren, die mehr oderweniger als n Vektoren enthalt, niemals eine Basis sein.




Wir konnen nun die Frage beantworten, wann eine quadratischeMatrix A invertierbar ist.

Angenommen die Matrix A ist invertierbar, d.h., es gibt einmultiplikatives Inverses A−1 mit A · A−1 = En. Wir betrachten A−1

als aufgebaut aus einzelnen Spaltenvektoren ~a1, . . . , ~an, d.h.A−1 =

(~a1 . . . ~an

). Dann gilt:

A ·A−1 = A ·(~a1 . . . ~an

)=(A · ~a1 . . . A · ~an

)=(~e1 . . . ~en

)

Es gilt also A · ~ai = ~ei fur i ∈ {1, . . . , n}. Das bedeutet, dass manaus den Spalten von A durch Linearkombination jedenEinheitsvektor (und damit auch jeden anderen Vektor) erhaltenkann.




Die Menge der Spaltenvektoren von A ist damit einErzeugendensystem und – da sie aus genau n Vektoren besteht –eine Basis.

Umgekehrt gilt auch, dass es zu einer Matrix, derenSpaltenvektoren eine Basis bilden, Vektoren ~a1, . . . , ~an gibt, die dieobigen Eigenschaften haben und aus denen man eine inverseMatrix konstruieren kann. (Wie man diese Vektoren berechnenkann, besprechen wir spater.)




Zusammenfassend gilt also:

Invertierbare Matrizen und Basen

Eine n × n-Matrix A uber einem Korper K ist invertierbar, genaudann, wenn die Spalten von A eine Basis des Kn bilden.

Man sagt dann auch, die Matrix hat den vollen Rang.



Gaußsches Eliminationsverfahren

Wir betrachten nun ein Verfahren zum Losen vonGleichungssystemen.

Gegeben sei eine m × n-Matrix A und ein m-dimensionaler Vektor~b. Gesucht ist ein n-dimensionaler Vektor ~x , der folgendeGleichung erfullt:

A · ~x = ~b

Wenn A quadratisch (m = n) und zudem noch invertierbar ist,dann kann man zeigen, dass es genau eine Losung ~x gibt: manmultipliziert die obige Gleichung auf beiden Seiten mit A−1:

A−1 · A · ~x = A−1 · ~b und daraus folgt wegenA−1 · A · ~x = En · ~x = ~x , dass ~x = A−1 · ~b.




Trotzdem bleiben noch viele offene Fragen:

Wie berechnet man ~x? (Wir haben ja noch kein Verfahren,um das multiplikative Inverse einer Matrix zu bestimmen.)

Was passiert, wenn A nicht quadratisch oder nicht invertierbarist?

Kann eine Gleichung evtl. mehrere Losungen haben?

Kann eine Gleichung evtl. keine Losung haben?




Wir betrachten eine Gleichung in “ausgeschriebener” Form:

A · ~x = ~b

wird geschrieben alsA1,1 . . . A1,n

.... . .

...Am,1 . . . Am,n

·

x1...xn

=

b1...bm

und das ist gleichbedeutend damit, dass das folgendeGleichungssystem eine Losung hat:

A1,1 · x1 + · · ·+ A1,n · xn = b1...

Am,1 · x1 + · · ·+ Am,n · xn = bm




In den folgenden Beispielen arbeiten wir im Korper R.

Beispiel 1: Gleichungssystem mit einer Losung

3 · x1 + 4 · x2 = 2

x1 − 3 · x2 = 5

Man kann dieses Gleichungssystem durch “geschicktes” Einsetzenlosen: zweite Gleichung wird umgeformt in x1 = 5 + 3 · x2,eingesetzt in die erste Gleichung ergibt

3 · (5 + 3 · x2) + 4 · x2 = 15 + 13 · x2 = 2

und daraus folgt x2 = −1. Daher: x1 = 5 + 3 · x2 = 5 + 3 · (−1) = 2.

Die (einzige) Losung ist damit x1 = 2, x2 = −1.




Fur dieses Beispiel gilt:

A =

(3 41 −3

)~b =

(25

)

und A hat das multiplikative Inverse

A−1 =

(313

413

113 − 3

13

)

(Wir werden noch sehen, wie man solche Inverse tatsachlichberechnen kann.)

Test:

~x = A−1 · ~b =

(313

413

113 − 3

13

)·(

25

)=

(2613

−1313

)=

(2−1

)




Beispiel 2: Gleichungssystem ohne Losung

x1 + 2 · x2 = 3

−2 · x1 − 4 · x2 = 1

Man sieht, dass man −2 · x1 − 4 · x2 erhalt, indem man x1 + 2 · x2mit −2 multipliziert. Also musste auch das Ergebnis rechts unten(= 1) ein entsprechendes Vielfaches des Ergebnisses rechts oben(= 3) sein. Das ist aber nicht der Fall.Daher hat das Gleichungssystem keine Losung.

Hier sieht man, dass die Matrix

A =

(1 2−2 −4

)

aus linear abhangigen Spaltenvektoren besteht und nicht den vollenRang hat. Sie ist also nicht invertierbar.




Beispiel 3: Gleichungssystem mit mehreren Losungen

x1 + 2 · x2 = 3

−2 · x1 − 4 · x2 = −6

Die untere Gleichung ist ein Vielfaches der oberen Gleichung(Faktor −2). Also ist die untere Gleichung redundant und wirmussen alle Losungen der oberen Gleichung bestimmen. Es giltx1 = 3− 2 · x2, also hat die Losung ~x die Form:

~x =

(x1x2

)=

(3− 2 · x2

x2

)=

(30

)+ x2 ·

(−21

)

Dabei kann x2 ∈ R beliebig gewahlt werden und wir habenunendlich viele Losungen.

Wie in Beispiel 2 ist die Matrix nicht invertierbar.




Wir betrachten nun ein allgemeines Verfahren, um solcheGleichungssystem zu losen: das Gaußsche Eliminationsverfahren.Der Einfachheit halber stellen wir ein Gleichungssystemfolgendermaßen dar:

A1,1 · x1 + · · ·+ A1,n · xn = b1...

Am,1 · x1 + · · ·+ Am,n · xn = bm

entsprichtA1,1 . . . A1,n b1...

. . ....

...Am,1 . . . Am,n bm




Das Gaußsche Eliminationsverfahren basiert auf folgendenBeobachtungen:

Wenn man zwei Zeilen vertauscht, so andern sich dadurch dieLosungen nicht.

Wenn man eine Zeile mit einem Wert ungleich 0 multipliziert,so andern sich dadurch die Losungen nicht.

Wenn man das Vielfache einer Zeile zu einer anderen Zeileaddiert (von einer anderen Zeile subtrahiert), so andern sichdadurch die Losungen nicht.

Wenn man zwei Spalten i , j vertauscht, so andert sichdadurch die Reihenfolge der Variablen (Wert von xi wird mitWert von xj vertauscht). Das kann man sich merken und amEnde wieder in Ordnung bringen.




Ziel: wir bringen das Gleichungssystem durch die obenbeschriebenen Umformungen auf folgende Form (obereDreiecksform):

A1,1 A1,2 . . . A1,k . . . A1,n b10 A2,2 . . . A2,k . . . A2,n b2...

. . .. . .

.... . .

......

0 . . . 0 Ak,k . . . Ak,n bk0 . . . 0 bk+1...

. . ....

...0 . . . 0 bm

wobei A1,1 = 1,A2,2 = 1, . . . ,Ak,k = 1




Bemerkung:

Es handelt sich dabei um eine Matrix mit Einsen auf der (nichtnotwendigerweise durchgehenden) Diagonale, bei der unterhalb derDiagonale nur Nullen stehen.

Außerdem kommen ab der k + 1-sten Zeile nur noch Nullen vor.Dieser Block von Nullen kann auch vollkommen fehlen.

Aus obiger Form kann man dann relativ einfach alle Losungenablesen.




Bei einer m× n-Matrix A lauft das Gaußsche Eliminationsverfahrenin n Schritten ab. In jedem Schritt wird eine weitere Spalte in diegewunschte Form gebracht.

Gaußsches Eliminationsverfahren (i-ter Schritt)

Angenommen die Spalten 1, . . . , i − 1 sind schon in dergewunschten Form. Dann sieht die Matrix folgendermaßen aus:

1 A1,2 . . . A1,i . . . A1,n b10 1 . . . A2,i . . . A2,n b2...

. . .. . .

.... . .

......

0 . . . 0 Ai ,i . . . Ai ,n bi0 . . . 0 Ai+1,i . . . Ai+1,n bi+1...

. . ....

.... . .

......

0 . . . 0 Am,i . . . Am,n bm




Wir betrachten nun Ai ,i , das sogenannte Pivotelement.

Pivotelement Ai ,i 6= 0

In diesem Fall hat Ai ,i ein multiplikatives Inverses A−1i ,i (wir

arbeiten in einem Korper!).

Wir multiplizieren die i-te Zeile mit A−1i ,i , wodurch das

Pivotelement nun den Wert 1 hat. Wir haben folgende Situation:

1 A1,2 . . . A1,i . . . A1,n b10 1 . . . A2,i . . . A2,n b2...

. . .. . .

.... . .

......

0 . . . 0 1 . . . Ai ,n bi0 . . . 0 Ai+1,i . . . Ai+1,n bi+1...

. . ....

.... . .

......

0 . . . 0 Am,i . . . Am,n bm




Pivotelement Ai ,i 6= 0 (Fortsetzung)

Wir behandeln nun jede Zeile j (mit j > i): wir multiplizieren diei-te Zeile mit Aj ,i und ziehen sie von der j-ten Zeile ab.

Dadurch ergibt sich folgende Zeile:

0 . . . 0 (Aj ,i−Aj ,i ·1) . . . (Aj ,n−Aj ,i ·Ai ,n) | (bj−Aj ,i ·bi )

und es gilt Aj ,i − Aj ,i · 1 = 0.

Damit ist die i-te Spalte jetzt in der richtigen Form.




Falls das Pivotelement Ai ,i den Wert 0 hat, so hat es keinmultiplikatives Inverses und wir konnen das vorherige Verfahrennicht anwenden. Wir unterscheiden zwei Falle:

Pivotelement Ai ,i = 0 (Fall 1)

Angenommen es gibt ein Element Aj ,i (mit j > i) unterhalb vonAi ,i mit Aj ,i 6= 0.

Dann vertausche die i-te und die j-te Zeile und fange mit demi-ten Schritt wieder von vorne an.(Achtung: die Elemente bi , bj in der rechten Spalte mussen auchgetauscht werden.)




Pivotelement Ai ,i = 0 (Fall 2)

Angenommen es gibt kein Element Aj ,i (mit j > i) unterhalb vonAi ,i mit Aj ,i 6= 0. D.h., alle Elemente in dieser Spalte, angefangenmit Ai ,i , sind gleich Null.

Dann betrachten wir das Rechteck rechts unten in der Matrix:

Ai ,i . . . Ai ,n biAi+1,i . . . Ai+1,n bi+1...

. . ....

...Am,i . . . Am,n bm

Falls alle Elemente Aj ,` (mit j ≥ i und ` ≥ i) gleich Null sind, dannhalt das Verfahren an.




Pivotelement Ai ,i = 0 (Fall 2) (Fortsetzung)

Ansonsten finde eine Spalte `, in der es einen Wert Aj ,` 6= 0 gibt(mit j ≥ i , ` ≥ i) und vertausche die Spalte i und die Spalte `.

Diese Vertauschung muss gemerkt und spater wieder ruckgangiggemacht werden!

Beginne mit dem i-ten Schritt wieder von vorne.




Ablesen der Losung: Umgeformtes Gleichungssystem

Keine Losung

Wir betrachten zunachst den unteren Block, in dem nur Nullenstehen. Falls eines der Elemente bk+1, . . . , bm ungleich Null ist, sohat das Gleichungssystem keine Losung.




Umgeformtes Gleichungssystem

Losung bestimmen

Ansonsten betrachte den oberen Block mitA1,1 = 1,A2,2 = 1, . . . ,Ak,k = 1

A1,1 A1,2 . . . A1,k . . . A1,n b10 A2,2 . . . A2,k . . . A2,n b2...

. . .. . .

.... . .

......

0 . . . 0 Ak,k . . . Ak,n bk

und behandle die Zeilen von unten nach oben wie im Folgendenbeschrieben.




Umgeformtes Gleichungssystem

Losung bestimmen (Fortsetzung)

Die j-te Zeile entspricht folgender Gleichung:

xj + Aj ,j+1 · xj+1 + · · ·+ Aj ,n · xn = bj

Es giltxj = bj − Aj ,j+1 · xj+1 − · · · − Aj ,n · xn

Setze dabei fur xj+1, . . . , xn moglicherweise bereits berechnetenWerte ein.




Nachbehandlung

Zuletzt mache noch die gemerkten Vertauschungen ruckgangig.

Dadurch erhalt man die Werte von x1, . . . , xn, wobeigegebenenfalls Variablen xj in der Darstellung ubrigbleiben. Diesebleiben stehen und reprasentieren beliebige Korperelemente.Dies passiert immer dann, wenn der obere Block nicht quadratischist und die Diagonale daher nicht ganz durchgeht.

Insgesamt erhalt man eine Menge von Losungsvektoren ~x , die wiefolgt dargestellt werden konnen:

~x ∈ {~u + xj1 · ~v1 + · · ·+ xjr · ~vr | xjk ∈ R}

Falls ~u = ~0 (das passiert, falls ~b = ~0), dann ist die Losungsmengeein Vektorraum und ~v1, . . . , ~vr eine Basis dieses Vektorraums.




Bemerkungen:

Beim Zeilen- bzw. Spaltentausch hat man meist mehrereMoglichkeiten. In diesem Fall tauscht man mit der Zeile, die dasgunstigste Pivotelement liefert.

Ein Pivotelement ist gunstig, wenn es ein einfach zu handhabendesmultiplikatives Inverses hat. Am besten ist naturlich die Eins alsPivotelement.




Beispiel 4:

Wir losen folgendes Gleichungssystem in R:

+3 · x3 +x4 = 33 · x1 +4 · x2 −2 · x3 +3 · x4 = 46 · x1 +8 · x2 +x3 −x4 = −13

In Matrixschreibweise:

0 0 3 13 4 −2 36 8 1 −1

·

x1x2x3x4

=

34−13




Anfangssituation:

0 0 3 1 33 4 −2 3 46 8 1 −1 −13

Schritt 1(a): Zeile 1 und Zeile 2 vertauschen, um Pivotelementungleich 0 zu erhalten

3 4 −2 3 40 0 3 1 36 8 1 −1 −13




Schritt 1(b): Zeile 1 mit 13 multiplizieren, um Pivotelement zu eins

zu machen1 4

3 −23 1 4

3

0 0 3 1 36 8 1 −1 −13

Schritt 1(c): Rechne “(Zeile 2) − 0· (Zeile 1)” und“(Zeile 3) − 6· (Zeile 1)”

1 43 −2

3 1 43

0 0 3 1 30 0 5 −7 −21




Schritt 2(a): Spalte 2 und Spalte 4 vertauschen, um Pivotelementungleich 0 zu erhalten. (Spaltenvertauschung merken!)

1 1 −23

43

43

0 1 3 0 30 −7 5 0 −21

Das Pivotelement ist bereits 1.

Schritt 2(b): Rechne “(Zeile 3) − (−7)· (Zeile 2)”

1 1 −23

43

43

0 1 3 0 30 0 26 0 0




Schritt 2(c): Zeile 3 mit 126 multiplizieren, um Pivotelement zu eins

zu machen1 1 −2

343

43

0 1 3 0 30 0 1 0 0

Damit ist das Gleichungssystem in der gewunschten Form.

Existenz der Losung: es gibt keinen Block von Nullen, daherexistiert eine Losung.




Bestimmung der Losung:

Zeile 3: x3 = 0Zeile 2: x2 + 3 · x3 = 3, also x2 = 3− 3 · x3 = 3− 0 = 3Zeile 1: x1 + x2 − 2

3 · x3 + 43 · x4 = 4

3 ,

also x1 = 43 − x2 + 2

3 · x3− 43 · x4 = 4

3 − 3 + 0− 43 · x4 = −5

3 − 43 · x4.

Vertauschungen ruckgangig machen: wir mussen noch x2 und x4zurucktauschen, es ergibt sich damit

x1 = −5

3− 4

3· x2 x2 beliebig x3 = 0 x4 = 3




Vektorschreibweise:

~x =

x1x2x3x4

=

−53 − 4

3 · x2x203

=

−53

003

+ x2 ·

−43

100

Dieses Gleichungssystem hat unendlich viele Losungen, eine furjede Belegung von x2 mit einer reellen Zahl.




Beispiel 2 (noch einmal):

x1 + 2 · x2 = 3

−2 · x1 − 4 · x2 = 1

Anfangssituation:

1 2 3−2 −4 1




Schritt 1: Rechne “(Zeile 2) − (−2)·(Zeile 1)”

1 2 30 0 7

Existenz der Losung: Im unteren Block der Nullen ist das Elementin der rechten Spalte ungleich Null (7). Daher existiert keineLosung.




Bemerkung:

Das Gaußsche Eliminationsverfahren kann nicht dazu benutztwerden, um diophantische Gleichungen zu losen.

Dort sucht man nach Losungen in den ganzen Zahlen Z. Dieganzen Zahlen mit der Addition und Multiplikation bilden jedochkeinen Korper (fehlende multiplikative Inverse!).

Das Gaußsche Eliminationsverfahren ist jedoch fur jeden beliebigenKorper (z.B. (Zp,+p, ·p), p Primzahl) anwendbar.



Multiplikatives Inverses einer Matrix

Mit Hilfe des Gaußschen Eliminationsverfahrens kann man nun dasmultiplikative Inverse einer Matrix bestimmen.

Gegeben sei eine quadratische Matrix

A =

A1,1 . . . A1,n

.... . .

...An,1 . . . An,n

Man stellt sich vor, dass das multiplikative Inverse A−1 ausSpaltenvektoren ~a1, . . . , ~an zusammengesetzt ist und schreibtA−1 =

(~a1 . . . ~an

).

(Siehe auch den Abschnitt uber Erzeugendensysteme und BasenInvertierbare Matrizen und Basen .)




Damit A−1 das Inverse von A ist, muss gelten:

A · A−1 = A ·(~a1 . . . ~an

)=(A · ~a1 . . . A · ~an

)

= En =

1 . . . 0...

. . ....

0 . . . 1

=

(~e1 . . . ~en

)

Also gilt fur jedes i ∈ {1, . . . , n}: A · ~ai = ~ei

Dabei ist ~ei der i-te Einheitsvektor.

Man muss also n Gleichungssysteme mit jeweils n Gleichungenlosen. Existieren fur alle Gleichungssysteme Losungen, so erhaltman die Inverse A−1. Anderenfalls gibt es keine Inverse.




Beispiel: wir bestimmen das multiplikative Inverse folgender Matrix

A =

(3 41 −3

)

Wir setzen zunachst ~a1 =

(x1x2

)und losen das Gleichungssystem

A · ~a1 = ~e1:

3 · x1 + 4 · x2 = 1

x1 − 3 · x2 = 0

Das ergibt die Losungen x1 = 313 und x2 = 1

13 .




Wir setzen nun ~a2 =

(y1y2

)und losen das Gleichungssystem

A · ~a2 = ~e2:

3 · y1 + 4 · y2 = 0

y1 − 3 · y2 = 1

Das ergibt die Losungen y1 = 413 und y2 = − 3

13 .

Insgesamt erhalt man folgende Matrix A−1:

A−1 =(~a1 ~a2

)=

(x1 y1x2 y2

)=

(313

413

113 − 3

13

)




Bemerkung (Gauß-Jordan-Verfahren):

Es gibt eine effizientere Methode um das Inverse einer Matrix zubestimmen. Man kann insbesondere alle n Gleichungssysteme“gleichzeitig” losen.

Dabei schreibt man die zu invertierende Matrix und dieEinheitsmatrix wie folgt nebeneinander:

3 4 1 01 −3 0 1

Dann formt man die linke Matrix durch Zeilentausch (nichtSpaltentausch!), indem man Zeilen mit einem Wert (ungleich 0)multipliziert und indem man Vielfache von Zeilen zu anderenZeilen addiert, zur Einheitsmatrix um.Die Matrix, die dabei rechts entsteht, ist dann die Inverse.



Schlussbemerkungen

Es gibt noch viele andere wichtige Gebiete im Zusammenhang mitalgebraischen Strukturen, Vektorraumen und Matrizen:

Ringe (Strukturen, die ahnlich zu Korpern sind, in denen aberweniger Gesetze gelten)

Eigenvektoren und Eigenwerte

Determinanten

. . .


Documents

Mathematische Strukturen Sommersemester 2016...In vielen F allen (z.B. zum L osen von Gleichungssystemen) ben otigt man beim Rechnen etwas mehr Struktur: man braucht sogenannte Inverse