Lineare Algebra I - Prof. Bürgisser - WS 2007 / 08

Mitschrift zur Linearen Algebra I

Wintersemester 07 / 08

bei Prof. Dr. Peter BurgisserMit Vorbehalt von Tippfehlern sowie sprachlichen und mathematischen bzw.

inhaltlichen Ungenauigkeiten

1

Lineare Algebra I


Vorlesung 1

Mittwoch, 17.10.2007

Michael Habermann

[email protected]

1 Grundlagen

Was ist eine Aussage?

Aristoteles: ”Eine Aussage ist, was entweder wahr oder falsch ist”

Welche der folgenden Satze sind Aussagen?

· Der Mond kreist um die Erde.

· 1 + 1 = 3.

· Es ist warm hier.

· Angela Merkel ist schon.

· x+ 1 = y

Eine Implikation / Folgerung verknupft Aussagen und transportiert Wahrheit.

A,B seien Aussagen.

A⇒ B bedeutet:

· A impliziert B, aus A folgt B,

· A ist hinreichend(e Bedingung) fur B,

· B ist notwendig(e Bedingung) fur A,

· wenn A (wahr ist), dann (ist) B (wahr)

A⇒ B ist gleichbedeutend mit nicht B ⇒ nicht A

aber nicht mit B ⇒ A

· Wer nicht wagt, der nicht gewinnt!

Aquivalenz: Falls A⇒ B und B ⇒ A,

so sind die Aussagen A und B aquivalent: A⇔ B

Implikationsketten: A⇒ A1 ⇒ A2 ⇒ ...⇒ An ⇒ B

impliziert: A⇒ B

1.1 Mengen

Grundbegriff, auf dem die ganze Mathematik aufbaut.

Georg Cantor (1895): ” Eine Menge ist die Zusammenfassung bestimmter,

wohlunterschiedener Objekte, unserer Anschauung

oder unseren Denkens, wobei von jedem dieser Objekte feststeht,

ob es zur Menge gehort oder nicht.”

Die Objekte der Menge heißen Elemente der Menge.

Schreiben: a ∈ A: a ist Element der Menge A

a /∈ A: a ist nicht Element der Menge A

Darstellung von Mengen:

· Aufzahlung: A = 1, 2, 3, 4

c© by Michael Habermann Seite 2

Lineare Algebra I


Vorlesung 1


Michael Habermann

[email protected]

· Beschreibung der Eigenschaft der Elemente

A = a : a ungerade ganze Zahl, 0 ≤ a < 10

1.1.1 Beispiel

· p = p : p Primzahl, 0 ≤ p ≤ 9 = 2, 3, 5, 7· N = 0, 1, 2, 3, ... Menge der naturlichen Zahlen

· Z = ...,−3,−2,−1, 0, 1, 2, 3, ...Menge der ganzen Zahlen

Die leere Menge ∅ = enthalt keine Elemente: ∅ = x : x 6= x

1.1.2 Definition

Eine Menge A heißt Teilmenge der Menge B, falls jedes Element

von A auch Element von B ist.

D.h. Fur alle a ∈ A gilt a ∈ B Schreibweise: A ⊆ B

1.1.3 Definition

Zwei Mengen A und B heißen gleich, falls

A ⊆ B und B ⊆ A Schreibweise: A = B

D.h. A = B bedeutet: Fur alle a gilt a ∈ A, genau dann, wenn a ∈ B

1.1.4 Beispiel

· N ⊆ Z, aber N 6= Z, da −1 /∈ N

· 2, 4 ⊆ 1, 2, 3, 4, 2, 4 6= 1, 2, 3, 4· 2, 4 = a : a gerade ganze Zahl, 1 < a ≤ 4· Die leere Menge ∅ ist Teilmenge jeder Menge A,

auch ∅ ⊆ ∅. Nicht verwechseln mit ∅ /∈ ∅

· Bei Aufzahlungen werden Wiederholungen und die Reihenfolge ignoriert.

2, 4, 4, 2 = 2, 4 = 4, 2

1.2 Verknupfungen von Mengen:

1.2.1 Definition

Seien A und B Mengen

· Die Schnittmenge (der Durchschnitt) ist definiert als

A ∩B := x : x ∈ A und x ∈ B· Die Vereinigungsmenge ist defiert als

A ∪B := x : x ∈ A oder x ∈ B· Die Differenzmenge ist definiert als

A \B := x : x ∈ A und x /∈ B


Lineare Algebra I


Vorlesung 1


Michael Habermann

[email protected]

· A und B heißen disjunkt, falls

A ∩B = ∅

D.h. A und B enthalten keine gemeinsamen Elemente

1.2.2 Beispiel

A := 0, 1, 3, 5, 7, 9, B := 0, 1, 2, 4, 6, 8⇒ A ∩B = 0, 1, A ∪B = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

A \B = 3, 5, 7, 9

Eigenschaften der Mengenverknupfungen

1.2.3 Satz:

(1) A ∩∅ = ∅, A ∪∅ = A (∅ extremal, neutral)

(2) A ∩A = A, A ∪A = A (Idenpotenz)

(3) A ∩B = B ∩A, A ∪B = B ∪A (Kommutativitat)

(4) (A ∩B) ∩ C = A ∩ (B ∩ C),

(A ∪B) ∪ C = A ∪ (B ∪ C) (Assoziativitat)

(5) A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C),

A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) (Distributivitat)


Lineare Algebra I


Vorlesung 2

Donnerstag, 18.10.2007

Michael Habermann

[email protected]

1.2.4 Satz (5):

Seien A,B,C Mengen

Dann gilt: A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩B)

Beweis: Beh. 1: A ∩ (B ∪ C) ⊆ (A ∩B) ∪ (A ∩ C)

Sei a ∈ A ∩ (B ∪ C). Dann a ∈ A und a ∈ B ∪C1. Fall: a ∈ B ⇒ a ∈ A ∩B ⇒ a ∈ (A ∩B) ∪ (A ∩ C)

2. Fall: a /∈ B ⇒ a ∈ C ⇒ a ∈ A ∩ C ⇒ a ∈ (A ∩B) ∪ (A ∩ C)

Beh. 2: (A ∩B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C).

Sei a ∈ (A ∩B) ∪ (A ∩ C)

1. Fall: a ∈ A ∩B ⇒ a ∈ A und a ∈ B ⇒ a ∈ B ∪ CAlso: a ∈ A ∩ (B ∪ C)

2. Fall: a /∈ A ∩B ⇒ a ∈ A ∩ C ⇒ a ∈ A und a ∈ C ⊆ B ∪ CAlso: a ∈ A ∩ (B ∪ C)

q.e.d.

1.2.5 Definition

Die Potenzmenge P (A) einer Menge A ist die Menge aller Teilmengen von A

P (A) = B : B ⊆ A

1.2.6 Beispiel:

· A = 1, 2 ⇒ P (A) = ∅, 1, 2, 1, 2· Fur jede Menge A gilt ∅ ∈ P (A) und A ∈ P (A).

· P (1) = ∅, 1· P (∅) = ∅

Man beachte also den Unterschied zwischen ∈ und ⊆:

1 ∈ 1, 2; 1 ⊆ 1, 2; 1 /∈ 1, 2; 1 ∈ P (1, 2)Statt P (A) auch 2A

Die naive Definition von Mengen nach Cantor fuhrt zu Widerspruchen:

1) Russelsche Antinomie (Paradoxie)

Sei R die Menge aller Mengen, die sich nicht selbst als Element enthalten:

R := A : A Menge und A /∈ AWare R eine Menge, so musste entweder R ∈ R oder R /∈ R.

Aber: R ∈ R⇔ R /∈ R2) Der Barbier von Sevilla rasiert genau diejenigen mannlichen Einwohner von Sevilla,

die sich nicht selbst rasieren.

Rasiert der Barbier sich selbst?

M := x : x mannliche Einwohner von Sevilla, den der Barbier rasiert.M ist keine Menge!


Lineare Algebra I


Vorlesung 2


Michael Habermann

[email protected]

1.3 Abbildungen

1.3.1 Definition

Seien A und B Mengen, Ist a ∈ A und b ∈ B, so nennt man (a, b) ein geordnetes Paar.

Zwei geordnete Paare (a, b) und (a′, b′) heißen gleich, falls a = a′ und b = b′.

Das kartesische Produkt von A und B ist die menge aller geordneten Paare (a, b),

wobei a ∈ A, b ∈ B: A×B := (a, b) : a ∈ A, b ∈ BDem ”kartesisch” nach Rene Decartes, einem franzosischen Philosoph und

Mathematiker (17 Jhdt.), der die analytische Geometrie erfunden hat.

1.3.2 Beispiel

· (1, 2) 6= (2, 1)

· 1, 2, 3 × b1, b2 = (1, b1), (1, b2), (2, b1), (2, b2), (3, b1), (3, b2)· R = reellen Zahlen ⇒ R×R = (x, y) : x, y ∈ R(x, y) kartesische Koordinaten eines Produktes.

1.4 Beziehungen zwischen Objekten als Relationen

1.4.1 Defintion

Eine Relation zwischen zwei Mengen A und B

ist eine Teilmenge R ⊆ A×B. Falls A = B, sprechen wir

von einer Relation auf A

1.4.2 Beispiel

· A = 1, 2, 3, B = b1, b2, R := (1, b2), (2, b1), (3, b1)· A = B = R, R= := (x, y) : (x, y) ∈ R×R, x = y

= (x, x) : x ∈ RR< := (x, y) ∈ R×R : x < y

1.4.3 Wichtige Klassen von Relationen:

· Abbildungen (oder Funktionen)

· Aquivalenzrelationen

· Ordnungsrelationen


Lineare Algebra I


Vorlesung 3


Michael Habermann

[email protected]

Wiederholung: Mengen A, Element x

x ∈ A oder x /∈ AA ⊆ BA = B bedeutet: A ⊆ B und B ⊆ AA ∩B := x : x ∈ A und x ∈ BA ∪B := x : x ∈ A oder x ∈ BA \B := x : x ∈ A und x /∈ B

kartesisches Produkt der Mengen A und B

A×B := (a, b)︸︷︷︸

geordnetesPaar

: a ∈ A und b ∈ B

(a, b) = (a′, b′) genau dann, wenn a = a′ und b = b′

(1, 2) 6= (2, 1) 1, 2 = 2, 1, 1, 1 = 1

Relation R ⊆ A×BRelation in A, falls B = A, d.h. R ⊆ A×A

Abbildungen Def.: Eine Abbildung (oder Funktion)

von der Menge A in die Menge B ist eine Relation f ⊆ A×B derart,

dass es fur alle a ∈ A genau ein b ∈ B gibt mit (a, b) ∈ fSchreibweise: f : A→ B

A heisst Definitionsbereich von f

B heisst Bildbereich oder Wertebereich von f

Das zu a ∈ A eindeutig gehorende b ∈ B mit (a, b) ∈ f wird meist

bezeichnet mit f(a) ”f von a”

Illustrationen:

1.4.4 Beispiel

· R = (1, b2), (2, b1), (3, b1) ist eine Abbildung

f : 1, 2, 3 → b1, b2Es gilt f(1) = b2, f(2) = b1, f(3) = b1· (1, b1), (2, b2), (1, b2) keine Abbildung falls b1 6= b2

1.4.5 Beispiel

Oft ergibt sich f(a) durch eine konkrete Rechenvorschrit, z.B.

f : N→ N, f(a) = a2 Andere Schreibweise: f : N→ N, a 7→ a2

Der Name der Variablen a ist egal, kann geradesogut schreiben

f : N→ N, x 7→ x2

Der Graph einer Abbildung f : A→ B ist definiert als

Gf := (a, f(a)) : a ∈ A(Streng genommen ist Gf dasselbe wie f)


Lineare Algebra I


Vorlesung 3


Michael Habermann

[email protected]

1.4.6 Bemerkung

Zwei Abbildungen f : A→ B mit f ′ : A′ → B′ sind gleich, falls

A = A′ und B = B′ und f(a) = f ′(a) fur alle a ∈ A

1.4.7 Beispiel

N→ N, x 7→ x2 und

Z→ Z, x 7→ x2 sind verschiedene Abbildungen.

Z→ N, x 7→ x2

1.4.8 Defintion

Eine Abbildung f : A→ B heisst

· injektiv, falls aus a1, a2 ∈ A mit

a1 6= a2 stets f(a1) 6= f(a2) folgt

(Fur alle a1, a2 ∈ A gilt: a1 6= a2 ⇒ f(a1) 6= f(a2)

Aquivalent dazu:

Fur alle a1, a2 ∈ A gilt: a1 = a2 ⇐ f(a1) = f(a2)

Beh.: Die Aussagen I und II sind aquivalent, d.h.

I ⇒ II (aus I folgt II)

II ⇒ I (aus II folgt I)

Zeigen I ⇒ II: Nehmen an, I ist wahr. Wollen zeigen, dass II wahr ist.

Fuhre einen indirekten Beweis. Nehmen an, dass II falsch ist.

Das bedeutet, es gibt a1, a2 ∈ A und f(a1) = f(a2) aber a1 6= a2

Weil I wahr ist, gilt aber f(a1) 6= f(a2). DAS IST EIN WIDERSPRUCH!!!

⇒ Unsere Annahme war deshalb falsch, deshalb ist II wahr //)

· surjektiv, falls fur alle b ∈ B ein a ∈ A existiert mit b = f(a)

· bijektiv, falls f injektiv und surjektiv ist.

Illustration

1.4.9 Beispiel

· f : lebende Menschen → N, x 7→ Lebensalter von x in Jahren

nicht surjektiv, nicht injektiv

· 1) f : N→ N, f(x) = x2 injektiv, nicht surjektiv

2) g : Z→ N, g(x) = x2 nicht injektiv, nicht surjektiv

3) h : R→ y ∈ R : y ≥ 0, h(x) = x2 nicht injektiv, nicht surjektiv


Lineare Algebra I


Vorlesung 4


Michael Habermann

[email protected]

f : A→ B, a 7→ f(a)

1.4.10 Definition

Die identische Abbildung auf der Menge A ist definiert als

idA : A→ A, a 7→ a

1.4.11 Defintion

f : A→ B und g : B → C Abbildungen,

so definiert man deren Komposition oder Hintereinanderausfuhrung ob die Abbildung,

g f : A→ C, a 7→ g(f(a))

1.4.12 Satz

Eine Abbildung f : A→ B ist bijektiv, genau dann,

wenn es eine Abbildung g : B → A gibt mit

g f = idA und f g = idB

Hier ist zu zeigen, dass zwei Aussagen I und II aquivalent sind.

D.h. I gilt genau dann, wenn II gilt.

Zeigen: · I impliziert II (aus I folgt II), I ⇒ II

· II impliziert I

Beweis:

(1) Sei f : A→ B bijektiv. Zu b ∈ B gibt es genau ein a ∈ A mit f(a) = b

Wir definieren die Abbildung g : B → A, welche b ∈ B dieses eindeutig bestimmte a zuordnet

Dann gilt: f(g(b)) = b fur alle b ∈ B, d.h. f g = idB

Ferner

g(f(a)) = a fur alle a ∈ A, d.h. g f = idA

(2) Umgekehrt sei g : B → A mit g f = idA, f g = idB gegeben

· Seien a1, a2 ∈ A mit f(a1) = f(a2). Dann a1 = g(f(a1)) = g(f(a2)) = a2

Folglich ist f injektiv

· Sei b ∈ B. Setze a := g(b). Dann gilt f(a) = f(g(b))↓= b

Also ist f surjektiv //

Erganzung zum Satz:

Die Abbildung g im Satz ist eindeutig bestimmt und heisst inverse Abbildung um f

Man schreibt dafur g = f−1

Vorsicht: f−1 nicht zu verwechseln mit 1f(x) = f(x)−1 falls f : A→ R = 0

a 7→ f(x)


Lineare Algebra I


Vorlesung 4


Michael Habermann

[email protected]

1.4.13 Definition

Sei f : A→ B eine Abbildung

· Fur X ⊆ A heisst die Menge

f(X) := f(x) : x ∈ Xdas Bild von X unter f

· Fur Y ⊆ B heisst die Menge

f−1(Y ) := a ∈ A : f(a) ∈ Y (Vorsicht! Die Abbildung f−1 ist im allgemeinen nicht definiert!)

heisst Urbild von Y unter f

1.4.14 Beispiel

f : R→ R, f(x) = x2. Fur a, b ∈ R, a ≤ b bezeichne mit

[a, b] := x ∈ R : a ≤ x ≤ bdas Intervall mit Endpunkten a, b

X = [1, 2] f(X) = [1, 4]

Y = [1, 4] f−1(Y ) = [−2,−1] ∪ [1, 2]

1.4.15 Bemerkung

Sei f bijektiv, Dann f−1 : B → A

f−1(Y )︸︷︷︸

BildvonY unterf−1

= f−1(Y )︸︷︷︸

UrbildvonY unterf

1.5 Ordnungs und Aquivalentrelationen

Eine Relation in A ist eine Teilmenge R ⊆ A×A

1.5.1 Beispiel

A = N = 0, 1, 2, ...R := (x, y) ∈ N×N : x ≤ yKleiner-Gleich Relation

1.5.2 Definition

Eine Relation ≤ in A heisst partielle Ordnung, falls folgende Eigenschaften erfullt sind.

Reflexivitat: a ≤ a fur alle a ∈ AAntisymetrie: Aus a ≤ b und b ≤ a folgt a = b

fur alle a, b ∈ ATransitivitat: Aus a ≤ b und b ≤ c folgt a ≤ c

fur alle a, b, c ∈ A


Lineare Algebra I


Vorlesung 4


Michael Habermann

[email protected]

1.5.3 Beispiel

1. ≤ in N ist eine partielle Ordnung

2. Seien a, b ∈ N

a teilt b, falls es ein c ∈ N mit ac = b gibt

In Zeichen: a | b z.B. 3 | 6, 6 ∤ 15

(Die Teilbarkeit | ist eine partielle Ordnung auf N)

3. Sei Ω eine Menge.

Potenzmenge P(Ω) = a : a ⊆ ΩDie Teilmengeneigenschaft a ⊆ b definiert eine partielle Ordnung auf P(Ω)

1.5.4 Bemerkung

0 | 0, denn wahle belibiges c: 0 · c = 0

- Reflexivitat: a | a fur alle a ∈ N

(Grund: a· |= a)

- Antisymetrie: Sei a | b und b | cEs gibt c1, c2 ∈ N mit ac1 = b, bc2 = a

⇒ (bc2)c1 = b

1. Fall: b 6= 0

⇒ c2c1 = 1 ⇒ c1 = c2 = 1 ⇒ a = b

2. Fall: b = 0

⇒ a = 0 ⇒ a = b = 0√


Lineare Algebra I


Vorlesung 6


Michael Habermann

[email protected]

1.6 Aussagen

Aristoteles (384 - 322 vor Christus)

1.6.1 Definition

Eine Aussage ist eine sprachlichen Gebilde, das entweder wahr oder falsch ist.

Verknupfung von Aussagen: Seien A und B Aussagen

Wir definieren:

A ∧B (”A und B”) ist genau dann wahr, wenn A und B wahr ist.

A ∨B (”A oder B”) ist genau dann wahr, wenn A oder B wahr ist.

¬A (”nicht A”) ist genau dann wahr, wenn A falsch ist.

Beschreibung mit Wahrheisfeldern

A B A ∧B A ∨B A⇒ B A⇔ B B ⇒ A (A⇒ B) ∧ (B ⇒ A)

f f f f w w w w

f w f w w f f f

w f f w f f w f

w w w w w w w w

Implikationen A⇒ B (”A impliziert B, ”aus A folgt B”)

definiert durch Tabelle

! Vorsicht: A⇒ B ist wahr, wenn A falsch ist:

1 = 2⇒ Ich bin ein Esel wahre Aussage

Die Aquivalenz A ⇔ B (”A aquivalent B”)

ist definiert durch Tabelle

A ist genau dann wahr, wenn B wahr ist.

1.6.2 Bemerkung

A⇔ B ist logisch gleichwertig zu (A⇒ B) ∧ (B ⇒ A)

Wichtiges Prinzip: Man beweist Aquivalenz zweier Aussagen durch den Nachweis

der Implikationen in beide Richtungen.

1.6.3 Bemerkung (Kontrapositionsgesetz)

A⇒ B ist logisch gleichwertig zu ¬B ⇒ ¬A und auch zu ¬A ∨B¡

1. Beweis: mit Wahrheitstafel (Ubung)


Lineare Algebra I


Vorlesung 6


Michael Habermann

[email protected]

2. Beweis: A⇒ B ist falsch genau dann wenn A wahr und B falsch

(¬B)⇒ (¬A) ist falsch genau dann, wenn ¬B wahr und ¬A falsch

(¬A) ∨B ist falsch genau dann, wenn (¬A) wahr und B falsch

1.6.4 Beispiel:

Haufiger Fehler: falsche Ubersetzung in umgangssprachliche Implikationen

A ”es regnet”

B ”ich nehme einen Schirm mit”

A⇒ B wenn es regnet, nehme ich einen Schirm mit

B ⇒ A wenn ich einen Schirm mitnehme, dann regnet es

¬A⇒ ¬B wenn es nicht regnet, so nehme ich keinen Schirm mit

1.6.5 Methode des indirekten Beweises

Um sich in der Wahrheit einer Aussage A zu uberzeugen, nimmt man an, dass

A falsch ist und folgern mittels logischer Schlusse,

dass eine Aussage B sowohl wahr als auch falsch ist.

Da letzeres absurd ist, muss A wahr sein.

1.6.6 Beispiel

Zur Illustration:

Definition: Eine Primzahl ist eine Zahl p ∈ N, p > 1

deren einzige positive Teiler 1 und p sind.

(∗) Man sieht leicht: Jede Zahl n ∈ N und n > 1 wird von

einer Primzahl geteilt

Satz Es gibt unendlich viele Primzahlen

Beweis: (Euklid) Wir fuhren einen indirekten Beweis

Angenommen es gabe nur endlich viele Primzahlen

Diese seien p1, p2, ..., pn

Bilde das Produkt q := p1 · p2 · ... · pn

Nach (∗) wird q + 1 von einer Primzahl geteilt.

Also gibt es ein i ∈ 1, 2, ..., n so dass pi|(q + 1)

Andererseits ist pi|q. Daraus folgt: pi|1Daraus folgt pi = 1, ein Widerspruch zu pi > 1 Also war die Annahme falsch und es gibt unendlich viele Primzahlen. //


Lineare Algebra I


Vorlesung 6


Michael Habermann

[email protected]

1.6.7 Regeln beim Verknupfen von Aussagen

doppelte Negation ¬¬A⇔ A

de Morgan ¬(A ∨B)⇔ (¬A) ∧ (¬B)

¬(A ∧B)⇔ (¬A) ∨ (¬B)

Distributivitat A ∧ (B ∨ C)⇔ (A ∧B) ∨ (A ∧ C)

A ∨ (B ∧ C)⇔ (A ∨B) ∧ (A ∨ C)

A ∨ (¬A)⇔ w

A ∧ (¬A)⇔ f

1.6.8 Beispiel

Vereinfachung von zusammengesetzten Aussagen

A ∧ (A ∨B) ⇔ A

¬B ∧ (A ∨B) ⇔ (¬B ∧A) ∨ (¬B ∧B) ⇔ ¬B ∧A(¬(¬A ∧B)) ∧ (A ∨B)

⇔ (A ∨ ¬B) ∧ (A ∨B)︸︷︷︸

:=C

⇔ (A ∧ C)︸︷︷︸

A

∨(¬B ∧ C)

⇔ A ∨ (¬B ∧A) ⇔ A


Lineare Algebra I


Vorlesung 7


Michael Habermann

[email protected]

1.6.9 Pradikate

1 + 1 = 2 wahre Aussage

x+ y = y + x keine Aussage

Sei M eine Menge. Eine Aussagenform (also ein Pradikat)

ist ein ”Satz” in Variablen x1, ..., xn, der zu einer Aussage wird,

wenn jedes xi durch ein Element von M erzeugt wird.

Bsp.:

M = N (x+ y = y + x) ∧ (z = 1) ist ein Pradikat

Pradikate konnen mit ∧,∨,¬ verknupft werden.

1.6.10 Quantoren

Um Pradikate in Aussagen umzuwandeln, verwenden wir

Allquantor: ∀x ”fur alle x ∈M”

Existenzquantor: ∃x ”es gibt ein x ∈M”

Sei P (x) ein Pradikat uber der Menge M in der Variablen x. Die Aussage

∃P (x) ist genau dann wahr wenn es wenigstens ein a ∈M gibt,

so dass P (a) wahr ist.

∀P (x) ist genau dann wahr, wenn P (a) fur jedes a ∈M wahr ist.

Bsp.:

∀x(x ≤ x+ 1) ist wahr uber M = N

Man schreibt auch

∀x ∈MP (x) bzw. ∃x ∈MP (x)

Man macht entsprechende Festsetzungen fur mehrere Variablen

∀x∀y(x+ y = y + x) ist wahr uber N

Bsp.:

∀x∃y(x = y2) falsch uber M = R

wahr uber M = a ∈ R : a ≥ 0∀x∃y((x ≥ 0)⇒ x = y2) wahr uber M = R

! Vorsicht !: Bei verschiedenen Quantoren kommt es auf die Reihenfolge an

Bsp.:

M = Z:

∀x∃y(y ≤ x) ist wahr

∃y∀x(y ≤ x) ist falsch


Lineare Algebra I


Vorlesung 7


Michael Habermann

[email protected]

1.6.11 Negationsregel

¬(∀xP (x)) logisch aquivlanet zu ∃x¬P (x)

¬(∃xP (x)) logisch aquivalent zu ∀x¬P (x)

1.7 Vollstandige Induktion

Ein machtiges Beweisprinzip, um Aussagen der Form

∀n ∈ NP (n) zu beweisen.

Induktionsprinzip: Sei P (n) ein Pradikat uber N

Induktionsvorraussetzung: P (0) ist wahr.

Induktionsschritt: ∀n ∈ N(P (n)⇒ P (n+ 1)) ist wahr.

Dann ist ∀n ∈ NP (n) wahr.

1.7.1 Axiom

Jede nichtleere Teilmenge von N hat ein kleinstes Element.

1.7.2 Beweis des Induktionsprinzip

Wir schließen indirekt. Angenommen, es gibt ein n0 ∈ N so dass P (n0) falsch ist.

Die Menge A := n ∈ N : P (n) falsch ist nicht leer, da n0 ∈ AAxiom ⇒ A hat ein kleinstes Element m.

Es gilt m > 0, da 0 /∈ ADa m minimal ⇒ m− 1 /∈ AAlso P (m− 1) wahr. Nach dem Induktionsschritt P (m− 1)⇒ P (m) gilt P (m wahr.

D.h. m /∈ A Widerspruch //

1.7.3 Beispiel

Beispiel 1: ∀n ∈ N(n+1∑

k=1

k = (n+1)·(n+2)2 )


Lineare Algebra I


Vorlesung 7


Michael Habermann

[email protected]

Beweis durch Induktion:

Induktionsvorraussetzung (IV): n = 0: 1 = 1·22

√

Induktionsschritt (IS): Sei n ∈ N belibig. Es gelten+1∑

k=1

k = (n+1)·(n+2)2

Dann:n+2∑

k=1

k =n+1∑

k=1

k + (n+ 2)

= (n+1)·(n+2)2 + (n+ 2)

= (n+ 2)[n+12 + 2

2 ] = (n+2)·(n+3)2 //

1.7.4 Satz (Summe der geometrischen Reihe)

Sei q ∈ R, q 6= 1 und n ∈ N Dann

q0 + q1 + q2 + ...+ qn = qn+1−1q−1

Beweis durch Induktion:

(IV): n = 0 q0 = q1−1q−1 = 1

√

(IS): Angenommen P (n) ist wahr.

(q0 + q1 + ...+ qn) + qn+1 = qn+1−1q−1 + qn+1 = qn+1−1

q−1 + qn+1(q−1)q−1 = qn+2−1

q−1 //

1.7.5 Satz

Alle naturlichen Zahlen sind gleich.

Beweis: Fur a, b ∈ N definiere maxa, b :=

a falls a ≥ bb falls a < b

Betrachte folgendes Pradikat P (n)

∀a, b ∈ N(maxa, b = n⇒ a = b)

(IV): P (0) ist wahr, denn maxa, b = 0⇒ a = b = 0

(IS): Es gelte P (n). Seien a, b ∈ N und maxa, b = n+ 1

Dann gilt maxa− 1, b− 1 = n

Nach Induktionsvorraussetzung gilt:

a− 1 = b− 1, also a = b //

∀nP (n) wahr ⇒ ”alle naturlichen Zahlen sind gleich”


Lineare Algebra I


Vorlesung 7


Michael Habermann

[email protected]

Modifiziertes Induktionsprinzip:

Sei P (n) ein Pradikat uber N , n0 ∈ N

Verankerung: P (n0) ist wahr

Schritt: Fur belibiges n ≥ n0 gilt

P (n)⇒ P (n+ 1)

Dann ist P (n) wahr fur alle n ≥ n0

Beweis: Wende das Induktionsprinzip auf das Pradikat

Q(n) := P (n+ n0) an

Q(0) = P (n0) wahr

∀n ∈ N(Q(n)⇒ Q(n+ 1)

2 Mengen

2.1 Endliche Mengen

2.1.1 Definiton

Zwei Mengen A und B heissen gleichmachtig, falls es eine Bijektion

von A nach B gibt. Notation A ≃ B

2.1.2 Bemerkung

A ≃ AA ≃ B ⇒ B ≃ A(A ≃ B) ∧ (B ≃ C) ⇒ A ≃ C

Beweis: f : A→ B bijektiv

g : B → C bijektiv

⇒ g f : A→ C bijektiv //


Lineare Algebra I


Vorlesung 8


Michael Habermann

[email protected]

2.1.3 Beispiele endlicher Mengen

N = 0, 1, ...,N∗ := 1, 2, ... = N \ 0

2.1.4 Definition

Zwei Mengen A und B heissen gleichmachtig falls,

es eine Bijektion A→ B gibt. Schreibweise A ≃ B

2.1.5 Definition

Eine Menge A heisst endlich, falls A = ∅ oder

es gibt n ∈ N∗ mit A ≃ 1, 2, ..., n

2.1.6 Lemma

Fur n,m ∈ N∗ gilt.

1, 2, ..., n ≃ 1, 2, ...,m ⇒ n = m

Aufgrund des Lemmas ist die folgende Definition sinnvoll

2.1.7 Definition

Die Kardinalitat |A| einer nichtleeren endlichen Menge ist die eindeutig bestimmte

Zahl n ∈ N∗ mit A ≃ 1, 2, ..., nMan sagt |∅| = 0

2.1.8 Bemerkung

Sei A endlich. Dann A = ∅ ⇔ |A| = 0

Folgerung: Seien A,B endliche Mengen. Dann

A ≃ B ⇔ |A| = |B|

Beweis: ”⇐”: Sei n := |A| = |B|. Dann

A ≃ 1, 2, ..., n, B ≃ 1, 2, ..., n⇒ A ≃ B

”⇒”: A ≃ 1, 2, ..., |A|, B ≃ 1, 2, ..., |B|⇒ 1, 2, ..., |A| ≃ 1, 2, ..., |B|Lemma⇒ |A| = |B|. //

Beweis des Lemmas: Beweise mit Induktion nach m, dass

∀n ∈ N∗(1, 2, ...,m = 1, 2, ..., n ⇒ m = n) (Beweis als Ubung)

Seien A1, A2, ..., Ar Mengen. Deren Vereinigung ist


Lineare Algebra I


Vorlesung 8


Michael Habermann

[email protected]

A1 ∪A2 ∪ ... ∪Ar =⋃r

i=1Aj := xi∃i ∈ 1, 2, ..., rx ∈ AjAnalog definiert man den Durchschnitt

A1 ∩A2 ∩ ... ∩Ar =⋂r

i=1Aj := xi∀i ∈ 1, 2, ..., rx ∈ Aj

2.1.9 Satz 1

Seien A1, ..., Ar endliche Mengen, die paarweise disjunkt sind.

(d.h. ∀i 6= y Ai ∩Aj = ∅). Dann ist A1 ∪ ... ∪Ar endlich.

und |A1 ∪A2 ∪ ... ∪Ar| = |A1|+ |A2|+ ...+ |Ar |

Beweis: Induktion nach r. Start i = 1 klar

Sei r = 2. oBdA A1, A2 6= ∅. Seien

f : 1, 2, ..., n1 → und g : 1, 2, ..., n2 → A2 bijektiv

Definiere: h : 1, 2, ..., n1 + n2 → A1 ∪A2,

h(x) = f(x), falls 1 ≤ x ≤ n1 oder g(x− n1) falls n1 < x ≤ n1 + n2

h ist surjektiv. h ist injektiv, mit A1 ∩A2 = ∅

Also h bijektiv ⇒ |A1 ∪A2| = n1 + n2

Induktionsschritt Es gelte die Behauptung fur r ≥ 1

Seien A1, ..., Ar+1 und paarweise disjunkt. Dann sind

B := A1 ∪ ... ∪Ar und Ar+1, disjunkt. Also

|A1 ∪ ... ∪Ar+1| = |B ∪Ar+1| = |B|+ |Ar+1| = |A1|+ ...+ |Ar|+ |Ar+1| //

Das kartesische Produkt von Mengen A1, ..., Ar ist definiert als

A1 ×A2 × ...×Ar := (a1, a2, ...ar) : ai ∈ Ai fur i ∈ 1, 2, ..., r

2.1.10 Satz 2

Sind A1, ..., Ar| = |A1| · |A2| · ... · |Ar |

Beweis: Indukiton nach r. Start r = 1 klar.

sei r = 2: Es gilt

A1 ×A2 =⋃

b∈A2A1 × b

Ausserdem (A1 × b) ∩ (A1 × b′ = ∅ falls b 6= b′

Es gilt A1 × b ≃ A1, also |A1 × b| = |A1|Satz 1 ⇒|A1 ×A2| =

∑

b∈A2

|A1 × b =∑

b∈A2

|A1| = |A1| · |A2|

Der Induktionsschritt geht ahnlich wie vorher //

2.1.11 Definition

Fur Mengen A,B bezeichne BA die Menge der Abbildung A→ B


Lineare Algebra I


Vorlesung 8


Michael Habermann

[email protected]

2.1.12 Korollar (”Folgerung”)

Seien A,B endlich. so ist BA endlich und

|BA| = |B||A|

Bsp.: |1, 2, 31,2| = 32 = 9

Beweis: oBdA A 6= ∅√

Sei |A| = n > 0

oBdA A = 1, 2, ..., n. (A ≃ A′ ⇒ BA ≃ BA′

)

Dann BA = B × ...×B︸︷︷︸

n−mal

Satz 2 ⇒ |BA| = |B|n = |B||A|

2.1.13 Korollar

(Potenzmenge in A ¶(A) = 2A := B : B ⊆ A1B : A→ 0, 1) Sei A endlich. Dann ist 2A endlich und

|2A| = 2|A|

Beweis: Wir ordnen einer Teilmenge B ⊆ A ihre

Indikatorfunktion 1B : A→ 0, 1 zu, definiert durch

1B(x) := 1 falls x ∈ B; 0 sonst.

Umgekehrt ordnen wir einer Funktion f : A→ 0, 1 die Teilmenge

f−1(1) = x ∈ A : f(x) = 1 zu

Die Abbildungen

2A → 0, 1A, B 7→ 1B

und

0, 1A → 2A, f 7→ f−1(1)sind invers zueinander. (triviale Verifikation)

Folglich

2A ≃ 0, 1AKorollar 1 ⇒

|0, 1A| = 2|A|

⇒|2A| = |0, 1A| = 2|A| //

2.1.14 Bemerkung

A = 1, 2, ..., n, f ∈ 0, 1Af = (f1, ..., fn) ”Folge von n Bits”

2.1.15 Satz

Seien A,B endlich und f : A→ B


Lineare Algebra I


Vorlesung 8


Michael Habermann

[email protected]

(1) Ist f injektiv, so gilt |A| ≤ |B| f : N→ N, n 7→ n+ 1

gilt uberdies |A| = |B|, so ist f bijektiv.f injektiv, f nicht surjektiv

(2) Ist f surjektiv, so gilt |A| ≥ |B|gilt uberdies |A| = |B|, dann ist f bijektiv

Beweis: (1) Sei f : A→ B injektiv. Dann ist

A→ f(A), a 7→ f(a) bijektiv

Haben wir eine disjukte Zerlegung

B = f(A) ∪ (B \ f(A))

Satz 1 ⇒ |B| = |f(A)|+ |B \ f(A)| ≥ |f(A)| = |A|ist uberdies |A| = |B| ⇒ |B \ f(A)| = 0

⇒ B \ f(A) = ∅

⇒ f(A) = B ⇒ f surjektiv

(2) Sei f surjektiv. Sei oBdA B = 1, 2, ..., nBetrachte fur i ∈ Bf−1(i) := f−1(i) = a ∈ A : f(a) = i(heisst Faser von i). Nach Vorraussetzung gilt

∀i ∈ B f−1(i) 6= ∅ (f injektiv)

Es gilt A : f−1(1) ∪ f−1(2) ∪ ... ∪ f−1(n)

und f−1(i) ∩ f−1(j) = ∅ fur i 6= j

Satz 1 ⇒|A| =

n∑

i=1

|f−1(i)|︸︷︷︸

≥1

≥ n = |B|

Ist uberdies |A| = |B|, so folgt

∀i ∈ B |f−1(i)| = 1

D.h. f ist injektiv

2.2 Unendliche Mengen

2.2.1 Definition

Eine Menge heisst unendlich, wenn sie nicht endlich ist.

2.2.2 Bemerkung

N ist unendlich


Lineare Algebra I


Vorlesung 10


Michael Habermann

[email protected]

Mengen A,B

A ≤ B :⇔ ∃ϕ : A→ B injektiv

2.2.3 Satz (Schroder-Bernstein)

A ≤ B und B ≤ A ⇒ A ≃ B

Beweis: Sei ϕ : A→ B injektiv

Ψ : B → A injektiv

Schreibweise Ψϕ := Ψ ϕ fur Komposition

ϕn := ϕϕ · · · ϕ︸︷︷︸

n−mal

fur n ∈ N∗, ϕ = id

X := A \Ψ(B) Ureier A = EierΨ := B \ ϕ(A) Urhuhner B = Huhner

ϕ : aus Ei schlupft Huhn

Ψ : Huhn legt ein Ei

Definieren X ⊆ AX := (Ψϕ)n(x) : x ∈ X,n ∈ N Eier die von Ureier abstammen

BX := ϕ(Ψϕ)n(x) : x ∈ X,n ∈ N = ϕ(AX) Huhner, die von Ureiern abstammen

Y ⊆ BY := (ϕΨ)n(y) : y ∈ Y, n ∈ N Huhner, die von Ureier abstammen

AY := Ψ(ϕΨ)n(y) : y ∈ Y, n ∈ N = Ψ(BY ) Eier die von Urhuhner abstammen

1. Beh.: AX ∩AY = ∅

Beweis: Sonst ∃n,m ∈ N ∃x ∈ X , y ∈ Y(Ψϕ)n(x) = Ψ(ϕΨ)m(y) = (Ψϕ)mΨ(y)

(Ψϕ)n injektiv

1. Fall: n ≤ m (Ψϕ)n(x) = (Ψϕ)n(Ψϕ)m−nΨ(y)

Kann Kurzen, da (Ψϕ)m injektiv ⇒ x = (Ψϕ)m−nΨ(y) = Ψ(ϕΨ)m−n(y) ∈ Ψ(B)

Wiederspruch zu x ∈ A \Ψ(B)

Analog BX ∩BY = ∅ Definieren

A∞ := A \ (AX ∪AY )

B∞ := B \ (BX ∪BY )

Genugt zu zeigen: AX ≃ BX , AY ≃ BY , A∞ ≃ B∞

Nach Definition ist ϕ(AX) = BX , also ist

AX → BX , a 7→ ϕ(a) bijektiv, also AX ≃ BX

Analog AY ≃ BY

2. Beh.: ϕ(A∞) ⊆ B∞

Sei a ∈ A∞. Ware ϕ(a) /∈ B∞, dann

1. Fall: ϕ(a) ∈ BX , etwa ϕ(a) = ϕ(Ψϕ)n(x)

⇒ a = (ψϕ)n(x) ⇒ a ∈ AX 2. Fall: ϕ(a) ∈ BY , etwa ϕ(a) = (ϕΨ)n(y)


Lineare Algebra I


Vorlesung 10


Michael Habermann

[email protected]

Falls n = 0 ⇒ ϕ(a) = y Falls n > 0 ⇒ a = Ψ(ϕΨ)n−1(y) ⇒ a ∈ AY 2. Beh. gezeigt.

3. Beh.: B ⊆ ϕ(A∞)

Sei b ∈ B∞ Da b /∈ Y ⇒ ∃a ∈ A b = ϕ(a)

Ware a ∈ AX ⇒ b = ϕ(a) ∈ BX Ware a ∈ AY , etwa a = Ψ(ϕΨ)n(y) fur ein y ∈ Y⇒ b = ϕ(a) = (ϕΨ)n+1(y) ∈ BY ⇒ 3. Beh. gezeigt.

2+3 Beh. ⇒ ϕ(A∞) = B∞

Also ist A∞ → B∞, a 7→ ϕ(a) bijektiv,

Also A∞ ≃ B∞ //

2.2.4 Korrolar

Q ist abzahlbar unendlich

Beweis: ϕ : Q→ Z×N∗, q = ab7→ (a, b)

wobei Bruch ab

gekurzt.

Die Abbildung ϕ ist inkektiv ⇒ Q ≤ Z×N∗

Ferner Z ≃ N, N∗ ≃ N ⇒ Z×N∗ ≃ N×N ≃ N

⇒ Q ≤ N

Wegen N ⊆ Q ⇒ N ≤ Q

Schroder-Bernstein⇒ Q ≃ N //

2.2.5 Korrolar

R ≃ 2N

Beweis: Sei I = x ∈ R : 0 ≤ x < 1Jedes x ∈ I hat eine dyadische Darstellung (vergleiche Analysis)

x =∞∑

i=0

ai

2i+1 , ai ∈ 0, 1

Ist nicht eindeutig, da1

2m = 12m + 0

2m+1 + 02m+2 + ... = 1

2m+1 + 12m+2 + ...

Wenn man den rechten Fall ausschließst, so ist die dyadische Darstellung eindeutig.

Genauer, die Abbildung:

M := a ∈ 0, 1N : k ∈ N : ak00 ist unendlich → I

a = (ao, a1, a2, ...) 7→∞∑

k=0

ak

2k

ist bijektiv (Fur formalen Beweis siehe Analysis)

Also M ≃ I. Da M ⊆ 0, 1N ⇒M ≤ 2N

Wir haben aber auch 2N ≤M , da

0, 1N→M , (a0, a1, a2, ...)→ (a0, 0, a1, 0, a2, 0, ...)

inektiv ist. Also 2N ≤M


Lineare Algebra I


Vorlesung 10


Michael Habermann

[email protected]

Schroder-Bernstein⇒ I ≃M ≃ 2N

Die Abbildung f :]− 1, 1[→ R, f(x) = x1−x2 ist bijektiv. (vergleiche Analysis)

Also R ≃]− 1, 1[≃]0, 1[≤ IDa I ⊆ R ⇒ I ≤ R

⇒ R ≃ IInsgesamt: R ≃ I ≃ 2N //

2.2.6 Bemerkung

Man kann zeigen, dass fur belibige Mengen A, B stets

A ≤ B oder B ≤ A gilt.

3 Gruppen

3.1 Permutationen

3.1.1 Definition

Eine Permutation eine menge A ist eine bijektive Selbstabbildung

g : A→ A von A

Man bezeichnet die Menge der Permutationen um A = 1, 2, ..., n mit Sn.

3.1.2 Bemerkung:

|Sn| = n!

Schreibe fur die Komposition von Abbildungen g, h : A→ A

gh := g h (”zuerst h, dann g”)

Offenbar gilt fur alle g, h, k ∈ Sn:

(1) e := indA ∈ Sn

(2) g, h ∈ Sn ⇒ gh ∈ Sn

(3) g ∈ Sn ⇒ g−1 ∈ Sn

(4) (gh)k = g(hk) (Assoziativgesetz)

(5) ge = eg = g

(6) gg−1 = g−1g = e

3.1.3 Beispiel:

n = 5,

g =

(1 2 3 4 5

3 4 5 1 2

)

Permutationen 1 7→ 3, 2 7→ 5, 3 7→ 4, 4 7→ 1, 5 7→ 2

Sei h =

(1 2 3 4 5

1 3 5 2 4

)

Dann


Lineare Algebra I


Vorlesung 10


Michael Habermann

[email protected]

gh =

(1 2 3 4 5

3 4 2 5 1

)

, hg =

(1 2 3 4 5

5 4 2 1 3

)

Insbesondere gh 6= hg

g−1 =

(1 2 3 4 5

4 5 1 3 2

)

”Zyklen” ind spezielle Permutationen, z.B.

g1 =

(1 2 3 4 5

2 3 4 5 1

)

Schreibweise: g1 = (12345) = (23451)

heisst Zykel der Lange 5


Lineare Algebra I


Vorlesung 11


Michael Habermann

[email protected]

Sn = g : g : 1, 2, ..., n → 1, 2, ..., n bijektiv = Permutation um 1, 2, ..., n

gg−1 = g−1g = e := id, ge = eg = g

Zyklus g = (251346)

gemeint 2 7→ 5, 5 7→ 1, 1 7→ 3

3 7→ 4, 4 7→ 6, 6 7→ 2

3.1.4 Definition

Sei k ≥ 2 und a1, ..., ak ∈ 1, 2, ..., n paarweise verschieden

Definiere g ∈ Sn durch

g(b) :=

ai+1 falls b = a und i < k

a1 falls b = ak

b falls b /∈ a1, ..., akg heisst Zykel der Lange k. Bez:

g = (a1, a2, ..., ak)

Ein Zykel der Lange 2 heisst Transposition

3.1.5 Beispiel

n = 8 g = (235)(68)

g(1) = 1, g(2) = 3

(235) = (352) = (523)

3.1.6 Bemerkung

1. b heisst Fixpunkt um g, falls g(b) = b

2. a1, ..., ak = Menge der Nichtfixpukte um g = (a1, ..., ak)

3. (a1, ..., ak) = b1, ..., bl) ⇔ k = l und ∃i ≤ k (b1, ..., bk) = (ai, ..., ak, a1, ..., ai−1)

3.1.7 Definition

Zwei Zykel (a1, ..., ak) und (b1, ..., bl) heissen disjunkt, falls a1, ..., ak ∩ b1, ..., bl = ∅

3.1.8 Lemma

Disjunkte Zyklen kommulieren, d.h.

z1, z2 disjunkte Zyklen ⇒ z1z2 = z2z1

Beweis: Setzen zi := Nichtfixpunkte von ziFallunterscheidung

1. a /∈ z1, a ∈ z2: z1(z2(a)) = z1(a) = a = z2(z1(a))

2. a ∈ z1, a /∈ z2: z1(z2(a)) = z1(a), z2(z1(a)) = z1(a) da z1 ∩ z2 = ∅

3. a /∈ z1, a ∈ z2: analog


Lineare Algebra I


Vorlesung 11


Michael Habermann

[email protected]

4. a ∈ z1, a ∈ z2: unmoglich

3.1.9 Beispiel

n = 3 (12)(13) = (132)

(13)(12) = (123)

3.1.10 Satz

Jede Permutation g ∈ sn lasst sich als ein Produkt um paarweise disjunkten Zyklen schreiben,

und zwar bis auf die Reihenfolge auf genau eine Art.

(e = ”leere Produkt”)

Formaler Beweis folgt nachste Woche

3.1.11 Beispiel

g =

(1 2 3 4 5 6 7 8 9

3 1 5 8 2 7 6 4 9

)

= (1352)(48)(67)

3.1.12 Beispiel

|S3| = 3! = 6, S3 = e, (12), (13), (23), (123), (132)

3.1.13 Korollar

Jedes g ∈ Sn ist ein Produkt von Transpositionen

Beweis: G.z.z. Jeder Zykel ist Produkt von Transpositionen

Sei g = (a1, a2, ..., ak) ein Zykel

Behauptung: g = (a1a2)(a2a3)(a3a4) · · · (ak−1ak)

a1 7→ a2, a2 7→ a3, ..., ak−1 7→ ak

ak 7→ a1

3.1.14 Definition

Eine Nachbartransposition ist eine Transposition der Form (aa+ 1)

3.1.15 Korollar

Jede Permutation ist ein Produkt um Nachbartranspositionen

Beweis Als Ubung


Lineare Algebra I


Vorlesung 11


Michael Habermann

[email protected]

3.1.16 Definition

Sei g ∈ Sn Ein Fehlstand um g ist ein Paar (i, j) mit i < j und g(i) > g(j)

3.1.17 Beispiel

n = 5 g =

(1 2 3 4 5

2 4 5 1 3

)

Fehlstande: (1, 4), (2, 4), (2, 5), (3, 4), (3, 5)

3.1.18 Definition

Sei g ∈ Sn und α die Anzahl der Fehlstande

· g heisst gerade, falls α gerade is

· g heist ungerade, falls α ungerade ist.

Das Signum (oder auch Vorzeichen) von g ist definiert als

sgn(g) := (−1)α =

1 falls g gerade ist

−1 sonst

3.1.19 Beispiel

1. sgn(e) = 1 (α = 0)

2. sgn(aa+ 1) = −1 (α = 1)

3.1.20 Theorem

g, h ∈ S − n gilt

sgn(gh) = sgn(g) · sgn(h)

3.1.21 Korollar

sgn(ab) = −1

Beweis: Sei g ∈ Sn mit g(1) = a, g(2) = b (existiert)

Dann (ab) = g(12)g−1

(Verfikation: Fur k /∈ a, b ist g−1(k) /∈ 1, 2⇒ g(12)( g−1(k)

︸︷︷︸

Fixpunktvon12

= g(g−1(k)) = k

g(12)(g−1(a)) = g(2) = b Analog g(12)(g−1(b)) = g(1) = a )

gg−1 = eSatz⇒ sgn(g)sgn(g−1) = sgn(e) = 1

⇒ sgn(g−1) = 1sgn(g) = sgn(g)

Satz ⇒ sgn(ab) = sgn(g(12)g−1)

= sgn(g) sgn(12)︸︷︷︸

=−1

sgn(g−1)

= −sgn(g) · sgn(g−1) = −(sgn(g))2 = −1 //


Lineare Algebra I


Vorlesung 11


Michael Habermann

[email protected]

3.1.22 Korollar

sgn(a1...ak) = (−1)k−1, d.h. Zyklen ungerader Lange sind gerade,

Zyklen gerade Lange sind ungerade.

Beweis: Wissen (a1...ak) = (a1a2)(a2a3)...(ak−1ak)

Satz ⇒ sgn(a1...ak) = (−1)k−1 //

3.1.23 Beispiel

n = 12

g = 1 2 3 4 5 6 7 8 9 10 11 12

8 1 5 2 7 109 4 1 6 3 12 sgn(g) = ?

g = (1 8 4 2)(3 5 7 9 11)(6 10)

sgn(g) = (−1) · (+1)(− 1) = +1

g ist gerade


Lineare Algebra I


Vorlesung 12


Michael Habermann

[email protected]

3.1.24 Satz

Fur g, h ∈ Sn gilt sgn(gh) = sgn(g) · sgn(h)

Beweis: (1) h = (a a+ 1) Betrachte

φ : (i, j) : (i, j) Fehlstand um g (i, j) 6= (a a+ 1) → (i, j) : (i, j)

Fehlstand um gh (i, j) 6= (a a+ 1)definiert durch

φ((i, , j)) := (i, j) falls i, j ∩ a, a+ 1 = ∅

φ((i, a)) := (i, a+ 1)

φ((i, a+ 1)) := (i, a)

φ((a, j)) := (a+ 1, j)

φ((a + 1, j) := (a, j)

Man pruft nach ·φ wohldefiniert

·φ bijektiv

Sei α die Anzahl der Fehlstande in g

Sei β die Anzahl der Fehlstande in gh

Dann β

α+ 1 falls g(a) < g(a+ 1)

α− 1 falls g(a) > g(a+ 1)

Also sgn(gh) = (−1)β = (−1)α±1 = −(−1)α

= −sgn(g) = sgn(g) · sgn(h)

(2) Sei nun h = t1 · t2 · ... · tq, wobei

ti Nachbartransposition (existiert nach Korollar)

⇒ sgn(h) = sgn((t1...tq−1)tq)(1)= −sgn(t1...tq−1)

Induktion nach q ⇒ sgn(t1 · · · tq) = (−1)q

Analog sei g = t1 · t2 · · · tq, ti Nachbartransposition

⇒ sgn(g) = (−1)p

Ferner gh = t2 · · · tqt1 · · · tqsgn(gh) = (−1)p+q = (−1)p · (−1)q = sgn(g) · sgn(h) //

3.2 Gruppen und Untergruppen

Sei A eine Menge. Eine r-stellige Operation in A ist eine Abbildung ω : Ar → A (r ∈ N)

Wichtig sind: · 2-stellige (oder binare Operationen)

ω : A×A→ A

gewohnlich schreibt man statt ω(a, b)

aωb. z.B. a+ b, a · b, a ∪ b· 1-stellige Operationen: ωA→ A


Lineare Algebra I


Vorlesung 12


Michael Habermann

[email protected]

3.2.1 Definition

Eine Gruppe ist eine Menge G zusammen mit einer 2-stelliugen Operation

G×G→ G, (g, h) 7→ g · h (Multiplikation)

mit einem ausgezeichneten Element

e ∈ G (Neutralelement)

und einer 1-stelligen Operation

G→ G, g 7→ g−1 (Iversion)

so dass folgende Axiome erfullt sind:

(1) ßforallg, h, k ∈ G (g · h) · k = g · (h · k) (Assoziativitat)

(2) ∀g ∈ G g · e = e · g = g

(3) ∀g ∈ G g · g−1 = g−1 · g = e

Die Gruppe heisst abelsch (oder kommutativ), wenn gilt

(4) ∀g, h ∈ G g · h = h · g

3.2.2 Bemerkung

· Die Gruppe wird meistens mit G bezeichnet

· Meist lasst man Multiplikationenspunkt weg und schreibt

(g, h) 7→ gh

· Bei abelschen Gruppen schreibt man meist

(a, b) 7→ a+ b (mit Inversen −a und Neutralelement 0)

3.2.3 Beispiel

(1) G = sn

gh = Komposition von g, h

e = identische Abbildung

g−1 = inverse Abbildung

Sn heisst symmetrische Gruppe (auf n Symbolen)

Sn ist nicht abelsche Gruppe falls n ≥ 3

(12)(13) 6= (13)(12)

(2) G = Z

Multiplikation: Addition ganzer Zahlen

e = 0

Inversen: n 7→ −nG bildet eine abelsche Gruppe: Die additive Gruppe der ganzen Zahlen

(3) G = Q, (g, h) 7→ g + h

e = 0

g 7→ −g


Lineare Algebra I


Vorlesung 12


Michael Habermann

[email protected]

⇒ abelsche Gruppe. additive Gruppe der rationalen Zahlen Q

(4) G = Q× := Q \ 0 bildet abelsche Gruppe

(g, h) 7→ gh multiplikative Gruppe

g 7→ g−1 der rationalen Zahlen Q×

e = 1

(5) Additive Gruppe von R

Multiplikative Gruppe R× := R \ 0

(6) G = 1,−1(g, h) 7→ gh

e = 1

g 7→ g−1 = g

⇒ bildet Gruppe

3.2.4 Bemerkung

(1) Sei f ∈ G. Dann

f = e ⇔ ∃g ∈ G gf = g

Beweis: ”⇒” klar ”⇐” ⇒f

(2)= ef

(3)= (g−1g)f

(1)= g−1(gf) = g−1g

(3)= e

Also f = e //

(2) Seien g, h ∈ G. Dann

h = g−1 ⇔ hg = e (⇔ gh = e)

Beweis: ”⇒” klar ”⇐” Sei hg = e

h = he = h(gg−1) = (hg)g−1 = eg−1 = g−1

Also h = g−1 //

(3) (e−1)−1 = e

(4) (g−1)−1 = g

3.2.5 Folgerung

Zwei Gruppen, die in Mengen und Multiplikation ubereinstimmen, sind gleich.

3.2.6 Definition

Sei G eine Gruppe. Eine Untergruppe von G ist eine Teilmenge H ⊆ G mit

(1) ∀g, h (g, h ∈ H ⇒ gh ∈ H)

(2) e ∈ H(3) ∀g (g ∈ H ⇒ g−1 ∈ H)


Lineare Algebra I


Vorlesung 12


Michael Habermann

[email protected]

3.2.7 Bemerkung

(1) H ist dann in naturlicher Weise eine Gruppe

- Multiplikation von H ist die Einschiebung der Multiplikation in G auf H ×HH ×H → H , (g, h) 7→ g · h

Inversion H → H g 7→ g−1

Bezeichnung: H ≤ G fur H Untergruppe von G

(2) H ≤ G mit K ≤ H ⇒ K ≤ G

(3) H ≤ G und L ≤ G ⇒ H ∩ L ⇒ G

3.2.8 Beispiel

(1) e ≤ G, G ≤ Gechte Untergruppe H : H ≤ G, H /∈ e, G

(2) Untergruppen von S3 = e, (12), (13), (23), (123), (132)Echte Untergruppen sind: e, (12), e, (13), e, (23)

e, (123), (132) Verifiziere!

Behauptung: Das sind alle echte Untergruppen von S4

(3) Definiere An := g ∈ Sn : sgn(g) = 1Behauptung: An ≤ Sn

An heisst alternierende Gruppe

z.B. A3 = e, (123), (132)Beweis:

· g, h ∈ An ⇒ gh ∈ An : sgn(gh) = sgn(g)sgn(h) = 1 · 1 = 1


Lineare Algebra I


Vorlesung 13


Michael Habermann

[email protected]

Wiederholung:

Gruppe G

G×G→ G(g, h) 7→ gh

e ∈ GG→ G, g 7→ g−1

Axiome:

Bsp.: (1) G = S1 symetrische Gruppe

(2) Z,Q,R Gruppen (Operation Addition)

(3) Q× = Q \ 0, R× = R \ 0 Gruppen (Operation = Multiplikation)

Produkte mit vielen Faktoren:

Sei G eine Gruppe, g1, · · · , gt ∈ GMan definiert induktiv

g1g2 · · · gt := g1(g2 · · · gt) fur t ≥ 2

z.B. g1g2g3g4 := g1(g2(g3g4))

Verallgemeinerte Assoziativitat fur 1 ≤ s < t gilt

(g1 · · · gs)(gs+1 · · · gt) = g1 · · · gt

Beweis: Induktion nach s. Start s = 1: Klar nach Def.

Schritt s ≥ 2: (g1 · · · gs)(gs+1 · · · gt)Def= (g1(g2 · · · gs))(gs+1 · · · gt)

Assoz.= g1((g2 · · · gs)(gs+1 · · · gt))

Induvor= g1(g2 · · · gt)

Def= g1 · · · gt //

G Gruppe, Untergruppe H ≤ GH ⊆ G mit

· ∀g, h ∈ H gh ∈ H· e ∈ H· ∀g ∈ H g−1 ∈ H⇒ H ist in naturlicher Weise eine Gruppe

Bsp.: · Z ≤ Q, Q ≤ R

· −1, 1 ≤ Q×, Q× ≤ R×

· An := g ∈ Sn : sgn(g) = 1 ≤ Sn alternierende Gruppe

(Z,+)

Intermezzo: Division mit Rest

3.2.9 Satz

Seien a,m ∈ Z, m ≥ 1. Dann gibt es eindeutig bestimmte q ∈ Z, r ∈ 0, 1, ...,m− 1 und

a = qm+ r

r heisst der Rest von a bezuglich m

Bez.: a mod m := r


Lineare Algebra I


Vorlesung 13


Michael Habermann

[email protected]

Beispiel: a = 365, m = 7

365/7 = 52

Divisionsalgorithmus aus der Schule

365 = 52 · 7 + 1 ⇒ 365 mod 7 = 1

Beweis: Existenz: Sei q ∈ Z minimal mit a < (q + 1)m

⇒ qm ≤ a. Setze r := a− qm⇒ 0 ≤ r < m und a = qm+ r

Eindeutigkeit: Sei a = q, m+ r1 = q2m+ r2, ri ∈ 0, 1, ...,m− 1oBdA q2 ≥ q1⇒ 0 ≤ (q2 − q1)m = r1 − r2 ≤ r1 < m

⇒ q2 − q = 0 ⇒ q2 = q1 ⇒ r2 = r1 //

3.2.10 Beispiel

Sei m ∈ Z. Definiere

Hm := a ∈ Z : ∃b ∈ Z a = bm= a : a Vielfaches von m

Dann Hm ≤ Z (trivial)

z.B. H0 = 0, H1 = Z, H2 = ...,−4,−2, 0, 2, 4, ...· Fur m ∈ N∗ ist Hm = H−m unendlich

· Fur m,n ∈ N∗, m 6= n ⇒ Hm 6= Hn

3.2.11 Satz

Jede Untergruppe von Z ist von der Form Hm fur ein m ∈ N

Beweis: Sei H ≤ Z, H 6= 0Sei m := minn ∈ N∗ : n ∈ H⇒ m ∈ HEs gilt Hm ⊆ H (Verwende, dass H ≤ Z)

Umgekehrt sei a ∈ H oBdA a > 0

Division mit Rest ∃q, r ∈ Z

a = qm+ r 0 ≤ r < m

m ∈ ⇒ qm ∈ Ha ∈ H⇒ r = a− qm ∈ H

= a+ (−qm)

Minimalitat von m ⇒ r = 0 Also a = qm ⇒ a ∈ Hm

Haben gezeigt H ⊆ Hm. Es golt H = Hm //

3.2.12 Definition

Sei G eine Gruppe, H ≤ G, g ∈ G


Lineare Algebra I


Vorlesung 13


Michael Habermann

[email protected]

Die Menge gH := gh : h ∈ H heißt linke Nebenklasse von H bzgl. g (in G)

Analog heißt die Menge Hg := hg : h ∈ H rechte Nebenklasse von H bzgl. g (in G)

3.2.13 Bemerkung

H ist linke und rechte Nebenklasse von H

eH = H = He

Bsp.: G = S3, H = e, (12)eH = H , (12)H = H , (13)H = (13), (13)(12) = (13), (123)(23)H = (23), (132),(123)H = (123), (13), (132)H = (132), (23)Haben drei verschiedenen Linksnebenklassen von H in S3

e, (12) = H, (13), 123), (23), (132)Diese bilden eine Partition von S3 in Teilmengen gleicher Große

3.2.14 Lemma

Sei H ≤ G, a, b ∈ G. Dann aH = bH ⇔ b−1a ∈ H

Beweis: ”⇒” aH = bH ⇒ a = ae ∈ aH = bH

⇒ ∃h ∈ H a = bh

⇒ b−1a = b−1bh = eh = h ∈ H”⇔” Sei b−1a ∈ H Sei h ∈ H

ah = b(b−1a)h ∈ bHEs fehlt aH ≤ bH . Analog bH ⊆ aH //

3.2.15 Beispiel

(1) G = Sn, H = An, g ∈ Sn Dann

gAn =

An falls g ∈ An

Sn \An sonst

(2) Nebenklassen von Hm in Z) !WICHTIG!

G = Z, H = Hm, NK vom Hm = a+Hm fur a ∈ Z

Lemma: a+Hm = b+Hm ⇔ (−b) + a = a− b ∈ Hm

⇔ m teilt a− b

m = 0 Die NK von H0 = 0 sind a fur a ∈ Z

m > 0 (i) Die NK von Hm sind a+Hm fur 0 ≤ a < m

(ii) Gilt a+Hm 6= b+Hm fur 0 ≤ a < b < m

Beweis: (i) Gegben a ∈ Z Schreibe a = qm+ r, 0 ≤ r < m

Dann a− r ∈ Hm ⇒ a+Hm = r +Hm

(ii) Ware a ∈ b+Hm ⇒ b− a ∈ Hm ⇒ m teilt b − a


Lineare Algebra I


Vorlesung 13


Michael Habermann

[email protected]

Widerspruch zu 0 ≤ b− a < m //

3.2.16 Satz

Sei H ≤ G. Die Menge gh : g ∈ Gder linken Nebenklassen von H ist eine Partition von G in gleichmachtige Teile.

Analog fur rechte Nebenklassen

Die Menge Hg : g ∈ G der rechten Nebenklassen ist gleichmachtig

zur Menge gH : g ∈ G der linken Nebenklassen

Bsp.: G = S3, H = e, (12)Linke NK: H, (13), (123), (23)(132)Rechte NK : H, 13), (132), (23)(123)|G| = q|H |, q = (G : H) heisst Index von H in G

Interessant: |H | teilt |G|


Lineare Algebra I


Vorlesung 14


Michael Habermann

[email protected]

Wiederholung: G Gruppe, H ≤ G Untergruppe,

fur g ∈ G heißt gH = gh : h ∈ H heißt linke Nebenklasse (analog rechte NK Hg)

3.2.17 Satz

Sei H ≤ G. Die Menge

gH : g ∈ G aller linken Nebenklassen ist eine Partition von G

in gleichmachtige Teilmengen. Analog fur rechte Nebenklassen.

Ferner ist die Menge der rechten Nebenklassen gleichmachtig zu der Menge

der linken Nebenklassen.

Beweis: (i) ∀g ∈ G : gH 6= ∅, da g = ge ∈ gH

(ii) zu zeigen: linke Nebenklassen sind paarweise disjunkt

Seien a, b ∈ G mit aH ∩ bH 6= ∅

Dann existiert c ∈ aH ∩ bH , d.h. ∃h1, h2 ∈ H : c = ah1 = bh2

⇒ b−1a = h2h−11 ∈ H Lemma

= aH = bH

(iii) zu zeigen: linke Nebenklassen uberdecken G, d.h. G =⋃

g∈G gH

Da ”⊇” klar ist, zeigen wir ”⊆”:

Sei g ∈ G. Dann ist g ∈ gH ⊆⋃

g∈G gH

(iv) zu zeigen: Linke Nebenklassen sind gleichmachtig

Seien a, b ∈ G. Definiere ϕ : aH → bH , ah 7→ bh.

ϕ ist wohldefiniert, da c = ah = ah′ mit h, h′ ∈ Ha−1

⇒ h = h′

ϕ ist bijektiv, da ψ : bH → aH , bh 7→ ah

invers zu ϕ, d.h. ϕ ψ = id, ψ ϕ = id

(v) zu zeigen: Die Menge der rechten Nebenklassen ist gleichmachtig zu der Menge

der linken Nebenklassen.

Definiere ϕ : aH : a ∈ G → Hb : b ∈ GaH 7→ Ha−1

ψ : Hb : b ∈ G → aH : a ∈ GHb 7→ b−1H

Dann gilt ϕ ψ = id, ψ ϕ = id, also ϕ bijektiv

[ϕ ψ(Hb) = ϕ(b−1H = H(b−1)−1 = Hb] //

3.2.18 Definition

Eine Gruppe G heißt endlich, falls G als Menge endlich ist.

Man nennt |G| die Ordnung von G.

Sei G endliche Gruppe, H ≤ G. Dann heißt

(G : H) := |gH : g ∈ G| = |Hb : b ∈ G|


Lineare Algebra I


Vorlesung 14


Michael Habermann

[email protected]

der Index von H in G.

Bez.: Seien m,n ∈ Z Schreibe m|n ⇔ ∃k ∈ Z : n = km

und sagen ”m teilt n”

3.2.19 Satz (Lagrange)

Sei G endliche Gruppe, H ≤ GDann gilt |G| = (G : H) · |H |Insbesondere teilt |H | die Ordnung |G|

Beweis: Sei k := (G : H), g1H, ..., gkH alle linken Nebenklassen von H

Satz ⇒ G = g1H ∪ ... ∪ gkH disjunkte Vereinigung, ∀i : |giH | = |H |

Also: |G| =k∑

i=1

|giH | =k∑

i=1

|H | = k · |H |

3.2.20 Beispiel

(1) Sei m ∈ N, n ≥ 2 Betrachte An ≤ Sn

Linke Nebenklassen von An sind An, Sn \An = (12)An

(fruheres Beispiel)

⇒ (Sn : An) = 2Lagrange⇒ |An| = 1

2 |Sn| = n!2

(2) Alle echten Untergruppen von S3:

Sei HleqS3.Lagrange⇒ |H |||S3| = 6

⇒ |H | ∈ 1, 2, 3, 6 H echte Untergruppe ⇒ |H | ∈ 2, 31. Fall: H enthalt Transoposition t.

⇒ e, t ≤ H Lagrange⇒ 2||H | ⇒ |H | = 2

e, t = H

2. Fall: H enthalt keine Transposition

Da S3 nur e, Transposition und 3-er Zykel enthalt,

muss H einen 3er-Zykel enthalten: z ∈ He, z, z2 ≤ H Lagrange⇒ 3||H | ⇒ |H | = 3⇒ H = e, z, z2die echten Untergruppen von S3 sind also

e, (12), e, (13), e, (23), e, (123), 132)

Erzeugung:

Sei G Gruppe, M ⊆ G Teilmenge

Betrachte H := H : H ≤ G,M ⊆ H [G ∈ H]

3.2.21 Lemma

Es existiert genau ein H0 ⊆ H ,

d.h. H0 ist die kleinste Untergrupper von G, die M enthalt.


Lineare Algebra I


Vorlesung 14


Michael Habermann

[email protected]

Beweis: existenz: Definiere H0 :=⋂

H∈HH

Dann M ⊆ H0 und H0 ≤ G [prufe!]

⇒ H0 ∈ H. Außerdem: ∀H ∈ H: H0 =⋂

H∈HH ⊆ H ⇒ (∗)Eindeutigkeit: Seien H0, H1 ∈ H mit (∗)

⇒ H0 ⊆ H1, H1 ⊆ H0 ⇒ H0 = H1 //

3.2.22 Definition

Das H0 aus dem Lemma heißt die von M erzeugte Untergruppe von G

Wir schreiben: H0 =< M >

Falls M = g1, ..., gk, dann < g1, ..., gk >=< g1, ..., gk >

3.2.23 Proposition

Sei M ⊆ G. Dann gilt

< M >= g1gn : n ∈ N, ∀i : gi ∈M oder g−1i ∈M

Betrachte: Fur n = 0 ist das ”leere Produkt” = e

Beweis: Sei H1 die rechte Seite

Leicht: H1 ≤ G. Klar: M ⊆ H1 ⇒ H1 ∈ Hzu zeigen: Minimalitat, d.h. (∗)Sei H ∈ H, d.h. H ≤ G, M ⊆ H . Zu zeigen H1 ⊆ HSei g = g1 · · · gn ∈ H1, d.h. ∀i : gi ∈M oder g−1

i ∈M⇒ ∀i : gi ∈ Hh oder g−1

i ∈ H︸︷︷︸

⇒gi∈H

⇒ g ∈ H

Also H1 ⊆ H .

Notation: G Gruppe, g ∈ G Fur n ∈ Z definere

gn :=

g · · · g︸︷︷︸

n−mal

, n > 0

1, n = 0

g−1 · · · g−1

︸︷︷︸

|n|−mal

, n < 0

Beweis: ∀m,n ∈ Z : gn · gm = gn+m (leicht zu prufen)

Korollar: < g >= gn : n ∈ Z

Beweis: Propositon ⇒ < g > = gǫ1 · · · gǫn

︸︷︷︸

gǫ1+...+ǫn

: n ∈ N, ǫi ∈ ±1

= gn : n ∈ Z //

3.2.24 Bemerkung

< g > ist abelsch: gn · gm = gn+m = gm+n = gm · gn


Lineare Algebra I


Vorlesung 14


Michael Habermann

[email protected]

3.2.25 Definition

G Gruppe

(1) Eine Teilmenge M ⊆ G erzeugt G

falls < M >= G

(2) G heißt endlich erzeugt, falls eine endliche Teilmenge M ⊆ Gexistiert, die G erzeugt.

(3) G heißt zyklisch, falls ein g ∈ G existiert, mit G =< g >

3.2.26 Definition

Seien G und H Gruppen. G und H heißen isomorph, falls eine Abbildung

ϕ : G→ H existiert mit

(i) ϕ(e) = e

(ii) ∀g, h ∈ G : ϕ(g · h) = ϕ(g) · ϕ(h)

(iii) ϕ bijektiv.


Lineare Algebra I


Vorlesung 15


Michael Habermann

[email protected]

· G Gruppe, M ⊆ G< M > von M erzeugte Untergruppe

· G endlich erzeugt: ∃M ⊆ G,

M endlich und G =< M >

· heisst zyklisch: ∃g ∈ GG =< g >=:< g >

Bsp.: (1) M = Nachbartranspositionen ⊆ Sn

M erzeugt Sn

(2) Z ist zyklisch: Z =< 1 >=< −1 >

(3) endliche Gruppen sind endlich erzeugt

(4) (Q,+) nicht endlich erzeugt

(5) (Q×, ·) nicht endlich erzeugt

(6) Sei g ∈ G. Dann ist < g > zyklisch

3.2.27 Korrolar

Eine endliche Gruppe von Primzahlordnung ist zyklisch.

3.2.28 Definition

G Gruppe, g ∈ G. Existiert m ∈ N∗ mit gm = e, so heißt

ord(g) := minn ∈ N∗ : gn = edie Ordnung von g. Andernfalls setzt man ord(g) :=∞

3.2.29 Beispiel

(1) G = (R,+), g ∈ R, g 6= 0 ⇒ ord(g) =∞[mg = 0, m ≥ 1 ⇒ g = 0]

(2) G = (R×, ·) ord(1) = 1, ord(−1) = 2

∀g ∈ R× \ 1,−1 ord(g) =∞(3) z ∈ Sn Zykel der Lange l ⇒ ord(z) = l

(4) G = S7 g = (12)(345) ord(g) = 2 · 3 = 6

h = (12)(3456)ord(h) = 4

3.2.30 Proposition

G Gruppe, g ∈ G(1) Ist ord(g) =∞, so sind die gj fur j ∈ Z paarweise verschieden,

insbesondere ist gj, j ∈ Z unendlich

(2) Ist ord(g) = m, so ist

< g >= e, g, g2, ..., gm−1, | < g > | = m

Beweis: (1) Sei gi = gj fur i < j


Lineare Algebra I


Vorlesung 15


Michael Habermann

[email protected]

⇒ gi = gj = gi+j−i = gigj−i

⇒ e = g−igi = g−igigj−i = gj−i

⇒ ord(g) <∞(2) H := e, g, g2, ..., gm−1Beh.: H ≤ G

(1) e ∈ H(2) g−i = eg−i = gmg−i = gm−i fur 1 ≤ i < m⇒ g−i ∈ H(3) 0 ≤ i, j < m Falls i+ j < m ⇒ gigj = gi+j ∈ H

Falls i+ j ≥ m ⇒ gigj = gi+j = gi+j−m ∈ Hda 0 ≤ i+ j −m < m

Es folgt < g >⊆ H und Da H ⊆< g >

⇒ < g >= H

Noch z.z.: gj fur o ≤ j < m sind paarweise verschieden

Sonst: gi = gj 0 ≤ i < j < m

e = g0 = g−igi = g−igj = gj−i, 1 ≤ j − i < m

Widerspruch zur Minimalitat von m.

3.2.31 Korrolar

Sei G endlich, g ∈ G. Dann

(1) ord(g) = | < g > | und ord(g) teilt |G|(2) g|G| = e

Beweis: (1) ord(g) = | < g > | wegen Proposition

Lagrange ⇒ | < g > | teilt |G|(2) Sei |G| = k · ord(g) ⇒ g|G| = gk·ord(g) = (gord(g))k = ek = e //

3.3 Homomorphismen

Sei g ∈ G, ord(g) =∞ (z.B. G = R, g = 7)

Dann habe Bijektion

ϕ : Z→< g >, j 7→ gj

Es gilt:

ϕ(i)ϕ(j) = gigj = gi+j = ϕ(i+ j)

fur alle i, j ∈ Z. Nenne ϕ Gruppenisomorphismus

3.3.1 Definition

Seien G,H Gruppen

(1) Eine Abbildung ϕ : G→ H heißt Gruppenhomomorphismus (oder Homomorphismus

oder noch kurzer Morphismus), falls

∀a, b ∈ G ϕ(a · b) = ϕ(a) · ϕ(b)

(2) Ein Morphismus ϕ heißt Isomorphismus (kurz Iso),


Lineare Algebra I


Vorlesung 15


Michael Habermann

[email protected]

falls ϕ bijektiv

(3) Zwei Gruppen G und H heißen isomorph, falls

∃ϕ ϕ : G→ H , ϕ Iso

Bez.: G ≃ H(4) Ein Isomorphismus ϕ : G→ G heißt Automorphismus

3.3.2 Lemma

Sei ϕ : G→ H ein Morphismus, dann

(1) ϕ(eG) = eH

(2) ∀a ∈ G ϕ(a−1) = ϕ(a)−1

Beweis: (1) eGeG = eG ⇒ ϕ(eG)ϕ(eG) = ϕ(eGeG) = ϕ(eG)

⇒ ϕ(eG) = e //

(2) aa−1 = e

⇒ ϕ(a)ϕ(a−1) = ϕ(aa−1) = ϕ(e) = e

⇒ ϕ(a)−1 = ϕ(a−1) //

3.3.3 Bemerkung

1) id : G→ G Automorphismus

2) H ≤ G, Inklusion H → G, g 7→ g ist Morphismus

3) ϕ : G→ H Morphismus und ψ : H → K Morphismus

⇒ ψ ϕ : G→ K ist Morphismus

4) ϕ : G→ H Iso ⇒ ϕ−1 : H → G Iso

5) G ≃ G, G ≃ H ⇒ H ≃ GG ≃ H , H ≃ K ⇒ H ≃ K

3.3.4 Beispiele

(1) Sei g ∈ G Dann ist

ϕ : Z→ G, j 7→ gj ein Morphismus

[ ϕ(j + k) = ϕ(j)ϕ(k), d.h.

gj+k = gj · gk ”Potenzgesetz”]

(2) Sei m ∈ Z Dann ist Z→ Z, a 7→ ma ein Morphismus

(3) sgn : Sn → −1, 1︸︷︷︸

Gruppe·

g 7→ sgn(g) ist Morphismus

sgn(gh) = sgn(g)sgn(h)

3.3.5 Bemerkung

ϕ : G→ H Morphismus

(1) F ≤ G ⇒ ϕ(F ) ≤ HBeweis:


Lineare Algebra I


Vorlesung 15


Michael Habermann

[email protected]

1) e = ϕ(e) ∈ ϕ(F )

2) a ∈ F ϕ(a)−1 = ϕ(a−1) ∈ ϕ(F ), da a−1 ∈ F3) a, b ∈ F ⇒ ab ∈ F Also ϕ(a)ϕ(b) = ϕ(ab) ∈ ϕ(F ) //

Insbesondere F = G

imϕ := ϕ(G) ≤ H(2) K ≤ H ⇒ ϕ−1(K)

︸︷︷︸

a∈G:ϕ(a)∈K

≤ G

Insbedonere kere = ϕ−1(e) = a ∈ G : ϕ(a) = e ≤ Gheißt Kern in ϕ


Lineare Algebra I


Vorlesung 16


Michael Habermann

[email protected]

Wiederholung:

Gruppen G,H

ϕ : G→ H heißt Morphismus, falls

∀g1, g2 ∈ G ϕ(g1 · g2) = ϕ(g1) · ϕ(g2)

ϕ Isomorphismus, falls ϕ bijektiv

Bsp.: (1) sgn : Sn → −1, 1 Morphismus

ker(sgn) = An ≤ Sn

(2) R>0 = a ∈ R : a > 0 ≤ R× mult. Gruppe

R additive Gruppe

Beh.: (R,+) und (R>0, ·) sind isomorph!

Suche ϕ : R→ R>0 bijektiv

∀a, b ∈ R ϕ(a+ b) = ϕ(a) · ϕ(b)

Nehmen ϕ(a) = 2a Exponentialfunktion

Es gilt 2a+b = 2a · 2b

Umkehrabbildung: ϕ−1 : R>0 → R, x 7→ log2x

log2(x · y) = log2x+ log2y

Allgemein: Sei ϕ : G→ H Morphismus

Dann

ker(ϕ) := g ∈ G : ϕ(g) = e Kern

im(ϕ) := ϕ(g) : g ∈ G Bild

3.3.6 Lemma

Sei ϕ : G→ H Morphismus. Dann

ϕ injektiv ⇔ ker(ϕ) = e

Beweis: ”⇒” klar

”⇐” Sei ker(ϕ) = eSei ϕ(a) = ϕ(b)

⇒ e = ϕ(a)ϕ(a)−1

= ϕ(b)ϕ(a)−1

= ϕ(b)ϕ(a−1)

= ϕ(ba−1)

⇒ ba−1 ∈ ker(ϕ)

⇒ ba−1 = e

⇒ b = a

Also ϕ injektiv //

3.3.7 Bemerkung

(1) ϕ : G→ H Morphismus ⇒ ∀n ∈ N, ai ∈ G ϕ(a1a2...an) = ϕ(a1)...ϕ(an)


Lineare Algebra I


Vorlesung 16


Michael Habermann

[email protected]

Insbedonere ϕ(an) = ϕ(a)n fur n ∈ Z, a ∈ G

(2) ”Gruppentheoretische Eigenschaften” einer Gruppe G bleiben bei Ubergang

zu einer ismorphen Gruppe erhalten.

Bsp.: z.B. G ≃ G′,

G abelsch ⇔ G′ abelsch

G zyklisch ⇔ G′ zyklisch

3.4 Faktorgruppen

Sei G abelsch,

H ≤ G ⇒∀g ∈ G gH = Hg

3.4.1 Satz

G abelsch, H ≤ G. Die Menge der Nebenklassen

G|H := gH : g ∈ Gist eine Gruppe bzgl. der Multiplikation

(aH, bH) 7→ abH ,

Neutralelement H und Inverses

aH 7→ a−1H

Weiterhin ist ϕ : G→ G|H , a 7→ aH

ein surjektiver Morphismus mit Kern H

Beweis: (1) Multiplikation wohldefiniert:

zu zeigen: aH = a1H und bH = b1H

⇒ abH = a1b1H

Erinnerung: aH = a1H ⇔ a−11 a ∈ H

Haben a−11 a ∈ H , b−1

1 b ∈ Hb−11 a−1

1 ab = a−11 ab−1

1 b ∈ Hzu zeigen ist:

b−11 a−1

1 ab = (a1b1)−1ab ∈ H

(2) Inverse wohldefiniert: analog

(3) Die Abbildung ϕ : G→ G|H , a 7→ aH erfullt

ϕ(ab) = ϕ(a) · ϕ(b) fur alle a, b ∈ G[abH = aH · bH ]

(4) ϕ surjektiv mit Kern H : surjektiv klar

a ∈ ker(ϕ) ⇔ ϕ(a) = H ⇔ a ∈ H

(5) G|H ist eine Gruppe a, b, c ∈ GAssoziativitat: (ϕ(a)ϕ(b))ϕ(c) = ϕ(ab)ϕ(c)


Lineare Algebra I


Vorlesung 16


Michael Habermann

[email protected]

= ϕ((ab)c) = ϕ(a(bc)) = ϕ(a)ϕ(bc)

= ϕ(a)(ϕ(b)ϕ(c))

Neutralelement: ϕ(a)ϕ(e) = ϕ(ae) = ϕ(a) = ϕ(ea) = ϕ(e)ϕ(a)

ϕ(e) = H

Inverse wohldefiniert: analog

G|H heisst Faktorgruppe von G nach H ,

ϕ : G→ G|H heisst kanonischer Morphismus

3.4.2 Bemerkung

(1) Da G als abelsch vorrausgesetzt wurde, verwende in der Regel die additive Schreibweise

G|H = g +H : g ∈ Gϕ : G→ G|H , g 7→ g +H

(2) 0 ≤ GG|0 = g + 0 : g ∈ G = g : g ∈ Gϕ : G→ G|0, g 7→ g Isomorphismus

(3) G|G = G, ϕ : G→ G|G, g 7→ G

3.4.3 Beispiel

!!! WICHTIG !!!

G = Z, H = Hm =< m >= Vielfaches von mWissen bereits Z|Hm

= a+ < m >: 0 ≤ a < mZ|Hm

ist eine Partition von Z in gleichmaaßige Teile

m = 5 Z|<5> = < 5 >, 1+ < 5 >, 2+ < 5 >, 3+ < 5 >, 4+ < 5 >Die Nebenklasse a+ < m > wird eindeutig reprasentiert durch a ∈ N mit a < m

Wie wird in der Faktorgruppe Z|<m> gerechnet?

Neutralelement: < m >

Inverses: −(a+ < m >) = −a+ < m >= m− a+ < m >

Addition: (a+ < m >) + (b+ < m >)

= a+ b+ < m >

= (a+ b−m)+ < m >

Z|<m> heißt Restklassengruppe modulo m

Wir setzen Zm := 0, 1, 2, ...,m− 1 und identifizieren die Restklassengruppe Z|<m>

mit Zm via der Bijektion

: Zm → Z|<m>, a 7→ a+ < m >

Definiere eine Gruppe auf Zm, so dass ein Gruppenisomorphismus wird.


Lineare Algebra I


Vorlesung 16


Michael Habermann

[email protected]

Konkret: a+ b :=

a+ b falls a+ b < m

a+ b−m falls a+ b ≥ m−a := m− a0 := 0

Bsp.: Z5 = 0, 1, 2, 3, 43 + 4 = 2

2 + 2 = 4

−3 = 2

4 + 4 = 8 in Z, 8 = 1 · 5 + 3

4 + 4 = 3 in Z5

Additionstabelle fur Z5

0 1 2 3 4

0 0 1 2 3 4

1 1 2 3 4 0

2 2 3 4 0 1

3 3 4 0 1 2

4 4 0 1 2 3

Die Abbidlung Z→ Zm

a 7→ a mod m

ist ein surjektiver Morphismus mit Ker < m >

Bei uns bezeichnet a mod m den Rest von a

bei Division durch m ≥ 1

a = qm+ r, 0 ≤ r < m

a mod m := r


Lineare Algebra I


Vorlesung 17


Michael Habermann

[email protected]

Meine ”Lieblingssatze” in Lineare Algebra I

Cantor, Schroder-Bernstein, Signum ist Gruppenhomomorphismus (sgn(gh) = sgn(g) sgn(h)

Satz von Lagrange,

4 Ringe und Korper

4.1 Ringe

4.1.1 Definition

Ein Monoid (oder Halbgruppe) ist eine Menge S zusammen mit einer

binaren Operation

S × S → S, (a, b) 7→ ab (Multiplikation)

und einem ausgezeichnetem Element e ∈ S so dass gilt

(1) ∀a, b, c ∈ S (ab)c = a(bc)

(2) ∀a ∈ S ae = ea = a

S heisst Kommutativ, falls ∀a, b ∈ S ab = ba

4.1.2 Bemerkung

· Neutralelement ist durch Multiplikation eindeutig bestimmt

· Definiere wie bei Gruppen a1 a2 ... an

Dann (a1 · · ·an)(b1 · · · bn) = a1 · · · anb1 · bn

4.1.3 Definition

H heisst Unterring von S, falls H ⊆ S, e ∈ H ,

∀a, b ∈ H ab ∈ H

4.1.4 Bemerkung

H ist in naturlicher Weise ein Monoid

4.1.5 Definition

Seien S, S′ Monoide. Ein Morphismus von S nach S′ ist eine Abbildung

ϕ : S → S′ mit ∀a, b ∈ § ϕ(ab) = ϕ(a)ϕ(b)

und ϕ(e) = e

4.1.6 Beispiel

(1) Jede Gruppe ist ein Monoid

(2) Sei M Menge, S := MM : f : f : M →M Abb.


Lineare Algebra I


Vorlesung 17


Michael Habermann

[email protected]

Multiplikation = Komposition, Neutralelement = idM

Dann ist S ein Monoid

S ist keine Gruppe (strenggenommen: nicht zu Gruppe erweiterbar,

da nicht alle f bijektiv sind)

(3) (N,+, 0) ist Monoid, aber keine Gruppe

(4) (N, ·, 1) ist Monoid, aber keine Gruppe

(5) Bei der Definition von Morphismus darf ϕ(e) = e nicht weggelassen werde.

Bsp.: ϕ : N→ N, a 7→ 0

erfullt ϕ(ab) = ϕ(a)ϕ(b), aber ϕ(1) = 0 6= 1

(6) Wichtiges Beispiel: Sei X Menge, z.B. X = a, b, ..., zeine endliche Folge aus X ist ein n-Tupel

(x1, ..., xn), n ∈ N, xi ∈ X (Fur n = 0 haben ”leeres Wort” ∅)

Multiplikation: (x1, ..., xn)(y1, ..., ym) := (x1, ...xn, y1, ..., ym)

Konkatenation

Neutralelement ∅: S ist ein Monoid

nicht kommutativ: stammbaum 6= baumstamm

Sprachweise: X Alphabet. Wort aus X := endliche Folge aus X

S Monoid der Worte aus X

4.1.7 Definition

Ein Ring ist eine Menge A mit zwei binaren Operationen +, ·zwei ausgezeichneten Elementen 0, 1

einer einstelligen Operation − so dass gilt:

(1) (A,+, 0,−) ist abelsche Gruppe

(2) (A, ·, 1) ist Monoid

(3) ∀a, b, c ∈ A a(b + c) = ab+ ac

(b + c)a = ba+ ca

(Distributivgesetze)

A heisst kommutativ, wenn (A, ·, 1) kommutativ Monoid ist, d.h.

∀a, b ∈ A ab = ba

4.1.8 Bemerkung

(1) (A,+, 0,−) heisst additive Gruppe von A

(A, ·, 1) heisst multiplikatives Monoid von A

(2) Es gelten verallgemeinterte Distributivgesetze

a(b1 + ...+ bn) = ab1 + ...+ abn(b1 + ...+ bn)a = b1a+ ...+ bna


Lineare Algebra I


Vorlesung 17


Michael Habermann

[email protected]

(3) ∀a ∈ A a · 0 = 0 · aBeweis: a · 0 = a · (0 + 0) = a · 0 + a · 0

0 = a0 + (−a0) = a0 + a0 + (−a0) = a0

Analog 0a = 0

(4) ∀a, b ∈ A a · (−b) = (−a)b = −(ab)

Beweis: 0 = 0b = (a+ (−a)) · b = ab+ (−a)b⇒ −(ab) = (−a)bAnalog: a(−b) = −(ab)

(5) Man definiert die Subtraktion:

a− b := a+ (−b)Dann gilt: (a− b)c = ac− bc, c(a− b) = ca− cb

4.1.9 Definition

(i) Sei A Ring, B ⊆ AB heisst Unterring, falls B Untergruppe von (A,+, 0,−) und

B Untergruppe von (A, ·, 1).

D.h. · ∀a, b ∈ B a+ b, ab ∈ B· 0, 1 ∈ B· ∀a ∈ B −a ∈ B

B ist dann in naturlicher Weise ein Ring.

(ii) Seien A, C Ringe. Ein Ringmorphismus von A nach C

ist eine Abbildung ϕ : A→ C so dass ϕ Morphismus fur die additiven Gruppen

und multiplikativen Monoide wird d.h.

∀a, b ∈ A

ϕ(a+ b) = ϕ(a) + ϕ(b)

ϕ(ab) = ϕ(a)ϕ(b)//ϕ(1) = 1

4.1.10 Beispiel

Z kommutativer Ring

Q kommutativer Ring

R kommutativer Ring

Inklusion Z → Q Ringmorphismus

Z ⊆ Q

Q ≤ R Unterringe

Erinnerung an Faktorgruppen und Restlassengruppen

Gruppe Z, Untergruppe < m >≤ Z

Restklassengruppe Z|<m> = a+ < m >: a ∈ ZOperation: (a+ < m >) + (b+ < m >) := (a+ b)+ < m >

Z→ Z|<m> surjektiver Gruppenmorphismus mit Ker < m >. |Z|<m>| = m

a 7→ a+ < m >


Lineare Algebra I


Vorlesung 17


Michael Habermann

[email protected]

Zm := 0, 1, 2, ...,m− 1; Zmbijektiv→ Z|<m> definiere Addition auf Zm,

so dass α Gruppenisomorphismus wird.

a 7→ a+ < m >

Z5 = 0, 1, 2, 3, 42 + 2 = 4, 2 + 3 = 0

3 + 3 = 1, −2 = 3

Neu 2 · 2 = 4, 2 · 3 = 1

3 · 3 = 4 = −1

4.1.11 Satz

Sei m ∈ N, m ≥ 2 Die Menge Zm = 0, 1, ...,m− 1 mit der additiven Strucktur

(a, b) 7→ (a+ b) mod m

a 7→ (−a) mod mund der multiplikativen Strucktur

(a, b) 7→ (ab) mod m

ist ein kommutativer Ring. Die Abbildung ρ : Z→ Zm, a 7→ a mod m

ist ein surjektiver Ringmorphismus mit Ker < m >

Beweis: Aussage ist bezuglich der additiven Strucktur bereits bekannt

(i) (Zm, ·, 1) ist kommutativer Monoid

zeige: a mod m = a1 mod m

b mod m = b1 mod m

⇒ (ab) mod m = (a1b1) mod m

[Sei a− a1 = km, b− b1 = lm ⇒ab− a1b1 = ab− a1b + a1b− a1b1

= (a− a1)b + a1(b− b1)= kmb+ a1lm = (kb+ a1l)m]

Es folgt ∀a, b ∈ Z ρ(ab) = ρ(a)ρ(b)

ρ(1) = 1 ist klar

ρ erfullt die Eigenschaft eines Ringmorphismus

4.1.12 Bemerkung

(a+ b) mod m =

a+ b falls a+ b ≤ ma+ b−m sonst

(−a) mod m =

0 falls a = 0

m− a sonst


Lineare Algebra I


Vorlesung 18


Michael Habermann

[email protected]

Ring A

(A,+, ,−) abelsche Gruppe

(A, ·, 1) multi. Monoid

⇒ Distributizgesetz

z.B. Z, Q, R

Zm = 0, 1, ...,m− 1 m ∈ N, m ≥ 2

a+ b := (a+ b) mod m fur a, b ∈ Zm

a · b := (a · b) mod m 0 = 0

−a := (−a) mod m 1 = 1

Beh.: · Zm ist ein kommutativer Ring bzgl. +, ·· ρ : Z→ Zm, a 7→ a mod m ist surektiver Ringmorphismus

Beweis: Weiss ∀a, b ∈ Z ρ(a+ b) = ρ(a) + ρ(b)

Beh.: ∀a, b ∈ Z ρ(a · b) = ρ(a) · ρ(b)Beweis: (Beh.:) Wissen: a mod m = a1 mod m

b mod m = b1 mod m∗⇒ (ab) mod m = (a1b1) mod m

Sei a1 := a mod m = ρ(a), b1 := b mod m = ρ(b)

ρ(ab) = (ab) mod m∗= (a1b1) mod m = (ρ(a)ρ(b)) mod m = ρ(a) · ρ(b) // (Beh)

⇒ ρ erfullt die Axiome einer Ringmorphismus

(aber noch nicht gezeigt, dass Zm Ring ist)

Zm ist ein kommutativer Ring

Distributivgesetz x · (x + z) = x · y + x · z fur x, y, z ∈ Zm

ρ surektiv ⇒ ∃a, b, c ∈ Z x = ρ(a), y = ρ(b), z = ρ(c)

ρ(a) · (ρ(b) + ρ(c)) = ρ(a) · ρ(b+ c) = ρ(a(b + c))

= ρ(a · b+ a · c) = ρ(a · b) + ρ(a · c)= ρ(a) · ρ(b) + ρ(a) · ρ(c)

Analog zeigt man Assoziativgesetz x · (y · z) = (x · y) · zKommutativgesetz x · y = y · x

⇒ alles gezeigt

4.1.13 Beispiel

(1) Rechnen in Z11

7 · 8 = 1, 3 · 9 = 5

(2) (516 + 3 · 54 − 2 · 52) mod 7 =?

= ρ(516 + 3 · 54 − 2 · 52) = ρ(5)16︸︷︷︸

=2

+ ρ(3) · ρ(5)4︸︷︷︸

=6

− ρ(2) · ρ(5)2︸︷︷︸

=1

in Z7 52 = 4 3 · 54 = 3 · 2 = 6

54 = 42 = 2 2 · 52 = 2 · 4 = 1

58 = 22 = 4


Lineare Algebra I


Vorlesung 18


Michael Habermann

[email protected]

516 = 42 = 2

Schreibweise: Statt a mod m = b mod m schreibt man meist

a ≡ b mod mDies definiert eine Aquivalentklasse auf Z, der Aquivalenzklassen

gerade die Nebenklassen von < m > sind!

(3) Multiplikations-Tafel von Z6

· 0 1 2 3 4 5

0 0 0 0 0 0 0

1 0 1 2 3 4 5

2 0 2 4 0 2 4

3 0 3 0 3 0 3

4 0 4 2 0 4 2

5 0 5 4 3 2 1

2 · 3 = 0, 2 6= 0, 3 6= 0

Nullteiler von Z6: 2, 3, 4

(4) Multi.-Tafel von Z5 keine Nullteiler

Z5 ist ein Integritatsbereich

4.1.14 Definition

Sei A ein kpmmutativer Ring

(1) a ∈ A heisst Nullteiler, falls a 6= 0 und ∃b 6= 0 ab = 0

(2) A heisst Integritatsbereich, falls A keinen Nullteiler hat und A 6= ∅

4.1.15 Bemerkung

In Integritatsbereichen kann man ”Kurzen”, d.h.

ac = bc, c 6= 0 ⇒ a = b

Grund: ac = bc ⇒ (a− b)c = 0 ⇒ a− b = 0

c kein Nullteiler

4.1.16 Beispiel

Z, Q, R Integritatsbreiche

4.2 Exkurs uber ganze Zahlen

Teilbarkeit in Z, a, b ∈ Z

a|b ”a teilt b” :⇔ ∃c ∈ Z ac = b


Lineare Algebra I


Vorlesung 18


Michael Habermann

[email protected]

4.2.1 Regeln

Fur alle a, b, c ∈ Z gilt

1|aa|0a|b und b 6= 0 ⇒ |a| ≤ |b|a|b und b|c ⇒ a|ca|b und b|a ⇒ a = ±b0|a ⇔ a = 0

a|1 ⇔ a = ±1

a|b und a|c und x, y ∈ Z ⇒ a|(xb+ yc)

4.2.2 Definition

Eine Zahl p ∈ N heisst Primzahl, falls p genau zwei positivie Teiler hat.

Nichtprimzahlen heissen zusammengesetzt

4.2.3 Satz

jede positive ganze Zahl a ist ein Produkt von Primzahlen

(1 = leeres Produkt)

Beweis: Induktion nach n n = 1, 2 klar

Schritt: n ≥ 2 ObdA n zusammengesetzt Etwa n = ab, 1 < a, b < n

Indu’Vor ⇒ ∃ Zerlegung a = p1 · · · pr, b = q1 · · · qs, pi, qj prim

n = ab = p1 · · · prq1 · · · qs //

4.2.4 Großter gemeinsamer Teiler (ggT)

Sei a, b ∈ N∗

T := x ∈ N∗ : x|a und x|bSei d das maximale Element von T , d ist der großte gemeinsame Teiler von a, b

Bez.: d = ggT (a, b)

4.2.5 Satz

(1) ∃u, v ∈ Z d = ua+ vb

(2) T = x ∈ N∗ : x|d d.h.,

∀x ∈ N∗ (x|a und x|b ⇔ x|d)

Beweis: (1) Sie d∗ das minimale Element von

I := x ∈ N∗ : ∃u′, v′ ∈ Z x = u′a+ v′bEtwa d∗ = ua+ vb Division mit Rest

d∗ = qa+ r, 0 ≤ r < a

⇒ r = d∗ − qa = (u− q)a+ vb ∈ I


Lineare Algebra I


Vorlesung 18


Michael Habermann

[email protected]

Fortsetzung folgt im nachsten Jahr!

Berechnen des ggTs mit euklidischem Algorithmus

4.2.6 Beispiel

a = 600, b = 237 ggT (600, 237) = ggT (237, 126)

600 = 2 · 237 + 126 = ggT (237, 126) = ggT (126, 111)

b = 237 = 1 · 126 + 111 ...

126 = 1 · 111 + 15 ...

111 = 7 · 15 + 6 ...

15 = 2 · 6 ...

6 = 2 · 3 + 0 ggT (6, 3) = ggT (3, 0) = 3

4.2.7 Bemerkung

a = qb+ r Dann

ggt(a, b) = ggt(b, r)

Beweis: x|a ∧ x|b⇔ x|b ∧ x|r

Suchen u, v ∈ Z mit ua+ vb = d = 3

126 = a− 2b erweiterer euklidischer Algorithmus

111 = b− 126 = b− (a− 2b) = −a+ 3b

15 = 126− 111 = (a− 2b)− (−a+ 3b) = 2a− 5b

6 = 111− 7 · 15 = (−a+ 3b)− 7(2a− 5b) = −15a+ 38b

3 = 15− 2 · 6 = (2a− 5b)− 2 · (−15a+ 38b) = 32a− 81b

Ergebnis: 3 = ggT (600, 237) = 32 · 600− 81 · 237, v = −81

u = 32


Lineare Algebra I


Vorlesung 19


Michael Habermann

[email protected]

Beweis zur letzten Vorlesung

a, b ∈ N∗ T := x ∈ N∗ : x|a ∧ x|bd := maxT = ggT (a, b)

4.2.8 Satz

(1) ∃u, v ∈ Z d = ua+ vb

(2) T = x ∈ N∗ : x|d, d.h.

∀x ∈ N∗ (x|d ⇔ x|a ∧ x|b)

Beweis: zu (1) I := x ∈ N∗ : ∃u, v ∈ Z : x = ua+ vbd∗ := minI Etwa d∗ = ua+ vb zu zeigen: d = d∗

· d ≤ d∗: x ∈ T ⇒ x|a ∧ x|b ⇒ x|d∗ ⇒ x ≤ d∗Also d = maxT ≤ d∗

· d∗ ∈ T : Division mit Rest

a = qd∗ + r, 0 ≤ r < d∗

r = a− qd∗ = a− q(ua+ vb)

= (1− qu)a− qubMinimalitat von d∗ ⇒ r = 0 (sind r ∈ I r < d∗)

Also d∗|aAnalog d∗|b Also d∗ ∈ TEs folgt d = d∗

zu (2) x|a ∧ x|b ⇒ x|dx|d ⇒ x|a ∧ x|b //

4.2.9 Bemerkung

Berechnung von u, v in (1) geht effizient mit dem erweiterten euklidischen Algorithmus

4.2.10 Definition

a, b ∈ N∗ heissen teilerfremd, wenn ggT (a, b) = 1

4.2.11 Korrolar

ggT (a, b) = 1 ⇒ ∃u, v ∈ Z ua+ vb = 1

4.2.12 Korrolar

Sei p Primzahl, a, b ∈ Z

p|(ab) ⇒ p|a oder p|b

Beweis: oBdA a, b ∈ N∗. Zeigen Kontraposition


Lineare Algebra I


Vorlesung 19


Michael Habermann

[email protected]

Sei p † a und p † b Dann ggT (p, a) = 1, ggT (p, b) = 1

Korrolar⇒ ∃u, v, u′, v′ ∈ Z

1 = up+ va, 1 = u′p+ v′b

⇒ 1 = (up+ va)(u′p+ v′b) = (uu′p+ uu′b+ vau′)p+ vv′(ab)

⇒ p † (ab) (sonst p|1 ) //

4.2.13 Hauptsatz der elementaren Zahlentheorie

Jedes n ∈ N∗ hat eine bis auf die Reihenfolge eindeutige Produktzerlegung in Primzahlen:

n = p1 · · · pr = q1 · · · qs, pi, qj Primzahlen

⇒ r = s und ∃σ ∈ Sr ∀i pi = qσ(i)

Beweis: Existenz: bereits gezeigt (Kummer)

Eindeutigkeit: mit Induktion nach r

Start: r = 0 ⇒ n = 1 ⇒ s = 0√

Schritt: r ≥ 1 pr|n∗ ⇒ ∃j pr|qj (∗ p prim, p|(a1...an) ai ∈ Z ⇒ ∃ip|ai)

oBdA j = s (Vertausche Reihenfolge der q, ..., qs)

p1 · · · pr−1pr = q1 · · · qs−1pr ⇒ p1 · · · rr−1 = q1 · · · qs−1

Verwende Induvor: r − 1 = s− 1 ⇒ (r = s) ... //

4.3 Korper

4.3.1 Definition

Sei A ein Ring a ∈ A heisst Einheit, falls ∃b ∈ A ab = ba = 1

4.3.2 Bemerkung

b ist dann eindeutig bestimmt und heisst (multiplikative) Inverse von a: b =: a−1

[ ab1 = b1a = 1 ∧ ab2 = b2a = 1 ⇒ b1 = b1(ab2) = (b1a)b2 = b2 ]

4.3.3 Satz

A× = a ∈ A : a Einheit ist ein Untermonoid des multiplikativen Monoids von A

und ist eine Gruppe (Einheitsgruppe)

Beweis: (1) A× Untermonoid: 1 ∈ A×

a, c ∈ A× ⇒ ac ∈ A× [ (ac)(c−1a−1 = a(cc−1)a−1

= aa−1 = 1

(c−1a−1)(ac) = 1]

(2) A× Gruppe, Inversenoperation a 7→ a−1 //


Lineare Algebra I


Vorlesung 19


Michael Habermann

[email protected]

4.3.4 Definition

Ein Schiefkorper ist ein Ring K mit K× = K \ 0Ein Korper ist ein kommutatirver Schiefkroer K× heisst multiplikative Gruppe von K

4.3.5 Bemerkung

· K× ⊇ K \ 0 bedeutet: ∀a ∈ K (a 6= 0 ⇒ a Einheit)

· K× ⊆ K \ 0 bedeutet K 6= 0 (⇔ 0 6= 1) [Ubung]

4.3.6 Bemerkung

Sei A 6= 0 kommutativer Ring, a ∈ Aa Einheit ⇒ a kein Nullteiler

( a ∈ A× ac = 0 ⇒ c = (a−1a)c = a−10 = 0

⇒ a kein Nullteiler )

⇒ Jeder Korper ist ein Integritatsbereich

4.3.7 Beispiele

(1) Z× = 1,−1 Z ist kein Korper

(2) Q× = Q \ 0 Q ist Korper

(3) R× = R \ 0 R ist Korper

Untersuchen die Restklassen Zm auf Einheiten und Nullteiler

4.3.8 Satz

Sie m ∈ N, m ≥ 2, a ∈ Zm, a 6= 0

(1) a ∈ Z×m ⇔ ggT (a,m) = 1

(2) a Nullteiler ⇔ ggT (a,m) > 1

Also haben disjunkte Zerlegung

Zm = Z×m ∪ a : a Nullteiler ∪ 0

Beweis: · Sei ggT (a,m) = 1 Dann ∃u, v ∈ Z

1 = ua+ vm. Wende Ringmorphismus ρ : Z→ Zm, x 7→ x mod m an

Also 1 = ρ(1) = ρ(ua+ vm) = ρ(u)ρ(a) + ρ(v)ρ(m)

= ρ(u) · a⇒ a ∈ Z×

m

· d = ggT (a,m) > 1 Dannmd∈ N, m

d< m ⇒ 0 6= m

d∈ Zm

a · md

= ad·m in Z

aZm· m

d= 0 in Zm


Lineare Algebra I


Vorlesung 19


Michael Habermann

[email protected]

Also a = 0 oder a Nullteiler

a ∈ Zm \ 0 : ggT (a,m) = 1 ⊆ Z×m ⊆ Zm \ 0

a ∈ Zm \ 0 : ggT (a,m) > 1 ⊆ a ∈ Zm : a Nullteiler ⊆ Zm \ 0V ereinigung dieser disjunkten Mengen ist Zm \ 0

4.3.9 Beispiele

m = 600, a = 539 539−1 =? in Z600

EEA ⇒ 1 = −53 · 600 + 59 · 539 in Z

⇒ 1 = 59 · 539 in Z600 ⇒ 539−1 = 59


Lineare Algebra I


Vorlesung 20


Michael Habermann

[email protected]

4.3.10 Beispiel

(1) Ring Z12, Einheitsgruppe Z×12

Multiplikations-Tabelle

· 1 5 7 11

1 1 5 7 11

5 5 1 11 7

7 7 1 11 5

11 11 7 5 1

∀a ∈ Z×12 a

2 = 1 (”Diagonale”)

⇒ Z×12 nicht zyklisch

(2) Z×11 = 1, 2, .., 10 = Z11 \ 0 Einheitsgruppe

Z11 ist ein Korper

a = 2 Ordnung um a in Z×11?

(k 1 2 3 4 5 ... 8 9 10

ak 2 4 8 5 10 ... 3 6 1

)

ord(2)|10 ⇒ ord(2) = 10

Z×11 ist zyklisch und zwar erzeugt von a = 2

4.3.11 Korrolar

Sei m ∈ N, m ≥ 2 Aquivalent sind

(1) Zm Korper

(2) Zm Integritatsbereich

(3) m Primzahl

Beweis: (1) ⇒ (2): klar

(2) ⇒ (3): Kontraposition: Sei m = ab a, b < m

⇒ a · b = 0 in Zm a, b 6= 0 in Zm

⇒ a Nullteiler

(3) ⇒ (1): Sei m prim, a ∈ Zm, a 6= 0

ggT (a,m) = 1,m ⇒ ggT (a,m) = 1

⇒ a ∈ Z×m. //

4.3.12 Bemerkung

Die Zm mit m prim heissen endliche Primkorper

4.3.13 Satz (Kleiner Fermatischer Satz)

Sei p eine Primzahl, a ∈ Z×p


Lineare Algebra I


Vorlesung 20


Michael Habermann

[email protected]

Dann ap−1 = 1 in Zp

Anders formuliert: p prim, a ∈ Z, p † a⇒ ap−1 mod p = 1

Beweis: G eindliche Grupp, g ∈ G ⇒ g|G| = e (∗)Hier G = Z×

p = Zp \ 0⇒ |Z×

p | = p− 1

(∗) ⇒ ap−1 = 1 fur a ∈ Z×p //

4.3.14 Beispiel

(1) 802 in Z×11? Kleiner Fermat ⇒ 810 = 1 in Z11

892 = 89·10+2 = (810)9 · 82 = 19 · 82 = 9 in Z11

(2) Welcher Wochentag ist in 2473198 Tage?

2473198 mod 7 = (247 mod 7)3198 = 23198 = (26)533 = 1533 = 1

Kleiner Fermat 26 = 1 in Z7

3198 = 533 · 6Heute ist Donnerstag. Dann ist Freitag

4.4 Korper der komplexen Zahlen

4.4.1 Motivation

Z Z x+ b = 0

Z Q ax = b, a 6= 0

Q R Supremum

R C x2 = b [0.2cm] Wollen, dass x2 = −b fur b > 0 eine Losung hat.

Genugt eine Losung i der Gleichung i2 = −1 zu haben.

( (i ·√b)2 = i2 · b = −b) Nehmen an, wir hatten einen Korper K mit

R ⊆ K Unterring, i ∈ K, i2 = −1

(a+ ib) + (c+ id) = (a+ c) + i · (b+ d)

(a+ ib) · (c+ id) = (ac− bd) + i(ad+ bc)

Die Menge K0 := a+ ib : a, b ∈ R ist ein Unterring von K

Ferner (a+ ib)( aa2+b2

− i · ba2+b2

= (a+ib)(a−ib)a2+b2

= a2+b2

a2+b2= 1

Also hat jedes x ∈ K0, x 6= 0 eine multiplikaive Inverse in K0

⇒ K0 ist ein Korper. Man sagt K0 ist ein Unterkorper von K

Schreibweise eindeutig: a+ ib = a′ + ib′, a, b, c, d inR

⇒ a = a′, b = b′

( i(b− b′) = a′ − a. Ware b 6= b′ ⇒ b− b′ 6= 0

⇒ i = a′−ab−b′

∈ R da i2 = −1, Also b = b′ ⇒ a = a′)


Lineare Algebra I


Vorlesung 20


Michael Habermann

[email protected]

K0 ist der kleinste Unterkorper von K der R und i enthalt.

4.4.2 Konstruktion von C

Definiere C := R×R als Menge. Definiere

(a, b) + (c, d) := (a+ c, b+ d)

(a, b) · (c, d) := (ac− bd, ad+ bc)

0 := (0, 0)

−(a, b) := (−a,−b)1 := (1, 0)

4.4.3 Definition

Bezuglich dieser Operationen ist C ein Korper

Beweis: Beweis durch triviales Nachrechnen der Korperaxiome

C heisst Korper der komplexen Zahlen

4.4.4 Bemerkung

(1) Die Menge R = R× 0 ist ein Unterkorper von C

und R→ R, a 7→ (a, 0) ist ein Ringisomorphismus (Nachprufen!)

Identifiziere R mit R

⇒ R ⊆ C Unterkorper

(2) i := (0, 1) ⇒ i2 = (0, 1) · (0, 1) = (−1, 0) = −(1, 0) = −1

(a, b) = (a, 0) + (0, b) = (a, 0) + (0, 1) · (b, 0)

= (a, 0) + i(b, 0)

= a+ i · bubliche Schreibweise

4.4.5 Bezeichnung

z = a+ ib

a = Re(z) heisst Realteil von z

b = Im(z) heisst Imaginarteil von z

|z| :=√a2 + b2 heisst Absolutbetrag von z

Die Zahlen ib heissen rein imaginar


Lineare Algebra I


Vorlesung 21


Michael Habermann

[email protected]

5 Vektorraume und lineare Abbildungen

5.1 Lineare Gleichungssysteme

5.1.1 Beispiele

Gleichungen uber R

(1)x − 2y = 1 | · 23x + 4y = 5 |

5x = 7 ⇒ x = 75 , y = 1

5

(2)x − 2y = 1

3x − 6y = 3

2. Gleichung uberglussig, hat unendlich viele Losungen

x = 1 + 2µ, y = µ mit belibigen µ ∈ R

(3)x − 2y = 1

3x − 6y = 5

hat keine Losung

Sei K ein fest gewahlter Korper (z.B. K = Q, R, C, Zp)

Betrachte das lineare Gleichungssystem (LG)

α11x1 + α12x2 + ... + α1nxn = β1

α21x1 + α22x2 + ... + α2nxn = β2

......

αq1x1 + αq2x2 +... + αqnxn = βq

mit q Gleichungen und n Unbekannten xj und Koeffizienten αij , βi ∈ KL heisst homogen, falls β1 = ... = βq = 0

L heisst quadratisch, falls q = n ist.

Ein n-Tupel ξ = (ξ1, ..., ξn) ∈ Kn heisst Losung von L, falls

∀1 ≤ i ≤ q αi1ξ1 + αi2ξ2 + ...+ αinξn = βi, d.h.

∀in∑

j=1

αijξj = βi (in K)

5.1.2 Definition

Eine qxn-Matrix uber K ist eine rechteckiges Schema

A =

α11 α12 ... α1n

α21 α22 ... α2n

......

αq1 αq2 ... αqn

= [αij]1≤i≤q∧1≤j≤n = [αij ]


Lineare Algebra I


Vorlesung 21


Michael Habermann

[email protected]

mit Koeffizienten (oder Eintragen) αij ∈ K

Die i-te Zeile ist das n-te Tupel (αi1, αi2, ..., αin)

Die j-te Spalte ist das n-te Tupel

α1j

α2j

...

αqj

Eine nxn-Matrix heisst quadratisch

Formale Definition: Eine qxn-Matrix uber K ist eine Abbildung

α : 1, 2, ..., q × 1, 2, ..., n → K, (i, j)→ α(i, j) =: αij

Die Menge der qxn-Matrizen uber K wwird bezeichnet mit Kqxn (oder mit Matq,n(K))

Die Koeffizientenmatrix des Gleichungssamstems (L) ist die qxn-Matrix

A = [αij ]

Die erweitere Koeffizientenmatrix

A′ =

α11 ... α1n β1

......

αq1 ... αqn βq

Lineare Gleichungen werden bijektiv durch ihre erweitere Koeffizientenmatrix beschrieben

5.1.3 Gausselimination

Folgende Zeilenoperationen lassen die Losungsmenge invariant (unverandert):

(1) Vertauschen zweier Zeilen: sei i < l

(2) Addieren eines Vielfachen einer Zeile zu einer anderen

Sei ξ ∈ Kn Losung des linken Systemsn∑

j=1

αijξj = βi ⇒n∑

j=1

λαijξj = λβi

n∑

j=1

αljξj = βl

⇒∑

j

αljξj +∑

j

λαijξj = βl + λβi

=∑

j

(αlj + λαij)ξj

Mit Hilfe von (1) und (2) lasst sich A′ auf Treppenform (oder Stufenform) bringen

0 0 ∗ ...

0 0 0 ... ∗ 0 ...

0 0 0 0 0 0 0∗ ...

∗ steht fur Zahl 6= 0

Formale Definition Eine qx(n− 1)-Matrix C = [γij ] hat


Lineare Algebra I


Vorlesung 21


Michael Habermann

[email protected]

Treffenform, falls ∃i1 ∈ 0, 1, ..., q so, dass

m(i) := j : γij 6= 0fur 1 ≤ i ≤ i1 existiert und i 7→ m(i) strengmonoton wachsend ist und

γij = 0 fur i > i1

5.1.4 Beispiel

K = Z3 = 0, 1, 2, 3, q = 4, n = 5

x3 + x4 + x5 = 1

x1 + 2x2 + x3 + 2x5 = 1

x1 + 2x2 + x4 + 2x5 = 0

2x1 + x2 + x3 + 2x5 = 0

A′ =

0 0 1 1 1 1

1 2 1 0 2 1

1 2 0 1 2 0

2 1 1 0 2 0

=

1 2 1 0 2 1

0 0 1 1 1 1

1 2 0 1 2 0

2 1 1 0 2 0

=

1 2 1 0 2 1

0 0 1 1 1 1

0 0 2 1 0 2

0 0 2 0 1 1

=

1 2 1 0 2 1

0 0 1 1 1 1

0 0 0 2 1 0

0 0 0 1 2 2

=

1 2 1 0 2 1

0 0 1 1 1 1

0 0 0 2 1 0

0 0 0 0 0 2

Treppenform C

Zu C gehort das Gleichungssytem (L′) und L′ hat die Gleiche Losungsmenge wie L

Also ist L unlosbar.

kleine Abanderung von L:


Lineare Algebra I


Vorlesung 21


Michael Habermann

[email protected]

x3 + x4 + x5 = 1

x1 + 2x2 + x3 + 2x5 = 1

x1 + 2x2 + x4 + 2x5 = 0

2x1 + x2 + x3 + 2x5 = 1

A′ =

0 0 1 1 1 1

1 2 1 0 2 1

1 2 0 1 2 0

2 1 1 0 2 1

=

1 2 1 0 2 1

0 0 1 1 1 1

1 2 0 1 2 0

2 1 1 0 2 1

=

1 2 1 0 2 1

0 0 1 1 1 1

0 0 2 1 0 2

0 0 2 0 1 2

=

1 2 1 0 2 1

0 0 1 1 1 1

0 0 0 2 1 0

0 0 0 1 2 0

=

1 2 1 0 2 1

0 0 1 1 1 1

0 0 0 2 1 0

0 0 0 0 0 0

⇒ (L′) =

x1 + 2x2 + x3 + 2x5 = 1

x3 + x4 + x5 = 1

2x4 + x5 = 0

0 = 0

Losungsmenge des modifizierten Systems?

Wahrend ξ2, ξ5 ∈ K belibig

Bestimmte ξ4, ξ3, ξ1 eindeutig aus (L′) von unten nach oben so erhalt man alle Losungen

2ξ4 + ξ5 = 0 ⇒ 2ξ4 = ξ5 = 2ξ5 ⇒ ξ4 = ξ5ξ3 = −ξ4 − ξ5 + 1 = −2ξ5 + 1 = ξ5 + 1

ξ1 = −2ξ2 − ξ3 − 2ξ5 + 1 = ξ2 − ξ5 − 1− 2ξ5 + 1 = ξ2

Losungsmenge = (ξ2, ξ2, ξ5 + 1, ξ5, ξ5) : ξ2ξ5 ∈ Z3Es gibt genau 9 Losungen

z.B. ist Losung (0, 0, 1, 0, 0)


Lineare Algebra I


Vorlesung 22


Michael Habermann

[email protected]

5.1.5 Beispiel

K = Q, q = 3, n = 4

(L)

2x1 + x3 − 3x4 = 1

3x1 − x2 − 4x4 = 012x2 − x3 = 1

3

erweiterte Koeffizientenmatrix

A′ =

2 0 1 −3 1

3 −1 0 −4 0

0 12 −1 0 1

3

7→

2 0 1 −3 1

0 −1 − 32

12 − 3

2

0 12 −1 0 1

3

7→

2 0 1 −3 1

0 −1 − 32

12 − 3

2

0 0 − 74

14 − 5

12

(L’)

2x1 + x3 − 3x4 = 1

− x2 − 32x3 + 1

2x4 = − 32

− 74x3 + 1

4x4 = − 512

Gebundene Variable x1, x2, x3

Freie Variable x4

Losungsmenge: Wahle ξ4 ∈ Q belibig und bestimme daraus eindeutig ξ1, ξ2, ξ3aus (L’) von unten nach oben.

5.1.6 Algorithmusw fur Gausselimination

Eingabe [aij ]1≤i≤q,1≤j≤n+1 [ aij ∈ K stehen fur Variable (Speicherplatze)

fur die Koeffizienten der Matrix A’ ]

Variable r, s ∈ N fur Adressierung des Arbeitsfeldes, Hilfsvariable z ∈ K

0. Setzte r ← 1, s← 1

1. Falls r ≥ q STOP

2. Falls s > n+ 1 STOP

3. Falls (∀i ≥ r air = 0) setze s← s+ 1 und gehe nach 1.

4. Wahle i0 ≥ r mit ai0,r 6= 0 (z.B. das kleinste Solche)

Fur j = s, ..., n+ 1 setze (Vertausche i0-te mit r-te Zeile)

z ↔ arj

arj ← ai0j

ai0j ← z

5. Fur i = r + 1, ..., q setze z ← ais

ars

Fur j = s+ 1, ..., n+ 1 setze aij ← aij − zarj

(Subtrahiere z-faches der r-ten Zeile von der i-ten Zeile)

6. Setze r ← r + 1, s← s+ 1 und gehe nach 1. (Verschiebe Arbeitsfeld nach rechts unten)

5.1.7 Allgemein

Sei ein Gleichungssystem in Treppenform:


Lineare Algebra I


Vorlesung 22


Michael Habermann

[email protected]

∀i ≤ i0 γim(i) 6= 0

∀i < i0 m(i) < m(i+ 1)

Die m(i) heissen Pivotindizes (Pivot: Angelpunkt) die γim(i) heissen Pivotelemente

die xm(i), ..., xm(i0) heissen gebundene Varibalen die ubrigen xj heissen freie Varibablen

Losungsmenge von L’: Wahle belibige Werte in K fur die freien Variablen xj . Dann gibt

es genau eine Moglichkeit, die gebundenen Variablen xim(i) mit

Werten aus K zu belegen damit eine Losung entsteht.

L’ ist unlosbar genau dann, wenn die i0-te Zeile die Form 0 = δi0hat mit δi0 6= 0

5.1.8 Satz

Ein homogenes lineares Gleichungssystem uber einem Korper K

mit q Gleichungen und n Variablen mit n > q

hat stetig eine nichttriviale Losung, d.h. Losung 6= (0, ..., 0)

Beweis: Bringe das Gleichungssystem auf Treppenform

Dabei andert sich die Losungsmenge nicht

Es gibt hochstens q gebundene Variable.

Wegen n > q ibt es wenigstens eine freie Variable.

Diese kann auf 1 gesetzt werden und zu einer Losung 6= (0, ..., 0) erweitert werden. //

5.1.9 Satz

Sei L ein lineares Gleichungssystem uber dem Korper K. Sei E ein Oberkorper von K

d.h. K ⊆ E und K ist Unterring von E. Dann

L ist losbar uber E ⇔ L losbar uber K

Beweis: Bringe L auf Treppenform L′

L′ ist ein System uber K:

LoesK(L) = LoesK(L′)

Analog: LoesE(L) = LoesE(L′)

G.z.z. L′ losbar uber E ⇔ L′ losbar uber K

Wissen: L′ unlosbar uber K ⇔ i0-te Zeile von L′ hat Form 0 = δi0 ,

δi0 6= 0 ⇔ L′ unlosbar uber E

5.2 Vektorraume

Sei K ein Korper.

5.2.1 Definition

Ein Vektorraum uber K (ein K-Vektorraum) ist eine Menge V ,


Lineare Algebra I


Vorlesung 22


Michael Habermann

[email protected]

zusammen mit:

· einer binaren Operation +

· einem ausgezeichnetem Element 0

· eine einstellige Operation −· fur jedes λ ∈ K eine 1. stellige Operation

v 7→ λv, derart, dass gilt:

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

(2) ∀λ, µ ∈ K ∀n, v ∈ Vλ(u + v) = (λu) + (λv)

(λ+ µ)v = (λv) + (µv)

λ(µv) = (λµ)v

1v = v

Die Elemente v ∈ V heissen Vektoren

5.2.2 Beispiel

Anschauungsschema mit Bezugspunkt 0

E0 = v : v Ortsvektor an 0


Lineare Algebra I


Vorlesung 23


Michael Habermann

[email protected]

Wiederholung:

K Korper, V Menge, + : V × V → V , · : K × V → V

(V,+, ·) heißt Vektorraum uber K (K-Vektorraum), falls

(1) (V,+) abelsche Gruppe

(2) ∀λ, µ ∈ K, u, v ∈ V :

λ(µv) = (λµ)v

1v = v

λ(u + v) = λu + λv

(λ + µ)v = λv + µv

5.2.3 Definition

V K-VR, U ⊆ V . Dann heißt U ein Unterraum von V , falls

(1) U Untergruppe von (V,+)

(2) ∀λ ∈ K, v ∈ U : λv ∈ U

5.2.4 Bemerkung

· Ein Unterraum von V ist in naturlicher Weise ein K-VR

· 0, V sind immer Unterraume von V

[ zeige spater: λ0 = 0 ∀λ ∈ K ]

5.2.5 Beispiel

(1) K := R, E = Anschauungsebene. Wahle Bezugspunkt

0′ ∈ E Sei E0′ := Ortsvektoren v an 0′Zeichnung sollte jeder Selber haben oder aber einfach so wissen.

(2) Analog ist die Menge R0′ der Ortsvektoren an einen festen Bezugspunkt

im Anschauungsraum ein R-VR

Sei E eine Ebene durch 0′. Dann ist

U := v ∈ R0′ : Endpunkt von v liegt in Eein Unterraum von R0′

(3) Aufgabe 01 von Blatt 13:

X 6= ∅, Menge, K Korper. Sei V := f : X → KFur f, g ∈ V definiere: f + g durch (f + g)(x) := f(x) + g(x)

Fur λ ∈ K, f ∈ V dfiniere: λf durch (λf)(x) := λf(x)

Damit ist V ein K-Vektorraum

Die Beispile (4) bis (6) sind Spezialfalle davon:

(4) K Korper, n ∈ N


Lineare Algebra I


Vorlesung 23


Michael Habermann

[email protected]

Kn := K × ...×K︸︷︷︸

n−mal

= f : 1, ..., n → K

⇒ Kn ein K-VR

Es gilt fur ξ = (ξ1, ..., ξn), µ = (µ1, ..., µn) ∈ Kn, λ ∈ Kξ + µ = (ξ1 + µ1, ..., ξn + µn)

−ξ = (−ξ1, ...,−ξn)

0 = (0, ..., 0)

λξ = (λξ1, ..., λξn)

Oft schreibt man ξ ∈ Kn ans Spalte ξ =

ξ1...

ξn

(5) K∞ := (αn) : αn ∈ K∀n = α : N→ KK∞ ist K-Vektorraum

(6) KK = f : K → K ist K-VR

Beispiele fur Unterraume:

(4’) Qn ist kein UR des R-VR Rn

Aber: Rn ist Q-VR

Dann ist Qn UR der Q-VR Rn

Allgemein: Sei k ⊆ K, k Unterkorper von K

Dann ist kn ein UR des k-VR Kn

(4”) Betrachte das homogone LGS uber K

(H)

α11x1 + ... +α1nxn = 0...

...

αq1x1 + ... + αqnxn = 0

Damit ist Sol(H) = ξ ∈ Kn : ξ Losung von (H)

ein K-UR von Kn. Sei fur β =

β1

...

βn

∈ Kq

Lβ das zugehorige inhomogene LGS. Dann ist

β ∈ Kq : Lβ losbar in UR von Kq

(5’) α ∈ R∞ : α konvergiert , α ∈ R∞ : α Nullfolge sind URe von R∞

(6’) C(R) := f : R→ R : f stetig UR von RR

D(R) := f : R→ R : f diff’bar UR von C(R)

5.2.6 Bemerkung

Sei V K-VR, u, v ∈ V , λ, µ ∈ K Dann gilt

(1) 0 ∈ K · v = 0 ∈ V (o · v = (0 + 0)v = 0v + 0v ⇒ 0 = 0v )

(2) λ · 0 = 0 ( λ · 0 = λ(0 + 0) = λ0 + λ0 ⇒ 0 = λ0 )


Lineare Algebra I


Vorlesung 23


Michael Habermann

[email protected]

(3) λv = 0 ⇒ λ = 0 oder v = 0

(λv = 0, λ 6= 0 ⇒ 0 = λ−1(λv) = (λ−1λ)v = 1v = v)

(4) (−1)v = −v Spezialfall von

(5) (−λ)v = −(λv) = λ(−v)((−λ)v + λv = (−λ+ λ)v = 0v = 0)

(6) (λ − µ)v = λv − µvλ(u − v) = λu − λv (Bew. zur Ubung)

(7) Verallgemeinerte Distributivitat:

Fur λ, λ1, ..., λn ∈ K, v, v1, ..., vn ∈ V gilt:

(λ1 + ...+ λn)v = λ1v + ...+ λnv

λ(v1 + ...+ vn) = λv1 + ...+ λvn

(Beweis mit Induktion)

In Summenschreibweise:

(n∑

i=1

λi)v =n∑

ı=1λiv, λ(

n∑

i=1

vi) =n∑

i=1

λvi

(8) U1, U2 Unterrume von V ⇒ U1 ∩ U2 UR von V

Vorsicht: U1 ∪ U2 ist i.a. kein UR

5.2.7 Satz-Definition

Sei V ein K-VR, M ⊆ V . Dann existiert genau ein kleinster Unterraum U0 von V ,

der M enthalt. Dieser heisst der von M erzeugte Unterraum

(der von M aufgespannte UR, die lineare Hulle von M)

Bez. span(M) := U0 M erzeugt V ⇔ span(M) = V

Beweis, Existenz:

Sei U := U ⊆ V : U UR von V , M ⊆ UDef U0 :=

⋂U := v ∈ V : ∀U ∈ U : v ∈ U Dann gilt

M ⊆ U0, und U0 ist UR von V

Ferner ∀U ∈ U : U0 ⊆ UAlso ist U0 ein kleinster UR von V , der M enthalt (∗)Eindeutigkeit: Sei U1 ein UR von V , der (∗) erfullt.

M ⊆ U0 ⇒ U1 ⊆ U0

M ⊆ U1 ⇒ U0 ⊆ U1

⇒ U0 = U1

Suchen eine explizite Beschreibung fur span(M)

5.2.8 Definition

Seien v, v1, ..., vn ∈ V Dann heisst v eine Linearkombination

von v1, ..., vn, falls

∃λ1, ..., λn ∈ K: v = λ1v1 + ...+ λnvn

Bem.: U UR von V , v1, ..., vn ∈ U ⇒ λ1v1 + ...+ λnvn ∈ U


Lineare Algebra I


Vorlesung 23


Michael Habermann

[email protected]

5.2.9 Proposition

Sei M ⊆ V Dann gilt

span(M) = v ∈ V : v ist Lin-Komb. von Vektoren aus M =: U1

Beweis: Es gilt:

· U1 UR von V

· M ⊆ U1

U UR von V mit M ⊆ U ⇒ U1 ⊆ USatz-Def ⇒ U1 = span(M), da span(M) eindeutig //

5.2.10 Bemerkung

M := v1, ..., vn ⇒ span(M) = λ1v1 + ...+ λnvn : λ1, ..., λn ∈ K


Lineare Algebra I


Vorlesung 24


Michael Habermann

[email protected]

5.2.11 Wiederholung

Kn ist K-Vektorraum

(x1, ..., xn) + (y1, ..., yn) := (y1 + y1, ..., xn + yn)

λ · (x1, ..., xn) := (λx1, ..., λxn)

Ein Unterraum des K-VRs V ist eine Teilmenge nichtleere U ⊆ V mit

∀u, v ∈ U u+ v ∈ U∀λ ∈ K ∀v ∈ U λv ∈ U

z.B. V = R2

echte Unterraume entsprechen ”Geraden durch den Nullpunkt”

v1, ..., vn, v ∈ Vv heisst Linearkombination von v1, ..., vn falls

∃λ1, ..., λn ∈ Kv = λ1v1 + ...+ λnvn

M ⊆ Vspan(M) = v ∈ V : v ist Linearkombination von Elementen aus MM erzeugt V , falls span(M) = V

M = v1, ..., vn ⇒ span(M) = λ1v1 + ...+ λnvn : λi ∈ K

5.2.12 Beispiele

(1) R2 wird erzeugt von (1, 0), (0, 1)Formal: (x, y) ∈ R2 ⇒ (x, y) = x(1, 0) + y(0, 1)

R2 wird erzeugt von (1, 2), (3, 4)(1, 0) = (3, 4)− 2(1, 2)

(0, 1) = 12 ((1, 2)− (1, 0)) = 1

2 (1, 2)− 12 (1, 0)

(2) R3 wird erzeugt von (1, 0, 0), (0, 1, 0), (0, 0, 1)(3) Kn ist erzeugt von e1, ..., en, wobei

ei := (0, ..., 0, 1, 0, ..., 0) (die 1 ist an der i-ten Stelle

x = (x1, ..., xn) = x1e1 + ...+ xnen)

(4) A = [αij ] ∈ Kq×n

M :=

α11

...

αq1

, ...,

α1n

...

αqn

⊆ Kq

Menge der Spaltenvektoren von A

Beh.: span(M) = β ∈ Kq : Lβ losbarBeweis: Lβ losbar ⇔ ∃ξ ∈ Kn


Lineare Algebra I


Vorlesung 24


Michael Habermann

[email protected]

α11ξ1 + ... + α1nξn = β1

......

αq1ξ1 + ... + αqnξn = βq

⇔ ∃ξ ∈ Kn ξ1

α11

...

αq1

+ ...+ ξn

α1n

...

αqn

=

β1

...

βq

= β

⇔ β ist Linearkombination der Spaltenvektoren von A

⇔ β ∈ span(M) //

5.2.13 Definition

V K-VR, U1, ..., Ur ⊆ V Unterraume

U1 + ...+ Ur := span(U1 ∪ ... ∪ Ur) heisst Summe der U

5.2.14 Bemerkung

U1 + ...+ Ur = v1 + ...+ vr : vi ∈ Ui

5.2.15 Beispiel

(1) R0 = v : v Ortsvektor an 0 im Anschauungsraum· ein Vektor v ∈ R0, v 6= 0 erzeugt eine ”Gerade”

· Zwei Vektoren u, v ∈ R0 erzeugen eine ”Ebene”

(falls u, v nicht in einer Gerade liegen)

(2) U1, U2 ⊆ E0, U1 ∩ U2 = 0U1 + U2 = E0

falls U1 6= U2

(3) U1, U2 ⊆ R0 ”Ebenen”

U1 ∩ U2 = L

U1 + U2 = R0

5.3 Abbildungen zwischen Vektorraumen

5.3.1 Definition

Seien V,W K-Vektorraume. Ein Morphismus (von VR) oder

lineare Abbildung, ist eine Abbildung ϕ : V →W mit

∀u, v ∈ V ϕ(u+ v) = ϕ(u) + ϕ(v)

∀λ ∈ K, v ∈ V ϕ(λv) = λϕ(v)

5.3.2 Beispiel

(1) ϕ : V →W , v 7→ 0 ist Morphismus


Lineare Algebra I


Vorlesung 24


Michael Habermann

[email protected]

(2) id : V → V , v 7→ v ist Morphismus

(3) U ⊆ V Unterraum ⇒Inklusion U → V , u 7→ u ist Morphismus

(4) lim : (αi) ∈ R∞ : (αi) konvergent → R

(αi) 7→ limi→∞

αi

ist lineare Abbildung, denn

limi→∞

(αi + βi) = limi→∞

αi + limi→∞

βi

limi→∞

λαi = λ limi→∞

αi

(5) C(R) = f : f : R→ R stetig R-VR

C(R) = f : f : R→ R stetig diffenzierbar Unterraum

D : C1(R)→ C(R), f 7→ f ′ ist lineare Abbildung

(6) Sei d : E0 → E0 Drehung bzgl. 0 und Winkel α.

Dann ist d eine lineare Abbildung

(7) s : E0 → E0 Spiegelung einer Gerade L durch 0.

s ist eine lineare Abbildung

(8) t : E0 → E0 Translation (Verschiebung) um

w ∈ E0, w 6= 0, dh. t(v) = v + w

t ist keine lineare Abbildung!

u+ v + w = t(u+ v)?= t(u) + t(v) = u+ w + v + w = u+ v + 2w

⇒ w = 2w ⇒ w = 0

5.3.3 Bemerkung

Sei ϕ : V →W lineare Abbildung. Dann

(1) ϕ ist ein Morphismus der zugrundeliegenden abelschen Gruppe

Insbesondere ϕ(0) = 0, ϕ(−v) = −ϕ(v)

(2) ϕ(λ1v1 + ...+ λnvn) = λ1ϕ(v1) + ...+ λnϕ(vn)

(3) kerϕ := v ∈ V : ϕ(v) = 0 ist Unterraum von V

imϕ := ϕ(v) : v ∈ V ist Unterraum von V .

Wissen: ϕ injektiv ⇔ kerϕ = 0ϕ surjektiv ⇔ umϕ = W

5.3.4 Beispiele

(1) V = E0, L,K Geraden durch 0, L 6= K

p : V → L Projektion auf L langs K

kerp = K, imp = L, p ist lineare Abbildung

Spezialfall: ”Orthogonalprojektion” wenn K ⊥ L entspricht

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

(2) lim : (αi) ∈ R∞ : (αi) konvergiert → R ist surjektiv

(αi) 7→ limi→∞

αi


Lineare Algebra I


Vorlesung 24


Michael Habermann

[email protected]

mit Ker

kerlim = (αi) ∈ R∞ : (αi) Nullfolge (3) D : C1(R)→ C(R), f → f ′


Lineare Algebra I


Vorlesung 25


Michael Habermann

[email protected]

V,W K-Vektorraume

ϕ : V →W mit

∀λ, µ ∈ K ∀u, v ∈ V ϕ(λu + µv) = λϕ(u) + µϕ(v)

5.3.5 Bemerkung

(1) ϕ : U → V , ψ : V →W lineare Abbildung

⇒ ψ ϕ lineare Abbildung

(2) ϕ : V →W linear, ϕ bijektiv

⇒ ϕ−1 : W → V linear

Beweis: (2) ϕ−1 Gruppenmorphismus: schon bekannt

z.z. ϕ−1(λw) = λϕ−1(w) fur λ ∈ K, w ∈ WSei w = ϕ(v) ⇒ λw = λϕ(v) = ϕ(λv)

⇒ λϕ−1(w) = λv = ϕ−1(λw) //

5.3.6 Bezeichnungen

· Bijektive lineare Abbildungen heissen (lineare) Isomorphismen

· Eine lineare Abbildung ϕ : V → V heisst Endomorphismus

· Ein bijektiver Endomorphismus heisst Automorphismus

5.3.7 Definition

Zwei K-VR V,W heissen isomorph, falls

es einen Isomorphismus V →W gibt.

Bez.: V ≃W

Es gilt: V ≃ V , V ≃W ⇒ W ≃ VU ≃ V , V ≃W ⇒ U ≃W(≃ Aquivalenzrelation)

5.3.8 Beispiel

(1) R2 → R2, (x, y) 7→ (y, x) ist Automorphismus

(2) E0∼→ R2

v 7→ (ξ1, ξ2), ξ1, ξ2 kartesische Koordinaten von v

5.4 Dimensionen

5.4.1 Definition

Sei V ein K-VR. Eine Folge um Vektoren (v1, v2, ..., vn) aus V heisst

linear unabhangig, falls

∀λ1, ..., λn ∈ K (λ1v1 + ...+ λnvn = 0 ⇒ λ1 = ... = λn = 0)


Lineare Algebra I


Vorlesung 25


Michael Habermann

[email protected]

5.4.2 Bemerkung

(1) (v1, ..., vn) linear unabhangig, wenn sich die Vektoren nur auf die triviale

Art zu 0 linear konstruieren lassen

(2) V linear unabhangig ⇔ V 6= 0 (λv = 0, v 6= 0⇒ λ = 0)

5.4.3 Proposition

(v1, ..., vn) linear unabhangig ⇔ ∃i vi ist Linearkombination

von v1, ..., vi−1, vi+1, ..., vn

Beweis: ”⇒” v1, ..., vn linear abhangig ⇒ ∃λ1, ..., λn ∈ K∃i λi 6= 0 λ1v1 + ...+ λnvn = 0

Also vi = −λ1

λiv1 − ...− λi−1

λivi−1 − λi+1

λivi+1 − ...− λn

λivn

⇒ vi ist Linearkombination von v1, ..., vi−1, vi+1, ..., vn

”⇐ ” Sei Vi = µ1v1 + ...+ µi−1vi−1 + µi+1vi+1 + ...+ µnvn

mit mii ∈ K. Dann

0 = µivi + ...+ µi−1vi−1 + (−1)vi + µi+1vi+1 + ...+ µnvn

Also v1, ..., vn linear abhangig //

5.4.4 Beispiel

(3) V = R3 (1, 0, 0), (0, 1, 0), (1, 1, 0) linear abhangig

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

λ1(1, 1, 0) + λ2(1, 0, 1) + λ3(0, 1, 1) = (0, 0, 0)

(4) Seien v1, ..., vq ∈ Kq gegeben. Entscheide, ob v1, ..., vn linear unabhangig!

Sei vi =

α11

...

αqi

⇒

λ1v1 + ...+ λnvn =

α11λ + ... + α1nλn

......

αq1λ1 + ... + αqnλn

Also

λ1v1 + ...+ λnvn = 0 ⇔ λ = (λ1, ..., λn) ist Losung

des homogenen linearen Gleichungssystems H (welches zu (αij) gehort

Also

v1, ..., vn linear unabhangig ⇔ H hat nur die triviale Losung

5.4.5 Korrolar

Eine Folge von Vektoren v1, v2, ..., vn ∈ Kq mit n > q ist linear abhangig

Beweis: Ein fruherer Satz (siehe Abschnitt Gausselimination), besagt, dann hat H eine

nichttriviale Losung hat, weil n > q ist.


Lineare Algebra I


Vorlesung 25


Michael Habermann

[email protected]

5.4.6 Definition

Sei V V K-VR, e1, ..., en ∈ VDie Folge (e1, ..., en) heisst Basis von V , falls

(1) e1, ..., en erzeugen V

(2) (e1, .., en) linear unabhangig

5.4.7 Beispiel

V = Kn hat die Basis (e1, ..., en), wobei hier

ei = (0, ..., 0, 1, 0, ..., 0) Diese heisst Standardbasis.

5.4.8 Bemerkung

Sei ϕ : V →W ein linearer Isomorphismus, v1, ..., vn ∈ VDann · v1, ..., vn linear unabhangig ⇔ ϕ(v1), ..., ϕ(vn) linear unabhangig

· v1, ..., vn erzeugt V ⇔ ϕ(v1), ..., ϕ(vn) erzeugt W

· (v1, ..., vn) Basis von V ⇔ (ϕ(v1), ..., ϕ(vn)) Basis von W

ϕ : V →W linearer Isomorphismus

v1, ..., vn erzeugt V

Beh.: ϕ(v1), ..., ϕ(vn) erzeugt V

Beweis: Sei w ∈W . Es gibt v ∈ V mit ϕ(v) = w

Es gibt λ1, ..., λn ∈ Kmit λ1v1 + ...λnvn = v

Also λ1ϕ(v1) + ...+ λnϕ(vn) = ϕ(λ1v1 + ...+ λnvn) = ϕ(v)

Also ist ϕ(v) Linearkombination von ϕ(v1), ..., ϕ(vn)

5.4.9 Proposition

Seien e1, ..., en ∈ V . Aquivalent sind:

(1) (e1, ..., en) Basis von V

(2) Jedes v ∈ V lasst sich eindeutig, schreiben als

V = ξ1e1 + ...+ ξnen mit ξi ∈ K(3) Die lineare Abbildung

ϕ : Kn → V , (ξ1, ..., ξn) 7→ ξ1e1 + ...+ ξnen

ist ein Isomorphismus

Beweis: (1)⇒ (2)

Sei v ∈ V Da e1, ..., en V erzeugt ⇒ ∃ξ ∈ Kn mit v = ξ1e1 + ...+ ξnen

Eindeutigkeit: Ware auch v = λ1e1 + ...+ λnen, λi ∈ K⇒ 0 = v − v = (λi − ξ1)e1 + ...+ (λn − ξn)en

e1, ..., en linear unabhangig ⇒ ∀iλi − ξi = 0, d.h. λi = ξi

(2)⇒ (1)


Lineare Algebra I


Vorlesung 25


Michael Habermann

[email protected]

Klar: e1, ..., en ergeugt V

Sei 0 = λ1e1 + ...+ λnen, λi ∈ K0 = 0 · e1 + ...+ 0 · en

⇒ ∀iλi = 0 Also e1, ..., en linear unabhangig

(2)⇔ (3)

(2)⇔ ϕ bijektiv ⇔ ϕ linearer Isomorphismus


Lineare Algebra I


Vorlesung 26


Michael Habermann

[email protected]

Wiederholung:

V K-VR, vi ∈ VDef: (v1, ..., vn) heisst Basis von V , falls

(1) v1, ..., vn erzeugen V

(2) v1, ..., Vn linear unabhangig

Beispiel: V = Kn hat die Basis

(e1, ..., ei), wobei ei = (0, ..., 0, 1, 0, ..., 0) Standardbasis

5.4.10 Definition

Ein K-VR V heisst endlich erzeugt, falls ∃M ⊆ V endlich

und span(M) = V

5.4.11 Korrolar

Vektoren v1, ..., vn ∈ Kq mit n > q sind linear abhangig

5.4.12 Theorem

Sei V ein endlich erzeugter Vektorraum. Dann

(1) V besitzt eine Basis. Genauer: Jede V erzeugte Menge enthalt eine Basis

(2) Je zwei Basen sind gleichmachtig. Genauer:

e1, ..., en linear abhangig

f1, ..., fq erzeugen V

⇒ n ≤ q0.2cm] Beweis in Teilschritten:

(1a) Jede endliche erzeugende Menge enthalt eine Basis.

Sei M ⊆ V , M endlich, span(M) = V

Dann gibt es e1, ..., en ∈M mit spane1, ..., en = V und

∀i spane1, ..., ei−1, ei+1, ..., en 6= V

Beh.: e1, ..., en linear unabhangig

Beweis: Angenommen e1, ..., en linear abhangig

Dann oBdA ∃λ2, ..., λn ∈ K e1 = λ2e2 + ...+ λnen

⇒ V = spane1e2, ..., en = spane2, ..., enWird zur Minimalitat // (Beh)

(1b) Jede V erzeugende Menge M enthalt eine endliche erzeugende Teilmenge

Sei V erzeugt von f1, ..., fq (existiert nach Vor!)

∃e1, ..., em ∈M ∀i fi ist Linearkombination der e1, ..., em

Also V = spanf1, ..., fq ⊆ spane1, ..., em⇒ V = spane1, ..., em //

(2) Gemaß Teil (1a) genugt es folgendes zu zeigen:


Lineare Algebra I


Vorlesung 26


Michael Habermann

[email protected]

(e1, ..., en) linear unabhangig

(f1, ..., fq) Basis von V

⇒ n ≤ qNun ist ϕ : Kq → V , ξ 7→ ξ1f1 + ...+ ξqfq

ein lineareer Isomorphismus. Dann sind (Bem)

Kq ∋ ϕ−1(e1), ..., ϕ−1(en) linear unabhangig

⇒ n ≤ q //

5.4.13 Definition

Die Dimension dim(V ) eines endlich erzeugten K-Vektorraums ist definiert als die

(gemeinsame) Kardinalitat siner Basen.

Wir setzen dim(V ) =∞, falls V nicht endlich erzeugt ist.

5.4.14 Beispiel

dim(Kn) = n

5.4.15 Bemerkung

V endlich dimensional ⇔ V endlich erzeugt.

5.4.16 Korrolar (Klassifikation endlich-dimensionaler VR)

Seien V,W endlich dimensionale K-VR

Dann V ≃W ⇔ dim(V ) = dim(W )

Insbesondere V ≃ Kn ⇔ dim(V ) = n

Beweis: (1) V ≃W ⇒ dim(V ) = dim(W )

(e1, ...en) Basis von V , ϕ : V →W linearer Isomorphismus

(ϕ(e1), ..., ϕ(en)) Basis von W . Also dim(V ) = n = dim(W )

(2) Sei dim(V ) = n Dann existiert (e1, ..., en) Basis von V .

Dann ist ϕ : Kn → V , ξ 7→ ξ1e1 + ...+ xnen ein

linearer Isomorphismus

Also Kn ≃ V(3) dim(V ) = dim(W ) = n

(2)⇒ V ≃ Kn ⇒ V ≃W //

5.4.17 Beispiel

(1) E0 ≃ R2 dim(E0) = dim(R2) = 2

R0 ≃ R3 dim(R0) = dim(R3) = 0

Allgemein, heissen VR der Dimension 1 Geraden

Allgemein, heissen VR der Dimension 2 Ebenen


Lineare Algebra I


Vorlesung 26


Michael Habermann

[email protected]

(2) C als R-VR hat Basis (1, i)

dimRC = 2

(2’) C als C-VR dimCC = 1

(3) R als Q-VR nicht endlich erzeugt. dimQR =∞Beweis: Ware dimQR = n <∞

⇒ R ≃ Qn (als Q-VR)

Da Qn abzahlbar ist ⇒ R abzahlbar // Aber dimRR = 1

(4) dim(V ) = 0 ⇔ V = 0

5.4.18 Be.., merkung

Sei dim(V ) = n <∞, (e1, ..., en) Basiss von V

Dann ist ϕ : Kn → V , ξ = (ξ1, ..., ξn) 7→n∑

i=1

ξiei = v

ein linearer Isomorphismus. Sei v ∈ V Dann heisst

ξ = ϕ−1(v) der Koordinatenvektor von v bzgl. der Basis (e1, ..., en)

ξi heisst i-te Koordinate von v bzgl. (e1, ..., en)

5.4.19 Korollar

Sei dim(V ) = n <∞(1) Mehr als n Vektoren sind immer linear abhangig

(2) Weniger als n Vektoren erzeugen V nie

Beweis: Sei (e1, ..., en) Basis von V . Verwende Theorem

(e′1, ..., e′m) linear unabhangig ⇒ m ≤ n

f1, ..., fq erzeugen V ⇒ n ≤ q //

5.4.20 Satz (Basiserganzungssatz)

Sei dim(V ) <∞, e1, ..., em ∈ V linear unabhangig. Dann ibt es

em+1, ..., em+r ∈ V so, dass (e1, ..., em, em+1, ..., em+r) Basis von V ist.

Beweis: Sei e1, ..., em ⊆M ⊆ V , M linear unabhangig

mit |M | Maximal. (Existiert, da |M | ≤ dim(V ))

Schreibe M = e1, ..., em, em+1, ..., em+rNach Vor. ist e1, ..., em+r linear unabhangig

Genugt zu zeigen e1, ..., em+r erzeugen V

Sei v ∈ V Max ⇒ (e1, ..., em+r, v) linear abhangig

⇒ ∃λ1, ..., λm+r, λ0 ∈ Km+r∑

i=1

λiei + λ0v = 0 ein λi 6= 0

Es gilt λ0 6= 0 (sonst e1, ..., em+r linear abhangig)


Lineare Algebra I


Vorlesung 26


Michael Habermann

[email protected]

⇒ v ∈ spane1, ..., em+r Da v ∈ V belibig

⇒ V = spane1, ..., em+r

5.4.21 Korrolar

Sei dim(V ) = n <∞, e1, ..., en ∈ V Aquivalent sind

(1) e1, ..., en linear unabhangig

(2) e1, ..., en erzeugen V

(3) e1, ..., en Basis von V

Beweis: (1) ⇒ (2)

Basiserganzungssatz und Invasierung der Dimension

(2) ⇒ (3)

Basisauswahl und Invasierung der Dimension

(3) ⇒ (1) trivial //


Documents

Lineare Algebra I - Prof. Bürgisser - WS 2007 / 08