Kurs:Lineare Algebra II/Zusammenstellung: Einfache algebraische Strukturen

Ein Vorzug algebraischer Methoden besteht darin, dass viele Standard-Konstruktionen und Standard-Aussagen in verschiedenen Zusammenhängen anwendbar sind. Dies kann das Verständnis erleichtern und den Blick für das Wesentliche schärfen. Nach mehr als einem Semester linearer Algebra haben wir mehr Beispiele und neue Erkenntnisse angesammelt. Wir wollen von dieser Warte aus nochmals auf die Grundbegriffe der Algebra blicken.

Gruppen, Untergruppen und Homomorphismen

Der Begriff der Gruppe entsteht aus der Betrachtung von Symmetrien eines geometrischen Objektes. Symmetrien sind bijektive Abbildungen des Objektes auf sich. Die Verknüpfung von Symmetrien ergibt wieder Symmetrien und ist assoziativ.

Begriffe und Beispiele

Die Gruppe ist die wichtigste algebraische Struktur mit nur einer Operation.

Definition 4.1

Eine Menge mit einer Operation $(G,\circ )$ heißt Gruppe, wenn die Operation $\circ :G\times G\to G$ die folgenden Regeln erfüllt:

$(i_{1})$ Assoziativität: $x\circ (y\circ z)=(x\circ y)\circ z$ gilt für alle $x,y,z\in G$,

$(i_{2})$ Existenz eines (links-) neutralen Elementes: $\exists e\in G:e\circ x=x$ für alle $x\in G$,

$(i_{3})$ Existenz eine (Links-)Inversen: zu jedem $x\in G,\exists x'\in G$: $x'\circ x=e$.

Neutrales und Inverses sind stets eindeutig und rechtsneutral bzw. rechtsinvers. In der multiplikativen Schreibweise bezeichnet $x^{-1}$ das Inverse von $x$ (in der additiven Schreibweise ist es $-x$). Ist die Operation kommutativ, so sprechen wir von einer kommutativen oder Abelschen Gruppe.
Test: $(g\circ h)^{-1}=h^{-1}\circ g^{-1}$.

Zu jeder Struktur gibt es die zugehörige Unterstruktur und eine zugehörige Klasse von Abbildungen, genannt Homomorphismen.

Definition 4.2

Eine nicht leere Teilmenge $H\subset G$ einer Gruppe $G$ ist eine Untergruppe, wenn $H$ mit der Einschränkung der Operation von $G$ auf $H$ selbst eine Gruppe ist.

Test: $H\subset G$ ist eine Untergruppe gdw. $\forall x,y\in H:x\circ y^{-1}\in H$.

Definition 4.3

Ein (Gruppen)-Homomorphismus von Gruppen $G,G'$ ist eine Abbildung $\varphi :G\to G'$ mit der Eigenschaft:

$\varphi (x\circ y)=\varphi (x)\circ \varphi (y)$.

Test: Für jeden Gruppenhomomorphismus gilt: (1) $\varphi (e_{G})=e_{G'}$ und (2) $\varphi (g^{-1})=(\varphi (g))^{-1}$.
Der Kern von $\varphi$ ist eine Untergruppe von $G$: $ker(\varphi ):=\varphi ^{-1}(e)$.
Das Bild von $\varphi$ ist eine Untergruppe von $G'$: $im(\varphi ):=\varphi (G)$.

Typische Beispiele sind:

• $(\mathbb {Z} ,+)$ – die additive Gruppe der ganzen Zahlen.
• $(K,+)$ – die additive Gruppe eines Körpers.
• $(K^{n},+)$ – die additive Gruppe der $n$-Tupel von Körperelementen (des $n$-dimensionalen Standard-Vektorraumes).
• $(K\setminus \{0\},\cdot )$ – die multiplikative Gruppe eines Körpers.
• $(\mathbb {Z} /\mathbb {Z} n,+)$ – die additive Gruppe der Reste modulo $n$.
• $(S_{M},\circ )$ – die symmetrische Gruppe einer Menge $M$ besteht aus den Bijektionen von $M$ auf sich. Die Verknüpfung ist die Hintereinanderausführung von Abbildungen (nicht kommutativ für $|M|>2$ !). Insbesondere bezeichnet $S_{n}:=S(\{1,...,n\})$ die $n$-te Permutationsgruppe.
• $(Gl_{n}(K),\cdot )$ – die lineare Gruppe (oder Matrixgruppe) aller regulären $n\times n$-Matrizen bzgl. der Matrixmultiplikation.
• Die folgenden Teilmengen sind Untergruppen von $Gl_{n}$:

$Sl_{n}:=\{A\in Gl_{n}|\det(A)=1\}$ (spezielle lineare Gruppe),

$D_{n}:=\{A\in Gl_{n}|a_{ij}=0\ \mathrm {f{\ddot {u}}r} \ i\neq j\}$ (Diagonalmatrizen),

$\triangle _{n}:=\{A\in Gl_{n}|a_{ij}=0\ \mathrm {f{\ddot {u}}r} \ i>j\}$ (obere Dreiecksmatrizen).

• $(Aut(G),\circ )$ - die Menge aller bijektiven Homomorphismen einer Gruppe auf sich (genannt Automorphismen) bildet eine Gruppe (Untergruppe von $S(G)$) bzgl. der Verknüpfung von Abbildungen.
• Die Zuordnung $n\mapsto {\overline {n}}$ ist ein Homomorphismus $\mathbb {Z} \to \mathbb {Z} /\mathbb {Z} n$.
• Die Exponentialabbildung $\exp :\mathbb {Z} \to \mathbb {R} ^{*},n\mapsto e^{n}$ ist ein Homomorphismus der additiven Gruppe in die multiplikative Gruppe $\mathbb {R} ^{*}=\mathbb {R} \setminus \{0\}$. Eine Verallgemeinerung ist die Abbildung $\varphi _{x}:\mathbb {Z} \to G$, definiert für jedes $x\in G$ durch $n\mapsto x^{n}$. Bezeichnung: $\langle x\rangle :=im(\varphi _{x})$ - die von $x$ erzeugte (zyklische) Untergruppe.
• $I:G\to Aut(G)$ ist ein Homomorphismus definiert durch $I(g):=\tau _{g}\in Aut(G),\tau _{g}:x\mapsto gxg^{-1},g$ heißt Konjugation mit $g$.

Test: Man finde alle Untergruppen von $\mathbb {Z}$.
Test: Man finde jeweils Kern und Bild der Homomorphismen.

Lemma 4.4

Sei $G$ endliche Gruppe und $H$ eine Untergruppe, dann ist $\#(H)$ ein Teiler von $\#(G)$.

Zum Beweis wird gezeigt, dass $x\sim _{H}y$, definiert durch $xy^{-1}\in H$, eine Äquivalenzrelation ist und die zugehörigen Äquivalenzklassen $Hx$ (rechte Nebenklassen) jeweils die gleiche Anzahl von Elementen besitzen.
Insbesondere ist dann $ord(g):=\#(\langle x\rangle )$ ein Teiler von $n:=\#(G)$, wenn $G$ endlich ist.
Test: $g^{n}=e$ für alle $g\in G$.

Normalteiler, Quotientengruppe und Homomorphiesatz

In einer nicht kommutativen Gruppe sind i.a. linke und rechte Nebenklassen einer Untergruppe verschieden. Soll aber $(Hx)\cdot (Hy)$ wieder eine Nebenklasse sein und zwar $Hxy$, benötigen wir die Gleichheit $xH=Hx$.

Definition 4.5

Eine Untergruppe $N$ von $G$ heißt Normalteiler, wenn $xN=Nx$ für alle $x\in G$. Die Menge der Nebenklassen bzgl. eines Normalteilers $G/N:=\{Nx|x\in G\}$ ist die Quotientengruppe von $G$ nach $N$, die Operation ist definiert durch $Nx\cdot Ny:=Nxy$.

In diesen Sinne ist $\mathbb {Z} /\mathbb {Z} n$ die Quotientengruppe von $\mathbb {Z}$ nach der Untergruppe $\mathbb {Z} n$. Die Quotientengruppe eines Vektorraumes $V$ nach einem Untervektorraum $U$ bildet dann zun¨achst eine kommutative Gruppe $(V/U,+)$. Diese wird zum (Faktor-)Vektorraum durch $r(Ux):=U(rx)$.
Test: Zeige $\dim(V/U)=\dim(V)-\dim(U)$.
Test: Der Kern eines Homomorphismus ist stets ein Normalteiler; dies gilt i.a. nicht für das Bild.
Von universeller Bedeutung ist die folgende Aussage.

Satz 4.6 (Homomorphiesatz)

Sei $\varphi :G\to H$ ein Homomorphismus von Gruppen, dann induziert $\varphi$ einen Isomorphismus ${\overline {x}}\mapsto \varphi (x)$ der Gruppen: ${\overline {\varphi }}:G/ker(\varphi )\cong im(\varphi )$.

Permutationsgruppen

Die Permutationsgruppen $S_{n}$ sind die wichtigsten endlichen und nicht-kommutativen $(n>2)$ Gruppen. Es gelten die folgenden Eigenschaften:

• Es gibt $n!$ Permutationen.

• Jede Permutation ist Produkt von Transpositionen (Darstellung nicht eindeutig).

• Jede Permutation ist Produkt von paarweise elementfremden Zyklen (eindeutig bis auf Reihenfolge der Faktoren). Ein Zyklus $z=(k_{1},k_{2},...,k_{r})$ bildet ab $k_{1}\mapsto k_{2}\mapsto ...\mapsto k_{r-1}\mapsto k_{r}\mapsto k_{1}$.

• Die Ordnung einer Permutation ist der kgV ihrer Zyklenlängen.

• Zwei Permutationen sind konjugiert (d. h. sie lassen sich durch eine Konjugation ineinander überführen) gdw. die Längen der Zyklen ihrer Produktdarstellungen übereinstimmen.

Test: Jede endliche Gruppe aus $n$ Elementen ist isomorph zu einer Untergruppe von $S_{n}$ durch $g\mapsto \sigma _{g},\sigma _{g}(x):=gx$.
Zur Herleitung der Leibniz-Formel für Determinanten haben wir die folgende Aussage zum Signum einer Permutation benötigt:

Satz 4.7

Es gibt eine eindeutig bestimmt Abbildung $\operatorname {sgn} :S_{n}\to \{1,-1\}$ mit den Eigenschaften: (1) $\operatorname {sgn}((p,q))=-1$ und (2) $\operatorname {sgn}(\tau \sigma )=\operatorname {sgn}(\tau )\operatorname {sgn}(\sigma )$. Insbesondere gilt die Formel: $\operatorname {sgn}(\sigma )=\prod _{i<j}{\frac {x_{\sigma (i)}-x_{\sigma (j)}}{x_{i}-x_{j}}}=\prod _{i<j}{\frac {\sigma (i)-\sigma (j)}{i-j}}$.
$A_{n}:=ker(\operatorname {sgn} )$ heißt alternierende Gruppe und ist ein Normalteiler der $S_{n}$.

Information: Endlich erzeugte Abelsche Gruppe

Notationen:

• Die ’einfachste’ Abelsche Gruppe ist $\mathbb {Z}$. Die Untergruppen von $\mathbb {Z}$ sind von der Form $\mathbb {Z} n$, die Faktorgruppen $\mathbb {Z} /\mathbb {Z} n$ sind die zyklischen Gruppen, d. h. Gruppen, die von einem Element erzeugt sind.

• Für ein Element $a\in A$ einer Abelschen Gruppe $(A,+)$ und $n\in \mathbb {N}$ bezeichne $na:=a+...+a$ die $n$-fache Summe von $a$, resp. $(-n)a:=(-a)+...+(-a)$.

• Die Gruppe $A$ wird von $k$ Elementen $a_{1},...,a_{k}$ erzeugt, wenn jedes Element $x\in A$ eine Darstellung $x=n_{1}a_{1}+...+n_{k}a_{k}$ hat (bzw. wenn es einen surjektiven Homomorphismus $\varphi :\mathbb {Z} ^{k}\to A,(n_{1},...,n_{k})\mapsto \sum _{i}n_{i}a_{i}$ gibt).

• A heißt frei, wenn $\mathbb {Z} ^{k}\cong A$ ist (oder $ker(\varphi )=0$).

• Sind $B,C\subset A$ zwei Untergruppen von $A$, dann ist $A=B\oplus C$ eine direkte Summe, wenn jedes Element $a\in A$ eine eindeutige Zerlegung $a=b+c,b\in B$ und $c\in C$, besitzt.

Lemma 4.8

Für eine Abelsche Gruppe $(A,+)$ sind

$T(A):=\{x\in A|na=0\ f{\ddot {u}}r\ ein\ n>0\}$ und $T_{p}(A):=\{x\in A|p^{n}a=0\ f{\ddot {u}}r\ ein\ n>0\}$,

$p$ prim, Untergruppen von $A$, genannt Torsionsgruppe von $A$ bzw. $p$-Torsionsgruppe.

Es gelten die folgenden Strukturaussagen:

Satz 4.9

Ist $(A,+)$ eine endlich erzeugte Abelsche Gruppe, dann gilt:

$(i_{1})$ $A/T(A)$ ist frei,

$(i_{2})$ $T(A)=\bigoplus T_{p}(A)$ und $T_{p}(A)$ ist direkte Summe zyklischer Gruppen von $p$-Potenzordnung,

$(i_{3})$ $A\cong (A/T(A))\oplus T(A)$.

Ringe, Hauptidealringe und Euklidische Ringe

Ring: Begriff und Beispiele

Die wichtigste algebraische Struktur mit zwei Verknüpfungsoperationen ist der Ring.

Definition 4.10

Ein Ring $(R,+,\cdot )$ ist eine Menge mit zwei Operationen Addition und Multiplikation, mit folgenden Regeln:

$(i_{1})$ $(R,+)$ ist eine Abelsche Gruppe.

$(i_{2})$ Die Multiplikation ist assoziativ.

$(i_{3})$ Es gilt das Distributivgesetz (beidseitig).

Zusatz: Ein Ring heißt kommutativ mit $1$, wenn die Multiplikation kommutativ ist und ein (multiplikativ) neutrales Element $1$ existiert.
Unterring und Ringhomomorphismus werden analog zu den Definitionen (4.2) und (4.3) eingeführt. Achtung: Ist $\varphi :R\to R'$ ein Homomorphismus von Ringen mit 1, dann wird zusätzlich $\varphi (1_{R})=1_{R'}$ gefordert!
Frage: Warum folgt aus den Homomorphismus-Axiomen stets $\varphi (0)=0$, aber nicht notwendig $\varphi (1)=1$?
Wir wollen hier vor allem kommutative Ringe mit 1 betrachten. Insbesondere werden die Eigenschaften der ganzen Zahlen $\mathbb {Z}$ und des Polynomenringes $K[x]$ verallgemeinernd zusammengefasst.
Die wichtigste Unterstruktur sind die Ideale (spezielle Unterringe):

Definition 4.11

Eine nicht leere Teilmenge $I\subset R$ eines Ringes heißt Ideal, wenn $I+I=I$ und $R\cdot I=I$.

Beispiel: Die Vielfachen eines Ringelementes $a\in R$ bilden ein Ideal: $I=(a):=R\cdot a$, genannt Hauptideal erzeugt von $a$. Aber nicht jedes Ideal ist Hauptideal. So ist im Ring $R=K[x,y]$ (Polynome in zwei Variablen) die Menge $I=(x,y):=Rx+Ry$ ein Ideal, aber kein Hauptideal.
Test: Ein Körper besitzt nur die trivialen Ideale $(0)$ und $K=(1)$.
Test: Ist $\varphi$ ein Ringhomomorphismus, dann ist $ker(\varphi ):=\varphi ^{-1}(0)$ ein Ideal.

Lemma 4.12

$(a)=R$ gdw. $a$ hat in $R$ ein multiplikatives Inverses.

Ein solches Element heißt Einheit von $R$. Die Einheiten von $\mathbb {Z}$ sind $\{1,-1\}$, die Einheiten von $K[x]$ sind die konstanten Polynome ohne 0.
Test: Die Menge aller Einheiten in einem Ring bildet bzgl. der Multiplikation eine Gruppe (bezeichnet mit $R^{*}$).
Für einen Körper ist $K=K\setminus \{0\}$.
Ein Ring heißt nullteilerfrei, wenn aus $xy=0$ stets $x=0$ oder $y=0$ folgt. $\mathbb {Z}$ ist nullteilerfrei.
Test: Ein Körper $K$ und der Ring $K[x]$ ist nullteilerfrei. $\mathbb {Z} /\mathbb {Z} n$ ist nullteilerfrei gdw. $n$ ist eine Primzahl.

Teilbarkeit in Hauptidealringen

Wir wollen die Begriffsbildungen der Teilbarkeit von $\mathbb {Z}$ übertragen. Dazu ist es sinnvoll die Nullteilerfreiheit und die Hauptidealeigenschaft vorauszusetzen.

Definition 4.13

Ein Ring, der nullteilerfrei ist, d. h. $xy=0\Rightarrow (x=0\vee y=0)$ und in dem alle Ideale von einen Element erzeugt sind, heißt Hauptidealring.

Wir sehen, dass die folgenden Begriffe in der Sprache der Ideale oft einfacher zu beschreiben sind.

Definition 4.14

Seien $a,b,c,d\in {R}$ Elemente in einem nullteilerfreien Ring:

• $b$ ist Teiler von $a$, schreibe $b|a$, wenn $a=bc$, d.h. $(a)\subseteq (b)$.
• $b$ ist echter Teiler von $a$, wenn $b|a$ und $b$ keine Einheit und $a$ kein Teiler von $b$, d.h. $(a)\subset (b)$.
• $a$ heißt irreduzibel, wenn $a$ keine Einheit ist und keine echten Teiler besitzt, d.h. $(a)\subset R$ ist ein maximales Ideal.
• $a$ heißt prim, wenn gilt $(a|bc\Rightarrow a|b\ oder\ a|c)$, d.h. $R/(a)$ ist nullteilerfrei.
• $c$ heißt größter gemeinsamer Teiler von $a$ und $b$, schreibe $c=ggT(a,b)$, wenn $c|a$ und $c|b$ und $((d|a\ und\ d|b)\Rightarrow d|c)$, d.h. $(a,b)=(d)$.
• $a$ und $b$ heißen teilerfremd, wenn $ggT(a,b)$ eine Einheit ist, d.h. $(a,b)=(1)$.
• $c$ heißt kleinstes gemeinsames Vielfaches von $a$ und $b$, schreibe $c=kgV(a,b)$, wenn $a|c$ und $b|c$ und $((a|d\ und\ b|d)\Rightarrow c|d)$, d.h. $(a)\cap (b)=(c)$.

Damit ergibt sich unmittelbar aus den Definitionen:

Lemma 4.15

In einem Hauptidealring existieren $ggT$ und $kgV$.

Lemma 4.16

$\mathbb {Z}$ und $K[x]$ sind Hauptidealringe.

Dies folgt aus der Division mit Rest.
Üblicherweise nennen wir eine positive irreduzible Zahl Primzahl. Tatsächlich ist leicht einzusehen, dass jedes prime Element irreduzibel ist. Die Umkehrung gilt nach unserer Erfahrung in $\mathbb {Z}$. Der allgemeine Fall ist zu beweisen.

Satz 4.17 (Lemma von Euklid)

Im Hautidealring ist jedes irreduzible Element prim, (also prim = irreduzibel).

Aus $p|xy$ und nicht $p|x$ folgt $1=ggT(p,x)$ und somit eine Darstellung $1=sp+tx$. Daraus erhalten wir nach Multiplikation mit $y$, daß $p$ ein Teiler von $y$.

Corollar 4.18

Jedes Element $x\in R$ in einem Hauptidealring ist Produkt von endlich vielen Primelementen. Die Produktzerlegung ist eindeutig bis auf die Reihenfolge der Faktoren und eine Einheit.

Idee: Jedes Element ist Produkt endlich vieler irreduzibler Elemente (im Hauptidealring). Mit Induktion über die Anzahl der Faktoren und der Primeigenschaft folgt die Behauptung.
Allerdings sind die letzten beiden Beweise nicht konstruktiv und es hängt vom Ring ab, ob und wie die Faktorisierung oder der $ggT$ zu bestimmen ist. In $\mathbb {Z}$ kennen wir den Euklidischen Algorithmus, für seine Verallgemeinerung benötigen wir zusätzlich eine Ordnungsfunktion.

Euklidische Ringe und euklidischer Algorithmus

Eine effektive Bestimmung des $ggT$ wird mittels einer Division mit Rest bzgl. einer Ordnungsfunktion möglich:

Definition 4.19

Ein nullteilerfreier Ring heißt euklidisch, wenn es bzgl. einer Ordnungsfunktion $o:R\setminus \{0\}\to \mathbb {N}$ auf $R$ eine Division mit Rest gibt, d.h. zu je zwei Ringelementen $a,b\in R,b\neq 0$, existieren Ringelemente $q,r\in R$, so daß $a=qb+r$ mit $o(r)<o(b)$ oder $r=0$.

Beispiele:
$\mathbb {Z}$ ist euklidischer Ring mit der Ordnungsfunktion ’Betrag’.
$K[X]$ ist euklidscher Ring mit der Ordnungsfunktion ’degree’ und
$\mathbb {Z} [i]$ mit der Norm $N(a+bi):=a^{2}+b^{2}$.
Test: Jeder Körper $K$ ist euklidischer Ring.
Wie im Fall von $\mathbb {Z}$ und $K[x]$ (siehe 1.12) zeigt man allgemein:

Lemma 4.20

Ein euklidischer Ring ist Hauptidealring. Insbesondere wird jedes Ideal $I$ von einem Element minimaler Ordnung in $I$ erzeugt.

Eine iterierte Division mit Rest führt zum Euklidischen Algorithmus:

INPUT: $a,b\in \mathbb {Z}$
OUTPUT: $ggT(a,b)$
   c = 1;
   WHILE ($c\neq 0$)
   {c = a − div(a, b) b; a = b; b = c; }
   return(a);

Dabei bezeichne div die Prozedur, die den Quotienten bei der ’Division mit Rest’ zurückgibt.

Satz 4.21

Der Euklidische Algorithmus ist endlich und bestimmt den $ggT$.

Die beiden folgenden Anwendungen des Euklidischen Algorithmus zur Bestimmung des multiplikativen Inversen in $\mathbb {Z} /\mathbb {Z} n$ und zur Lösung des chinesischen Restsatzes funktionieren natürlich auch in $R/(a)$, wenn $R$ ein beliebiger Euklidischer Ring:

Lemma 4.22

$ax\equiv b(n)$ besitzt für $a$ und $b$ genau dann eine Lösung $x$, wenn $ggT(a,n)|b$.

Sei $ggT(a,n)=:d=sa+tn$ und $b=kd$, dann ist $x=ka$ eine Lösung. Umgekehrt, wenn eine Lösung existiert, ist $b\in (a,n)=(d)$, also $d|b$.
Daraus ergibt sich der Chinesische Restsatz:

Corollar 4.23

Seien $n_{1},...,n_{r}\in \mathbb {Z}$ paarweise teilerfremd und sei $n=n_{1}\cdot ...\cdot n_{r}$, dann besitzt das System simultaner Kongruenzen

$x\equiv b_{i}(n_{i}),\quad i=1,...,r$

für beliebige $b_{1},...,b_{r}\in \mathbb {Z}$ eine eindeutige Lösung $x$ in $\mathbb {Z} /n\mathbb {Z}$.

Es gilt: $N_{i}:=n/n_{i}$ ist teilerfremd zu $n_{i}$. Sei $x_{i}$ eine Lösung der Kongruenz $N_{i}x_{i}\equiv b_{i}(n_{i})$. Dann löst $x:=\sum _{i}N_{i}x_{i}=N_{1}x_{1}+...+N_{r}x_{r}$ die simultanen Kongruenzen.
Bemerkung: Damit gelten die folgenden Inklusionen von ’Kategorien’:

$\{\mathrm {K{\ddot {o}}rper} \}\subset \{{\text{Euklidische Ringe}}\}\subset \{{\text{Hauptidealringe}}\}\subset \{{\text{nullteilerfreie Ringe}}\}\subset \{{\text{Ringe}}\}$