Lineare Algebra - Mitschrift - Hanke/0 Grundlagen

Aus Infostudium Wiki

Wechseln zu: Navigation, Suche

Hoch zu Inhaltsverzeichnis

Vor zu Kapitel 1: Lineare Gleichungssysteme

Inhaltsverzeichnis

1 Abbildungen
2 Körper
3 Gruppen und Ringe
4 Signum einer Permutation

Abbildungen

(0.1) Definition (Abbildung)

Seinen $M, N$ Mengen. Eine Abbildung $f$ von $M$ nach $N$ ordnet jedem $x \in M$ ein Element $f (x) \in N$ zu, geschrieben:

$f : M \rightarrow N, x \mapsto f (x)$

$\left. \begin{array}{c} M \text{ Definitionsbereich}\\ N \text{ Wertebereich} \end{array} \right\}$ Immer mit angeben

$f (x) \in N$ ist das Bild von $x \in M$

$x \in M$ heißt ein Urbild von $y = f (x) \in N$

(0.2) Beispiele (zu 0.1)

$f : \mathbb{N} \rightarrow \mathbb{R}, i \mapsto i^2$
Eine Abbildung mit Def. Bereich $\mathbb{N}$ heißt Folge, geschrieben
$a_1, a_2, \ldots a_n \operatorname{mit} a_i = f (i)$
Die Addition in $\mathbb{Z}$ ist die Abbildung
$\mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}, (a, b) \mapsto a + b (a, b) \in \mathbb{Z}$
Sei $M$ eine Menge
$\operatorname{id}_M = M \rightarrow M, x \mapsto x$ heißt Identität
Für $n \in \mathbb{N}$ sei $\underline{n} := \{1, 2, \ldots, n\}$
zB. $f : \underline{3} \rightarrow \mathbb{R}, f (1) = 0, f (2) = \sqrt{3}, f (3) = - \frac{1}{2}$
Eine Abbildung mit Def. Bereich $\underline{n}$ heißt n-Tupel, geschrieben
$(a_1, a_2, \ldots, a_n)$ mit $a i = f (i)$ , also hier: $\left( 0, \sqrt{3}, - \frac{1}{2} \right)$
2-Tupel heißt Paar, 3-Tupel heißt Tripel

(0.3) Bemerkung (zu 0.1)

Zwei Abbildungen $f : M \rightarrow N$ und $g : M' \rightarrow N'$ sind gleich (geschrieben $f = g$ ) wenn

$M = M'$
$N = N'$
$\forall x \in M$ ist $f (x) = g (x)$

(0.4) Definition (Eigenschaften von Abbildungen)

Sei $f : M \rightarrow N$ eine Abbildung, sei $X \subset M, Y \subset N$

$f (x) := \{f (x) |x \in X\} \subset N$ heißt Bild von X
$f^{- 1} (Y) := \{x \in M|f (x) \in Y\}$ heißt Urbild von Y
Die Mengen $f^{- 1} (\{y\}) \subset M (y \in N)$ heißen Fasern von f
$f$ heißt surjektiv, wenn $f (M) = N$
$f$ heißt injektiv, wenn $\forall x, x' \in M :$ wenn $x \neq x'$ dann $f (x) \neq f (x')$
$f$ heißt bijektiv, wenn $f$ surjektiv und injektiv
Die Teilmenge von $M \times N$ : $G_j := \{(x, y) |x \in M, y = f (x)\}$ heißt Graph von $f$

(0.5) Bemerkung (zu 0.4)

Für $f : M \rightarrow N$ sind äquivalent:

$f$ ist injektiv
Sind $x, x' \in M$ mit $f (x) = f (x')$ dann $x = x'$
jede Faser von $f$ hat höchstens ein Element
$\forall y \in N$ hat die Gleichung $f (x) = y$ höchstens eine Leosung für $x \in M$

Ebenso äquivalent

$f$ ist surjektiv
Jede Faser von $f$ ist nicht leer
$\forall y \in N$ hat die Gleichung $f (x) = y$ mindestens eine Lösung

Außerdem äquivalent

$f$ ist bijektiv
Jede Faser von $f$ hat genau ein Element
$\forall y \in N$ hat die Gleichung $f (x) = y$ genau eine Lösung

(0.6) Beispiele (zu 0.4)

Hashfunktion/Checksumme/Fingerprint
$\operatorname{md} 5 : \{\operatorname{Texte}\} \rightarrow 2^{128}$
kann nicht injektiv, sollte surjektiv sein und ``gleich große Fasern haben
Verschluesselung
$\operatorname{crypt} : 2^k \rightarrow 2^k$
muß bijektiv sein

Auslassung: Weiterführendes Beispiel

(0.7) Definition (Umkehrabbildung)

Sei $f : M \rightarrow N$ bijektiv.

Die Abbildung $N \rightarrow M, y \rightarrow$ eindeutige Lösung von $x \in M$ von $f (x)$ heißt Umkehrabbildung von $f$ .

Achtung: $\underset{\in M}{\underbrace{f^{- 1} (x)}}$ heißt nicht $\underset{\in N}{\underbrace{f (x)^{- 1}}}$

(0.8) Definition (Komposition)

Seien $g : L \rightarrow M, f : M \rightarrow N$ Abbildungen. Die Abbildung

$f \circ g : L \rightarrow N, x \rightarrow f \circ g (x) := f (g (x))$

wird Komposition von $f$ mit $g$ genannt.

Achtung: Bildbereich von $g$ = Def. Bereich von $f$

(0.9) Beispiel (zu 0.7, 0.8)

$f : M \rightarrow N$ bijektiv

$f \circ f^{- 1} = \operatorname{id}_N$ und $f^{- 1} \circ f = \operatorname{id}_M$

(0.10) Satz

Sind $f, g$ bijektiv, dann sind $f \circ g$ bijektiv und $(f \circ g)^{- 1} = g^{- 1} \circ f^{- 1}$

(0.11) Beispiel (zu 0.7, 0.8, 0.10)

Sei $n \in N, a \in \mathbb{Z}$ und $\mathbb{Z}_n =\{0, 1, \ldots, n - 1\}$
Ist $\operatorname{ggT} (a, n) = 1$ dann ist die Abbildung
$m_a : \mathbb{Z}_n \rightarrow \mathbb{Z}_n, x \mapsto ax$ bijektiv
Auslassung: Beweis dazu
$m_3 : \mathbb{Z}_6 \rightarrow \mathbb{Z}_6, x \mapsto 3 x$ ist nicht injektiv: $m 3 (2) = 0 = m 3 (0)$
$f, g : \mathbb{Z}_{11} \rightarrow \mathbb{Z}_{11}, f (x) = x + 3, g (x) = 7 x$
$f \circ g (x) = f (7 x) = 7 x + 3$
$f - 1 (y) = y - 3$
$g - 1 (y) = 8 y$
Erinnerung (0.10): $(f \circ g)^{- 1} = g^{- 1} \circ f^{- 1}$
$(f \circ g)^{- 1} (y) = 8 y + 9$

Körper

(0.12) Definition (Körper)

Eine Menge K heißt Körper, wenn zwei Abbildungen

$+ : K \times K \rightarrow K, (a, b) \mapsto a + b \cdot : K \times K \rightarrow K, (a, b) \mapsto a \cdot b$

definiert sind, für die gelten:

(A1) $a + (b + c) = (a + b) + c \forall a, b, c \in K$

(A2) $\exists 0 \in K$ mit $a + 0 = 0 + a = a \forall a \in K$

(A3) $\forall a \in K$ gibt es $- a \in K$ mit $a + ( - a) = ( - a) + a = 0$

(A4) $a + b = b + a \forall a, b \in K$

(A5) $a \cdot (b \cdot c) = (a \cdot b) \cdot c \forall a, b, c \in K$

(A6) $\exists 1 \in K$ mit $1 \cdot a = a \cdot 1 = a \forall a \in K$

(A7) $\forall a \in K$ gibt es $a^{- 1} \in K$ mit $a a - 1 = a - 1 a = 1$

(A8) $ab = ba \forall a, b \in K$

(A9) $a (b + c) = a b + a c$ und $(a + b) c = ac + bc \forall a, b, c \in K$

(0.13) Folgerungen (aus 0.12)

(A2'): $\exists$ genau ein $0 \in K$ mit $a + 0 = 0 + a = a \forall a \in K$

(A3'): $\forall a \in K$ gibt es genau ein $- a \in K$ mit $a + ( - a) = ( - a) + a = 0$

(B1): $\forall a \in K : a + a = a \Rightarrow a = 0$

(B2): $\forall a \in K : 0 \cdot a = a \cdot 0 = 0$

(B3): $a, b \in K$ mit $a b = 0$ $\Rightarrow a = 0$ oder $b = 0$

(B4): $\forall a, b \in K : a (- b) = (- a) b = - (ab)$

(0.14) Bemerkung (zu 0.12)

Sei $K$ Körper

Für $a, b \in K$ schreiben wir kurz

$a - b$ für $a + ( - b)$

$a b$ für $a \cdot b$

$\frac{a}{b}, a / b$ für $a \cdot b^{- 1}$

$a n$ für $\underset{n - \operatorname{mal}}{\underbrace{a \cdot a \cdot \ldots \cdot a}} (n \in \mathbb{N})$

(0.15) Beispiele (zu 0.12)

a) Bekannte Körper

$\mathbb{R}$ und $\mathbb{Q}$ sind Körper (mit den üblichen Abbildungen $+$ und $\cdot$ )

$\mathbb{Z}$ ist keine Körper (A7 ist nicht gegeben)

b) Komplexe Zahlen

$\mathbb{R} \times \mathbb{R}$ mit den Abbildungen

$+ : (\mathbb{R} \times \mathbb{R}) \times (\mathbb{R} \times \mathbb{R}) \rightarrow \mathbb{R} \times \mathbb{R}, ((a, b), (a', b')) \mapsto (a + a', b + b')$

$\cdot : (\mathbb{R} \times \mathbb{R}) \times (\mathbb{R} \times \mathbb{R}) \rightarrow \mathbb{R} \times \mathbb{R}, ((a, b), (a', b')) \mapsto (aa' + bb', ab' + a' b)$

ist ein Körper (nämlich $\mathbb{C}$ , $(a, b)$ ist $(a + \operatorname{bi})$ )

c) Kleinster endlicher Körper

${0,1}$ mit den Abbildungen $+, \cdot$

definiert durch die Verknüpfungstabellen

$\left. \begin{array}{lll} + & 0 & 1\\ 0 & 0 & 1\\ 1 & 1 & 0 \end{array} \right\} \operatorname{XOR}$

$\left. \begin{array}{lll} \cdot & 0 & 1\\ 0 & 0 & 0\\ 1 & 0 & 1 \end{array} \right\} \operatorname{AND}$

Dieser Körper heißt $\mathbb{F}_2$ (oder $\mathbb{Z}_2$ )

d) Primzahlen-Restklassen

Sei $p$ Primzahl. Dann ist $\mathbb{Z}_p$ ein Körper

$\mathbb{Z}_p$ erbt alle Axiome bis auf (A7) von $\mathbb{Z}$

Weil $p$ Primzahl gilt $\operatorname{ggT} (b, p) = 1 \forall b \in \{0, \ldots p - 1\}$

$\overset{\text{euklid. Algo.}}{\Rightarrow} \forall a \in \{0, \ldots .p - 1\} \exists b : ab = 1$

e) Weiterer endlicher Körper

Auslassung: Nichts großartig aufregendes

Gruppen und Ringe

(0.16) Definition (Gruppe)

Sei $G$ eine Menge und $\ast : G \times G \rightarrow G, (a, b) \mapsto a \ast b$ eine Abbildung, genannt Verknüpfung oder Operation.

$(G, \ast)$ (oder kurz $G$ ) heißt Gruppe, wenn gelten:

(G1) $(x \ast y) \ast z = x \ast (y \ast z) \forall z, y, z \in G$

(G2) $\exists e \in G : e \ast x = x = x \ast e \forall x \in G$

(G3) $\forall x \in G : \exists x' \in G : x \ast x' = e = x' \ast x$

$(G, \ast)$ heißt abelsche Gruppe, wenn zusätzlich gilt:

(G4) $x \ast y = y \ast x \forall x, y \in G$

$e$ heißt neutrales Element von $G$

$x'$ in (G3) heißt inverses Element von $x$

(0.17) Bemerkung (zu 0.16)

In der Regel schreiben wir $G$ ``multiplikativ dh. $\cdot$ für $\ast$ , 1 für $e$ , $x - 1$ für $x'$
Neutrales Element und Inverses sind jeweils eindeutig
Wenn $G$ abelsch ist, schreiben wir $G$ meistens ``additiv, dh. $+$ für $\ast$ , 0 für $e$ , $- x$ für $x'$
Wegen (G1) lassen wir Klammern häufig weg
zB. $x \ast y \ast z = (x \ast y) \ast z = x \ast (y \ast z)$

(0.18) Beispiele (zu 0.16)

$(\mathbb{Z}, +)$ abelsche Gruppe, $(\mathbb{Z}_n, +)$ abelsche Gruppe
$K$ Körper
$(K, + )$ abelsche Gruppe ``additive Gruppe von $K$
$(K \backslash \{0\}, \cdot)$ abelsche Gruppe ``multiplikative Gruppe von $K$
$M$ Menge
$S_M := \{f : M \rightarrow M|f \text{ ist bijektiv} \}$
$(S_M, \circ)$ ist Gruppe, wobei $\circ =$ Komposition von Abbildung
(G1) $(f \circ g) \circ h = f \circ (g \circ h)$ also $(f \circ g) \circ h (x) = f (g (h (x))) = f \circ (g \circ h (x))$
(G2) $e = \operatorname{id}_M$
(G3) $f - 1 =$ Umkehrabbildung (vgl. Bsp. (0.9))
$n \in \mathbb{N}, M = \underline{n}$
$S_n := S_M = S_{\underline{n}}$ heißt symmetrische Gruppe und ihre Elemente Permutationen
$| S n | = n!$
Sei $(G, \cdot)$ Gruppe $n \in \mathbb{N}$
Betrache $G^n := \underset{n - \operatorname{mal}}{\underbrace{G \times G \times \ldots \times G}} =\{(a_1 \ldots a_n) |a_i \in G\}$
mit ``komponentenweiser Verknüpfung, d.h.
$(a_1, \ldots, a_n) \cdot (b_1, \ldots, b_n) := (a_1 \cdot b_1, \ldots, a_n \cdot b_n)$
$(G^n, \cdot)$ ist Gruppe und ist $G$ abelsch, dann auch $G n$
$M$ Menge. Betrache: $M^G := \{f : M \rightarrow G\}$
mit der Verknüpfung $(f \cdot g) (x) := f (x) \cdot g (x)$
$(M^G, \cdot)$ ist Gruppe

(0.19) Definition (Gruppenhomomorphismus)

Seine $G, H$ Gruppen

Eine Abbildung $\varphi : G \rightarrow H$ heißt Gruppenhomomorphismus wenn

$\varphi ( \underset{\operatorname{in} G}{\underbrace{x \cdot y}}) = \underset{\operatorname{in} H}{\underbrace{\varphi (x) \cdot \varphi (y)}} \forall x, y \in G$

Ein Homomorphismus $\varphi : G \rightarrow H$ heißt

$\left\{ \begin{array}{c} \text{Monomorphismus}\\ \text{Epimorphismus}\\ \text{Isomorphismus} \end{array} \right\} \text{wenn } \varphi \left\{ \begin{array}{c} \text{injektiv}\\ \operatorname{surjektiv}\\ \operatorname{bijektiv} \end{array} \right\}$

Existiert ein Isomorphismus $\varphi : G \rightarrow H$ dann heißen $G$ und $H$ isomorph, geschrieben

$G \cong H$

(0.20) Beispiel (zu 0.19)

$(\mathbb{Z}, +) \rightarrow (\mathbb{R}, +), x \mapsto x$ ist Monomorphismus
$\exp : (\mathbb{R}, +) \mapsto (\mathbb{R}_{> 0}, \cdot), x \mapsto e^x$
$e^{x + y} = e^x \cdot e^y$
ist Epimorphismus

(0.21) Schreibweise (und Beispiel)

Sei $(A, + )$ abelsche Gruppe, $a \in A$ sowie $U, V \subseteq A$

$a + U := \{a + u|u \in U\} \subseteq A U + V := \{u + v|u \in U, v \in V\} \subseteq A$

Beispiel

$A = (K^n, +), U =\mathbb{L}_0 \subseteq A$
$\mathbb{L}= S +\mathbb{L}_0$
$A =\mathbb{Z}, U = 7 \cdot \mathbb{Z}, 1 + U =\{\ldots, 1, 8, 15, \ldots\}$

(0.22) Definition (Ring)

Sei $R$ eine Menge mit zwei Verknüpfungen

$+ : R \times R \rightarrow R$ und $\cdot : R \times R \rightarrow R$

$(R, +, \cdot)$ heißt Ring (oder kurz $R$ ), wenn gelten:

(R1) $(R, + )$ ist abelsche Gruppe

(R2) $(x \cdot y) \cdot z = x \cdot (y \cdot z) \forall x, y, z \in R$

(R3) $\exists 1 \in \mathbb{R}$ mit $1 \cdot x = x = x \cdot 1 \forall x \in R$

(R4) $x \cdot (y + z) = x \cdot y + x \cdot y$ und $(x + y) \cdot z = x \cdot z + y \cdot z$ \ $\forall x, y \in R$

$R$ heißt kommultativ wenn zusätzlich gilt

(R5) $x \cdot y = y \cdot x$ $\forall x, y \in R$

(0.23) Beispiele (zu 0.22)

$\mathbb{Z}$ , alle $\mathbb{Z}_n$ und alle Körper sind auch kommultative Ringe
$R = {0}$ ist kommulatativer Ring (Trivialring), Achtung: 1=0
Vom kommultativen Ring zum Körper fehlen (A7) und $1 \neq 0$
$n\mathbb{Z}$ ist kein Ring, denn es existiert keine 1 (außer bei $n = 1$ )

(0.24) Definition (Einheit)

Sei $R$ ein Ring und $x \in R$

$x$ heißt invertierbar oder Einheit, wenn es $x' \in R$ mit $x \cdot x' = 1 = x' \cdot x$ gibt

Bemerkung: Falls existent ist $x'$ eindeutig und heißt Inverses bzw. inverses Element von $x$ , geschrieben $x - 1$

$R^{\ast} :=$ Menge aller Einheiten von $R$

(0.25) Bemerkung (zu 0.24)

$1 \in R^{\ast}$
Ist $x \in R^{\ast}$ , dann $x^{- 1} \in R^{\ast}$
$\mathbb{Z}^{\ast} =\{1, - 1\}$
$(R^{\ast}, \cdot)$ ist Gruppe (Einheitengruppe)
Beweis:
Seien $x, y \in R$ , zu zeigen: $x \cdot y \in R^{\ast}$
Es gibt $x^{- 1}, y^{- 1} \in R^{\ast}$
$(x \cdot y) (y^{- 1} \cdot x^{- 1})_{} \in R^{\ast} = x \cdot 1 \cdot x^{- 1} = 1$
Also $x \cdot y \in R^{\ast}$
Axiome: (G1): von $R$ , (G2): nach a), (G3): nach b)
$R$ kommultativer Ring
$R$ Körper $\Leftrightarrow R^{\ast} = R \backslash \{0\}$
Beweis:
(A7) $\Leftrightarrow R^{\ast} \supseteq R \backslash \{0\}$
$1 \neq 0 \Leftrightarrow 0 \notin R^{\ast}$
Sei $a \in \mathbb{Z}_n = (0, 1, \ldots, n - 1)$
$a \in \mathbb{Z}_n^{\ast} \Leftrightarrow \operatorname{ggT} (a, n) = 1$
Auslassung: Beweis..
$\mathbb{Z}_n$ Körper $\Leftrightarrow n$ Primzahl
Beweis: f), e)

(0.26) Definition (Ringhomomorphismus)

Seien $R, S$ Ringe. Eine Abbildung $\varphi : R \rightarrow S$ heißt (Ring-)Homomorphismus, wenn gelten:

$\varphi$ ist Gruppenhomomorphismus $(R, +) \rightarrow (S, +)$
$\varphi (x \cdot y) = \varphi (x) \cdot \varphi (y)$ $\forall x, y \in R$
$\varphi (1) = 1$

(0.27) Beispiel (zu 0.26)

Die Abbildung $\mathbb{Z} \rightarrow \mathbb{Z}_n, a \mapsto a \text{ mod } n$
Die Abbildung $m_a : \mathbb{Z} \rightarrow \mathbb{Z}, x \mapsto a \cdot z$
ist kein Ringhomomorphismus ( $m_a = a \neq 1)$ (ausser $a = 1$ )