3. Vektorräume

(3.1) Def.: Ein Vektorraum über einem Körper K ist eine abelsche Gruppe (V, +) zusammen mit einer Abbildung K × V → V, (α, v) ∈ K × V ↦ αv, so daß für alle α, β ∈ K und alle v, w ∈ V gilt:

(i) α(βv) = (αβ)v (=: αβv)

(ii) (α + β)v = (αv) + (βv) (=: αv + βv)

(iii) α(v + w) = (αv) + (αw) (=: αv + αw)

(iv) 1v = v (, wobei 1 das Einselement von K bezeichnet!)

Sprechweisen und Bezeichnungen: “Punkt vor Strich” αv + βw := (αv) + (βw), außerdem: v − w := v + (−w) Vektorraum über einem Körper K = K-Vektorraum

Das neutrale Element von (V, +) wird (zunächst) mit \underline{0} bezeichnet, zur Unterscheidung vom neutralen Element 0 von (K, +).

Elemente von V werden “Vektoren” (des Vektorraums V) genannt, Elemente des Körpers werden auch “Skalare” genannt.

Beispiele:

1) K := ℝ und V := ℝ^{n} mit den vor (1.15) eingeführten Operationen

(x_{1}, …, x_{n}) + (y_{1}, …, y_{n}) := (x_{1} + y_{1}, …, x_{n} + y_{n})
r(x_{1}, …, x_{n}) := (rx_{1}, …, rx_{n}).

In diesem Fall \underline{0} = (0, …, 0)

2) Allgemeiner: Sei K beliebiger Körper, n ∈ ℕ, n ≥ 1. Dann können wir genau wie in Beispiel 1) die Menge

K^{n} = {(x_{1}, …, x_{n}) | x_{1} ∈ K, …, x_{n} ∈ K}

zu einem Vektorraum über dem Körper K machen.

3) Sei I ein \underline{homogenes} lineares Gleichungssystem mit m Gleichungen und n Unbekannten x_{1}, …, x_{n} und Koeffizienten a_{11}, …, a_{mn} in K. Dann bildet die Lösungsmenge

L_{I} = {x = (x_{1}, …, x_{n}) ∈ K^{n} | x löst I}

mit den wie in 1) definierten Operationen einen K-Vektorraum, vgl. (1.15).

4) Sei K := ℝ, M ≠ ∅ eine Menge und V = {f | f : M → ℝ}.

Für r ∈ ℝ, f, g ∈ V definieren wir f + g ∈ V und rf ∈ V durch

(a) ∀x ∈ M : (f + g)(x) := f(x) + g(x)

(b) ∀x ∈ M : (rf)(x) := rf(x)

Mit diesen Operationen ist V ein ℝ-Vektorraum (wobei \underline{0} ∈ V die Abbildung ist, die jedes x ∈ M auf 0 ∈ ℝ abbildet).

Wir beweisen exemplarisch, daß (3.1)(iii) gilt: Seien f, g ∈ V, r ∈ ℝ. Zu zeigen ist:

(∗) r(f + g) = rf + rg

Auf beiden Seiten von (∗) stehen Abbildungen von M nach ℝ. Wir haben also zu zeigen, daß für alle x ∈ M gilt:

(r(f + g))(x) = (rf + rg)(x)

Wendet man auf beide Seiten (a) und (b) an (auf der linken Seite zunächst (b) dann (a)), so erhält man für die linke Seite

(r(f + g)(x)) =^{(b)} r((f + g)(x)) =^{(a)} r(f(x) + g(x))

und für die rechte Seite

(rf + rg)(x) =^{(a)} (rf)(x) + (rg)(x) =^{(b)} rf(x) + rg(x)

Schließlich gilt r(f(x) + g(x)) = rf(x) + rg(x) aufgrund des Distributivgesetzes für die reellen Zahlen.

(3.2) Rechenregeln. Für alle α ∈ K, v ∈ V gilt

(i) 0v = \underline{0}, α\underline{0} = \underline{0}

(ii) αv = \underline{0} ⇒ α = 0 oder v = \underline{0}

(iii) (−α)v = α(−v) = −(αv) (=: −αv)

Bew.:

(i) 0v = 0v + (v − v) = (0v + 1v) − v = (0 + 1)v − v = 1 · v − v = v − v = \underline{0} α\underline{0} = α\underline{0} + (α\underline{0} − α\underline{0}) = α(\underline{0} + \underline{0}) − α\underline{0} = α\underline{0} − α\underline{0} = \underline{0}

(ii) Sei αv = \underline{0} und α ≠ 0 ⇒^{(i)} α^{−1}(αv) = \underline{0} ⇒ (α^{−1}α)v = \underline{0} ⇒ 1v = \underline{0} ⇒ v = \underline{0}

(iii) (−α)v + αv = ((−α) + α)v = 0v =^{(i)} \underline{0} ⇒ (−α)v = −(αv)

α(−v) + αv = α((−v) + v) = α\underline{0} =^{(i)} \underline{0} ⇒ α(−v) = −(αv)

(3.3) Def.: Sei V K-Vektorraum und U ⊆ V. U heißt Unter(vektor)raum von V, falls

(i) U ≠ ∅

(ii) v_{1}, v_{2} ∈ U ⇒ v_{1} + v_{2} ∈ U

(iii) α ∈ K, v ∈ U ⇒ αv ∈ U

(3.4) Folgerung: Sei V K-Vektorraum, U ⊆ V Unterraum. Dann ist U (mit den von V auf U eingeschränkten Strukturen) ein K-Vektorraum.

Bew.: Sei U Unterraum.

(i) ⇒ + ist innere Verknüpfung auf U(⇒ (G_{1})).

(ii) ⇒ die Multiplikation mit Skalaren ist eine Abbildung K × U → U.

Wir zeigen: (U, +) ist abelsche Gruppe: v ∈ U ⇒^{(ii)} (−1)v ∈ U ⇒^{(3.2)(iii)} −v ∈ U

U ≠ ∅ ⇒ ∃v ∈ U ⇒ v und −v ∈ U ⇒^{(ii)} v + (−v) = \underline{0} ∈ V

Daraus folgen (G_{2}), (G_{3}) für (U, +), (G_{1}) für (U, +) folgt aus (G_{1}) für (V, +). Die anderen Eigenschaften sind offensichtlich erfüllt.

Beispiele:

1) {0} und V sind Unterräume von V

2) Ist m < n, so ist K^{m} × \{ \underbrace{(0, …, 0}_{(n−m)−mal}\} = \{(x_{1}, …, x_{n}) ∈ K^{n} | x_{m+1} = … = x_{n} = 0\}

Unterraum von K^{n}

3) Ist I homogenes lineares Gleichungssystem für n Unbekannte mit Koeffizienten a_{ij} in K, so ist L_{I} Unterraum von K^{n}, vgl. (1.15).

4) V = {f | f : M → ℝ}, vgl. Bsp. 4) nach (3.1). Zu festem a ∈ M sei U = {f ∈ V | f(a) = 0}. Dann ist U Unterraum von V.

(3.5) Fakt. Ist V ein K-Vektorraum und U eine Menge von Unterräumen von K, so ist W := ⋂_{U∈U} U Unterraum von V .

Bew.: ∀U ∈ U : \underline{0} ∈ U ⇒ \underline{0} ∈ W

v_{1}, v_{2} ∈ W ⇔ ∀U ∈ U : v_{1}, v_{2} ∈ U ⇒^{(3.3)(ii)} ∀U ∈ U : v_{1} + v_{2} ∈ U ⇔ v_{1} + v_{2} ∈ W

Ebenso: α ∈ K, v ∈ W ⇒ αv ∈ W.

(3.6) Def.: Sei V K-Vektorraum, M ⊆ V. U_{M} := {U | U Unterraum von V mit M ⊆ U}

Dann heißt span(M) := ⋂_{U∈U_{M}} U der von M aufgespannte (oder erzeugte) Unterraum. M

heißt Erzeugendensystem von V, falls span(M) = V gilt. V heißt endlich erzeugt, falls es eine endliche Menge M ⊆ V gibt mit span(M) = V.

Bem.: (3.5) ⇒ span(M) ist Unterraum von V, der (bzgl. der Inklusion) kleinste, M enthaltende Unterraum.

Bsp.:

1) M = ∅ oder M = \{\underline{0}\} ⇒ span(M) = \{\underline{0}\}

2) Ist M Unterraum von V, so span(M) = M

(3.7) Satz. Sei V K-Vektorraum, ∅ ≠ M ⊆ V. Dann gilt:

span(M) = {v ∈ V | ∃k ∈ ℕ, α_{1}, …, α_{k} ∈ K, v_{1}, …, v_{k} ∈ M : v = α_{1}v_{1} + … + α_{k}v_{k}} Bez.: α_{1}v_{1} + … + α_{k}v_{k} heißt eine Linearkombination der Vektoren v_{1}, …, v_{k}.

abgekürzt: α_{1}v_{1} + α_{s} v_{2} + … + α_{k}v_{k} = ∑_{i=1}^{k} α_{i}v_{i}

Bew.: Wir bezeichnen die Menge auf der rechten Seite des Gleichheitszeichens in (3.7) durch U_{0}.

1) Zeige U_{0} ist Unterraum von V. Wegen M ≠ ∅ gilt U_{0} ≠ ∅. Seien v, w ∈ U_{0}, v = α_{1}v_{1} + … + α_{k}v_{k}, w = β_{1}w_{1} + … + β_{j}w_{j} mit α_{1}, …, β_{j} ∈ K, v_{1}, …, w_{j} ∈ M. Dann gilt v + w = α_{1}v_{1} + … + α_{k}v_{k} + β_{1}w_{1} + … + β_{j}w_{j} ∈ U_{0}.

Sei α ∈ K, v = ∑_{i=1}^{k} α_{i}v_{i} ∈ U_{0} mit v_{i} ∈ M. Dann gilt

αv = α(α_{1}v_{1} + … + α_{k}v_{k}) = α(α_{1}v_{1}) + … + α(α_{k}v_{k}) = (αα_{1})v_{1} + … + (αα_{k})v_{k} ∈ U_{0}.

(Kürzer: α ∑_{i=1}^{k} α_{i}v_{i} = ∑_{i=1}^{k} αα_{i}v_{i}).

Also ist U_{0} ein M enthaltender Unterraum. Nach Definition (3.6) folgt span(M) ⊆ U_{0}.

2) Zeige U_{0} ⊆ span(M). Seien v_{1}, …, v_{k} ∈ M, α_{1}, …, α_{k} ∈ K. Da span(M) Unterraum ist, folgt nach (3.3)(iii): α_{1}v_{1} ∈ span(M), …, α_{k}v_{k} ∈ span(M), und nach (3.3)(ii) α_{1}v_{1}+α_{2}v_{2} ∈ span(M), (α_{1}v_{1} + α_{2}v_{2}) + α_{3}v_{3} ∈ span(M), u.s.w. bis

α_{1}v_{1} + … + α_{k}v_{k} ∈ span(M).

Also U_{0} ⊆ span(M).

Bsp.: Betrachte K^{n} und e_{1} := (1, 0, …, 0) ∈ K^{n}, e_{2} := (0, 1, 0, …, 0) ∈ K^{n}, …, e_{n} = (0, …, 0, 1) ∈ K^{n}. Dann ist M = {e_{1}, …, e_{n}} Erzeugendensystem für K^{n}. Es genügt, K^{n} ⊆ span(M) zu zeigen. Ist x = (x_{1}, …, x_{n}) ∈ K^{n}, so gilt x = x_{1}e_{1} + x_{2}e_{2} + … + x_{n}e_{n} ∈ span(M).

(3.8) Def.: Die Vektoren v_{1}, …, v_{k} heißen \underline{linear unabhängig}, falls gilt: Ist α_{1} ∈ K, …, α_{k} ∈ K und α_{1}v_{1} + … + α_{k}v_{k} = \underline{0}, so folgt α_{1} = α_{2} = … = α_{k} = 0. Sonst heißen die Vektoren v_{1}, …, v_{k} linear abhängig. Eine Teilmenge M von V heißt linear unabhängig, falls gilt: Ist k ∈ ℕ und sind v_{1}, …, v_{k} verschiedene Vektoren in M, so sind die v_{1}, …, v_{k} linear unabhängig. Sonst heißt M linear abhängig.

Bem.: v_{1}, …, v_{k} linear abhängig ⇔ ∃α_{1}, …, α_{k} ∈ K \underline{nicht} \underline{alle} = 0:

α_{1}v_{1} + … + α_{k}v_{k} = \underline{0}

Bsp.:

1) \underline{0} ∈ M ⇒ M linear abhängig. Denn: 1 · \underline{0} = \underline{0}.

2) M = \{v\} linear unabhängig ⇔ v ≠ 0. Denn: αv = \underline{0}, v ≠ \underline{0} ⇒^{(3.2)(ii)} α = 0.

3) Sei M ⊆ M′ ⊆ V. Dann: M linear abhängig ⇒ M′ linear abhängig M′ linear unabhängig ⇒ M linear unabhängig 4) e_{1}, …, e_{n} sind linear unabhängig in K^{n}. Denn:

x_{1}e_{1} + … + x_{n}e_{n} = (x_{1}, …, x_{n}) = \underline{0} ⇔ x_{1} = … = x_{n} = 0.

5) V = {f | f : ℝ → ℝ}. Die Funktion x → sin x und x → cos x sind linear unabhängig. Seien r, s ∈ ℝ und r sin x + s cos x = 0 \underline{für alle} x ∈ ℝ. Dann gilt das speziell für x = 0 und x = \frac{π}{2}, d.h.

r \underbrace{sin 0}_{=0} +s \underbrace{cos 0}_{=1} = 0  ⇒ s = 0
r \underbrace{sin (\frac{π}{2} )}_{=1} +s \underbrace{cos (\frac{π}{2} )}_{=0} = 0 ⇒ r = 0.

(3.9) Fakt. Die Vektoren v_{1}, …, v_{k} seien linear unabhängig. Dann gilt:

α_{1}v_{1} + … + α_{k}v_{k} = β_{1}v_{1} + … + β_{k}v_{k} ⇒ α_{1} = β_{1}, …, α_{k} = β_{k}

Bew.: Voraussetzung ⇒ (α_{1} − β_{1})v_{1} + (α_{2} − β_{2})v_{2} + … + (α_{k} − β_{k})v_{k} = \underline{0} ⇒^{l. unabh.} α_{1} − β_{1} = 0, …, α_{k} − β_{k} = 0 ⇒ α_{1} = β_{1}, …, α_{k} = β_{k}.

(3.10) Def.: Eine Teilmenge M von V heißt \underline{Basis von} V, falls M linear unabhängig und ein Erzeugendensystem von V (⇔ span(M) = V) ist.

Bsp.: {e_{1}, …, e_{n}} ⊆ K^{n} ist Basis von K^{n}, die “Standardbasis von K^{n}”.

Eine Beispielrechnung zur linearen Unabhängigkeit von Vektoren:

Wir fragen, ob die Vektoren (1, 0, 1), (0, 1, 1), (1, 1, −1) im ℝ-Vektorraum ℝ^{3} linear unabhängig sind. Dazu nehmen wir an, daß für die reellen Zahlen r, s und t gilt:

r(1, 0, 1) + s(0, 1, 1) + t(1, 1, −1) = (0, 0, 0)

Die Vektoren sind linear unabhängig, wenn wir aus dieser Gleichung folgern können, daß r = s = t = 0 gilt, vgl. Def. (3.8). Die Gleichung ist äquivalent zum homogenen linearen Gleichungssystem

r + t = 0 | −
s + t  = 0 |
r + s − t  = 0 _{←}|

Wir lösen es nach dem Gaußschen Eliminationsverfahren:

r  + t = 0
s + t = 0 | −
s − 2t = 0 _{←}|
r  + t = 0
s + t = 0
− 3t = 0

Aus der letzten Gleichung folgt t = 0, damit aus der vorletzten s = 0 und aus der ersten r = 0.

Vorsicht: Bezeichnet man im Körper (ℤ_{3}, +, ·) wie in Körpern üblich das 0-Element mit 0, das 1-Element mit 1 und das additive Inverse von 1 mit −1, so kann man die Vektoren (1, 0, 1), (0, 1, 1), (1, 1, −1) auch als Element des ℤ_{3}-Vektorraums (ℤ_{3})^{3} auffassen. In diesem sind sie linear abhängig, denn

(1, 0, 1) + (0, 1, 1) − (1, 1, −1) = (0, 0, 0) in (ℤ_{3})^{3}!

(3.11) Lemma. (i) v ∈ span(M) ⇒ span(M ∪ {v}) = span(M) (ii) v ∈ span(M) \ M ⇒ M ∪ {v} linear abhängig

Beweis von (i): span(M) ⊆ span(M ∪ {v}) ist klar.

Sei w ∈ span(M ∪ {v}), w = αv + ∑_{j=1}^{l} β_{j}w_{j} mit w_{j} ∈ M.

v ∈ span(M) ⇒ v = ∑_{i=1}^{k} α_{i}v_{i} ⇒ w = ∑_{i=1}^{k}(αα_{i})v_{i} + ∑_{j=1}^{l} β_{j}w_{j} ∈ span(M).

Beweis von (ii): (3.7) ⇒ Es existiert k ∈ ℕ, α_{1}, …, α_{k} ∈ K, v_{1}, …, v_{k} ∈ M: v =^{(∗)} ∑_{i=1}^{k} α_{i}v_{i}.

Wir können (mittels der Vektorraumaxiome) etwaige Summanden α_{i}v_{i} und α_{j}v_{j} mit v_{i} = v_{j} zu (α_{i} + α_{j})v_{i} zusammenfassen und dann annehmen, daß alle v_{1}, …, v_{k} verschieden sind. v ∉ M ⇒ v, v_{1}, …, v_{k} sind alle verschieden.

(∗) ⇒ 1 · v − ∑_{i=1}^{k} α_{i}v_{i} = 0 ⇒ M ∪ {v} linear abhängig.

(3.12) Satz. Folgende Aussage über eine Teilmenge M von V sind äquivalent:

(i) M ist Basis (ii) M ist linear unabhängig und jede echte Obermenge M′ ⊆ V von M ist linear

abhängig. (“M ist eine maximale linear unabhängige Teilmenge von V.”) (iii) Es gilt span(M) = V und für jede echte Teilmenge M′′ von M gilt: span(M′′) ≠ V.

(“M ist ein minimales Erzeugendensystem von V.”)

Bew.: V = {0} ⇔ M = ∅ ist Basis von V. Dann ist (3.12) klar. Es genügt also, den Fall M ≠ ∅ zu betrachten.

1) (i) ⇒ (ii): Es ist zu zeigen, daß jede echte Obermenge M′ ⊆ V von M linear abhängig ist. Sei v ∈ M′\M. Wegen span(M) = V (M Basis!) gilt v ∈ span(M)\M. Nach (3.11)(ii) ist M ∪ {v} und damit auch M′ ⊇ M ∪ {v} linear abhängig.

2) (ii) ⇒ (iii). Wir zeigen zunächst, daß span(M) = V gilt. Sei v ∈ V \ M. Wegen (ii) ist M ∪ {v} linear abhängig. Es existieren also verschiedene v_{1}, …, v_{k} ∈ M und

α, α_{1}, …, α_{k} ∈ K, nicht alle = 0, mit

αv + ∑_{i=1}^{k} α_{i}v_{i} = \underline{0}

Da M linear unabhängig ist ((ii)!), gilt α ≠ 0. Also

v = ∑_{i=1}^{k} (\frac{−α_{i}}{α} ) v_{i} ∈ span(M)

Also V \ M ⊆ span(M), und damit: V = span(M).

Sei schließlich M′′ eine echte Teilmenge von M, v ∈ M \M′′. Wäre v ∈ span(M′′), so würde aus (3.11)(ii) folgen, daß M′′ ∪{v} ⊆ M linear abhängig ist, im Widerspruch dazu, daß M nach Voraussetzung ((ii)!) linear unabhängig ist. Also v ∉ span(M′′) und deshalb span(M′′) ≠ V.

3) (iii) ⇒ (i). Zu zeigen ist, daß M linear unabhängig ist. Seien v_{1}, …, v_{k} verschiedene Elemente in M, α_{1}, …, α_{k} ∈ K und

∑_{i=1}^{k} α_{i}v_{i} = \underline{0}

wäre eines der α_{i} ungleich 0, z.B. α_{1} ≠ 0, so folgt:

v_{1} = ∑_{i=1}^{k} (\frac{−α_{i}}{α_{1}} ) v_{i} ∈ span\{v_{2}, …, v_{k}\} ⊆ span(M \ \{v_{1}\})

Wegen (3.11)(i) folgt span(M) = span(M \{v_{1}}), also span(M \{v_{1}}) = V, im Widerspruch zu (iii).

(3.13) Satz. Jeder Vektorraum besitzt eine Basis.

Bem.: Wir zeigen sogar: Ist M_{0} ⊆ V linear unabhängig, so existiert eine M_{0} enthaltende Basis von V.

Bew.: 1) Wir betrachten zunächst den Spezialfall, daß es ein endliches Erzeugendensystem, genannt M_{1}, von V gibt. Dann existiert das kleinste n ∈ ℕ, so daß es eine n-elementige Teilmenge von M_{1} gibt, die V erzeugt. Sei M ein solches Erzeugendensystem. Dann folgt aus (3.12), daß M eine Basis von V ist. Zusätzlich gilt M ⊆ M_{1}.

2) Für den allgemeinen Fall benötigen wir folgendes

(3.14) Lemma von Zorn. Sei M ≠ ∅ eine Menge, deren Elemente Mengen sind. Gilt für jede Kette K ⊆ M, daß ⋃_{M∈K} M ∈ M gilt, so existiert ein maximales Element in M, d.h. ein

M ∈ M, so daß aus M ⊆ M′ ∈ M folgt M = M′.

Dabei heißt eine Teilmenge K von M \underline{Kette}, falls K ≠ ∅ und falls für je zwei Elemente M_{1}, M_{2} ∈ K gilt:

(∗) M_{1} ⊆ M_{2} oder M_{2} ⊆ M_{1}

Wir nehmen das Lemma von Zorn als Axiom der Mengenlehre hin und definieren in Abhängigkeit von einer gegebenen, linear unabhängigen Menge M_{0} ⊆ V:

M := {M | M_{0} ⊆ M ⊆ V, M linear unabhängig}

Wegen M_{0} ∈ M gilt M ≠ ∅. Wir wollen die Voraussetzung von (3.14) nachweisen. Sei also K eine Kette in M. Dann gilt M_{0} ⊆ ⋃_{M∈K} M und es bleibt zu zeigen, daß ⋃_{M∈K} M linear

unabhängig ist.

Seien v_{1}, …, v_{k} verschiedene Vektoren in ⋃_{M∈K} M. Dann existieren M_{1}, …, M_{k} ∈ K mit

v_{1} ∈ M_{1}, …, v_{k} ∈ M_{k}. Wegen (∗) existiert eine der Mengen M_{1}, …, M_{k}, sagen wir M_{j}, die die anderen enthält. Dann sind v_{1}, …, v_{k} verschiedene Elemente in M_{j} und damit linear unabhängig (, da M_{j} ∈ M linear unabhängig ist). Also ⋃_{M∈K} M ∈ M. Nach (3.2) ist ein

maximales Element von M, das nach (3.14) existiert, eine M_{0} enthaltende Basis von V.

\underline{Wichtig}: Es gibt im allgemeinen sehr viele Basen eines Vektorraumes. Sie haben aber alle “gleich viele” Elemente, siehe (3.16). Zum Beispiel bilden zwei Vektoren v = (a, b), w = (c, d) des ℝ^{2} genau dann eine Basis des ℝ^{2}, wenn ad − bc ≠ 0 (, was “meistens” der Fall ist!).

Bemerkung: Die “Lösung eines homogenen linearen Gleichungssystems”, d.h. das Auffinden einer Parameterdarstellung des Lösungsraums, besteht gerade darin, eine Basis dieses Lösungsraums zu finden.

(3.15) Austauschlemma. Sei B = {v_{1} …, v_{n}} eine Basis von V mit n Elementen und w ∈ V \ {0}. Dann existiert j ∈ {1, …, n}, so daß B′ = (B \ {v_{j}}) ∪ {w} Basis von V ist.

Bew.: Wegen span(B) = V existieren α_{1}, …, α_{n} ∈ K, so daß

(∗) w = ∑_{i=1}^{n} α_{i}v_{i}

gilt. Da w ≠ 0 ist, existiert ein j, 1 ≤ j ≤ n mit α_{j} ≠ 0. Wir zeigen, daß \underline{für jedes solche} j gilt: B′ = (B \ {v_{j}}) ∪ {w} = {v_{1}, …, v_{j−1}, v_{j−1}, …, v_{n}, w} ist Basis.

Zunächst gilt v_{j} ∈ span(B′), da aus (∗) folgt

v_{j} = \frac{1}{α_{j}} (w − ∑_{i≠j^{i=1}}^{n} α_{i}v_{i}) = \frac{1}{α_{j}} w + ∑_{i≠j^{i=1}}^{n} (\frac{−α_{i}}{α_{j}} ) v_{i}

und die rechte Seite ist eine Linearkombination von Elementen von B′.

Nach (3.11)(i) folgt

span(B′) =^{(3.11)(i)} span(B′ ∪ {v_{j}}) = span(B ∪ {w}) =^{(3.11)(i)} span(B) = V,

d.h. B′ ist Erzeugendensystem von V. Um die lineare Unabhängigkeit von B′ zu zeigen, nehmen wir an, daß für β ∈ K, β_{1}, …, β_{j−1}, β_{j+1}, …, β_{n} ∈ K gilt:

(∗∗) βw + ∑_{i≠j^{i=1}}^{n} β_{i}v_{i} = \underline{0}

Mit (∗) folgt

β ∑_{i=1}^{n} α_{i}v_{i} + ∑_{i≠j^{i=1}}^{n} β_{i}v_{i} = \underline{0},

also

βα_{j}v_{j} + ∑_{i≠j^{i=1}}^{n}(βα_{i} + β_{i})v_{i} = \underline{0}.

Da B = {v_{1}, …, v_{n}} linear unabhängig ist, folgt aus der vorangehenden Gleichung βα_{j} = 0 und βα_{i} + β_{i} = 0 für alle i ≠ j. Da wir j so gewählt hatten, daß α_{j} ≠ 0 ist, folgt β = 0 und daraus β_{i} = 0 für alle i ≠ j. Damit haben wir gezeigt, daß in (∗∗) alle Koeffizienten β und β_{i} für i ≠ j gleich 0 sind, d.h. B′ ist linear unabhängig.

(3.16) Austauschsatz von Steinitz. Sei B = {v_{1}, …, v_{n}} eine Basis von V mit n Elementen und seien w_{1}, …, w_{m} m linear unabhängige Vektoren in V. Dann gilt

(i) m ≤ n (ii) Es gibt (n − m) Vektoren in B, bei geeigneter Numerierung v_{m+1}, …, v_{n}, so daß

{w_{1}, …, w_{m}, v_{m+1}, …, v_{n}} eine Basis von V ist.

Speziell gilt: Jede Basis von V hat n Elemente.

Bew.: Induktion nach m.

1) m = 1. \underline{0} ≠ w_{1} ∈ V ⇒ V ≠ \{0\} ⇒ n ≥ 1 = m ⇒ (i). (ii) folgt aus (3.15).

2) m > 1. Induktionsvoraussetzung: (i) und (ii) gelten für m − 1. Seien w_{1}, …, w_{m} linear unabhängig gegeben. Die Induktionsvoraussetzung impliziert: (m−1) ≤ n und es existieren n − m + 1 Vektoren in B, o.E. v_{m} …, v_{n}, so daß {w_{1}, …, w_{m−1}, v_{m} …, v_{n}} eine Basis von V ist.

Zeige (i): m ≤ n. Sonst gilt nach der vorangehenden Überlegung m − 1 = n und die Menge {w_{1}, …, w_{m−1}} ist Basis von V (n − m + 1 = 0!), im Widerspruch zur Voraussetzung, daß {w_{1}, …, w_{m}} linear unabhängig ist. Das beweist m ≤ n.

Zeige (ii): Wir wollen in der Basis {w_{1}, …, w_{m−1}, v_{m}, …, v_{n}} eines der v_{i}, m ≤ i ≤ n, gegen w_{m} “austauschen” und zwar so, daß wieder eine Basis entsteht.

Da span{w_{1}, …, w_{m−1}, v_{m}, …, v_{n}} = V gilt, existieren α_{1}, …, α_{n} ∈ K, so daß

w_{m} = α_{1}w_{1} + … + α_{m−1}w_{m−1} + α_{m}v_{m} + … + α_{n}v_{n}

gilt. Da {w_{1}, …, w_{m}} linear unabhängig ist, existiert ein j ∈ {m, …, n} mit α_{j} ≠ 0. Wir können annehmen, daß j = m ist. Wendet man das Austauschlemma (3.15) (vgl. auch den Anfang des Beweises von (3.15)!) auf w := w_{m} und die Basis {w_{1}, …, w_{m−1}, v_{m}, …, v_{n}} an, so folgt, daß {w_{1}, …, w_{m}, v_{m+1}, …, v_{n}} eine Basis von V ist. Das beweist (ii).

(3.17) Def.: Ist V endlich erzeugter Vektorraum, so heißt die Anzahl der Elemente einer (⇒ jeder) Basis von V die \underline{Dimension} \underline{von} V (abgekürzt: dim V).

Ist V nicht endlich erzeugt, so setzen wir dim V := ∞.

Beispiele:

1) V = \{\underline{0}\} ⇔ dim V = 0 (mit Basis M = ∅)

2) Für den K-Vektorraum K^{n} gilt: dim(K^{n}) = n Begründung: Die Standardbasis {e_{1}, …, e_{n}} von K^{n} hat n Elemente.

3) V = {f | f : ℝ → ℝ}, vgl. Bsp. 4) nach (3.1). Für diesen ℝ-Vektorraum gilt dim V = ∞, vgl. Blatt 6, Aufgabe 4(b).

Bem.: V endlich erzeugt ⇔ V endlich-dimensional.

(3.18) Folgerungen. Sei V Vektorraum, dim V = n < ∞. Dann gilt:

(i) Ist M ⊆ V linear unabhängig, so gilt #M ≤ n, und es gilt #M = n genau dann, wenn M Basis von V ist.

(ii) Ist M ⊆ V Erzeugendensystem von V, so gilt #M ≥ n, und es gilt #M = n genau

dann, wenn M Basis von V ist. (iii) Ist U ⊆ V Unterraum, so gilt dim U ≤ dim V. Jede Basis von U ist in einer Basis

von V enthalten. Es gilt genau dann dim U = dim V, wenn U = V gilt.

Lösung von Blatt 5, Aufgabe 3: Sei U Unterraum des ℝ^{2} mit {(0, 0)} ≠ U ≠ ℝ^{2}. Dann existiert v ∈ ℝ^{2} \ {(0, 0)}, so daß U = {rv | r ∈ ℝ}.

Bew.: Es gilt 0 < dim U < 2 = dim(ℝ^{2}), also dim U = 1. Sei {v} Basis von U ⇒ Beh.

Beweis von (3.18):

(i) (3.16)(i) ⇒ #M ≤ n. Speziell: Ist #M = n, so ist M (im Sinne von (3.12)!) eine maximale linear unabhängige Teilmenge, also nach (3.12) eine Basis.

(ii) Analog zu (i).

(iii) Ist B′ Basis von U, so ist B′ als Teilmenge von V linear unabhängig, also dim U = #B′ ≤ n = dim V nach (i). Aus (3.16)(ii) folgt, daß B′ in einer Basis von V enthalten ist. Gilt dim U = dim V, so ist nach (i) jede Basis B′ von U auch Basis von V, d.h. U = span(B′) = V.

(3.19) Def.: Seien U_{1}, U_{2} Unterräume eines Vektorraums V. Dann heißt der Unterraum

U_{1} + U_{2} := span(U_{1} ∪ U_{2})

die \underline{Summe von} U_{1} \underline{und} U_{2}. Gilt U_{1} ∩ U_{2} = \{\underline{0}\}, so nennt man span(U_{1} ∪ U_{2}) die \underline{direkte} \underline{Summe von} U_{1} \underline{und} U_{2} und schreibt

span(U_{1} ∪ U_{2}) =: U_{1} ⊕ U_{2}

Bsp.: Für 0 < m < n gilt: K^{n} = (K^{m} × \{\underline{0}\}) ⊕ (\{\underline{0}\} × K^{n−m})

(3.20) Fakt. (i) U_{1} + U_{2} = {u_{1} + u_{2} | u_{1} ∈ U_{1}, u_{2} ∈ U_{2}} (ii) Gilt U_{1} ∩ U_{2} = {0}, so existieren für jedes v ∈ U_{1} ⊕ U_{2} genau zwei Vektoren u_{1} ∈ U_{1}, u_{2} ∈ U_{2}, so daß v = u_{1} + u_{2} gilt.

Bsp.: 1) V = ℝ^{2}, U_{1}, U_{2} Unterräume der Dimension 1, U_{1} ≠ U_{2}. Dann: U_{1} ∩ U_{2} = {(0, 0)}, U_{1} ⊕ U_{2} = ℝ^{2}.

2) V = ℝ^{3}, U_{1} ≠ U_{2} Unterräume der Dimension 2. Dann: dim(U_{1} ∩ U_{2}) = 1, U_{1} + U_{2} = ℝ^{3}.

Beweis: Die Menge {u_{1} + u_{2} | u_{1} ∈ U_{1}, u_{2} ∈ U_{2}} ist Unterraum (!), der U_{1} und U_{2} enthält, also span(U_{1} ∪ U_{2}) ⊆ {u_{1} + u_{2} | u_{1} ∈ U_{1}, u_{2} ∈ U_{2}}, vgl. Def. (3.6). Die Inklusion {u_{1} + u_{2} | u_{1} ∈ U_{1}, u_{2} ∈ U_{2}} ⊆ span(U_{1} ∪ U_{2}) ist klar!

Gilt v = u_{1} + u_{2} = u′_{1} + u′_{2} mit {u_{1}, u′_{1}} ⊆ U_{1}, {u_{2}, u′_{2}} ⊆ U_{2}, so folgt

u_{1} − u′_{1} = u′_{2} − u_{2} ∈ U_{1} ∩ U_{2} = \{\underline{0}\}, also u_{1} = u′_{1}, u_{2} = u′_{2}.

(3.21) Lemma.

(i) Ist U Unterraum von V, so existiert ein Unterraum W von V, so daß U ∩ W = \{\underline{0}\} und U ⊕ W = V gilt. (W heißt ein zu U \underline{komplementärer Unterraum})

(ii) Sind U_{1}, U_{2} Unterräume von V mit U_{1} ∩ U_{2} = {0}, so gilt

dim(U_{1} ⊕ U_{2}) = dim U_{1} + dim U_{2}.

Bem.: Im allgemeinen gibt es sehr viele zu U komplementäre Unterräume. Beispiel: Es sei U = ℝ × {0} ⊆ ℝ^{2} und es sei v = (v_{1}, v_{2}) ∈ ℝ^{2} und v_{2} ≠ 0. Dann ist W = span{v} zu U komplementär.

Bew.: (i) Ergänze eine Basis B′ von U nach (3.18)(iii) zu einer Basis B von V und setze W := span(B \ B′). (ii) Für i = 1, 2 seien B_{1}, B_{2} Basen von U_{1}, U_{2}. Aus U_{1} ∩ U_{2} = {0} folgt B_{1} ∩ B_{2} = ∅. Wir zeigen, daß B_{1} ∪ B_{2} Basis von U_{1} ⊕ U_{2} ist (⇒ dim(U_{1} ⊕ U_{2}) = #(B_{1} ∪ B_{2}) = #B_{1} + #B_{2} = dim U_{1} + dim U_{2}). Wegen (3.20)(i) ist B_{1} ∪ B_{2} Erzeugendensystem von U_{1} ⊕ U_{2}. Um zu zeigen, daß B_{1} ∪ B_{2} linear unabhängig ist, sei

∑_{i=1}^{k} α_{i}v_{i} + ∑_{j=1}^{l} β_{j}w_{j} = \underline{0},

wobei α_{1}, …, β_{l} ∈ K, v_{1}, …, v_{k} verschiedene Elemente von B_{1}, w_{1}, …, w_{l} verschiedene Elemente von B_{2} sind. Dann folgt

∑_{i=1}^{k} α_{i}v_{i} = ∑_{j=1}^{l}(−β_{j})w_{j} ∈ U_{1} ∩ U_{2}.

Wegen U_{1} ∩ U_{2} = {0} folgt

∑_{i=1}^{k} α_{i}v_{i} = \underline{0} = ∑_{j=1}^{l}(−β_{j})w_{j}.

Da B_{1} und B_{2} beide linear unabhängig sind, folgt aus den vorangehenden Gleichungen α_{1} = … = α_{k} = 0 und β_{1} = … = β_{l} = 0. Das beweist die lineare Unabhängigkeit von B_{1} ∪ B_{2}.

Bem.: (3.21)(ii) gilt – richtig interpretiert – auch für den Fall, daß U_{1} oder U_{2} unendlichdimensional sind. Für den Rest des Kapitels werden wir aber \underline{dim V < ∞} voraussetzen.

(3.22) Dimensionssatz. Seien U_{1}, U_{2} Unterräume eines Vektorraums V. Dann gilt

dim(U_{1} + U_{2}) = dim U_{1} + dim U_{2} − dim(U_{1} ∩ U_{2})

Bew.: U_{1} ∩ U_{2} =: U_{12}. Nach (3.21)(i) existieren Unterräume W_{1}(von U_{1} ⇒ von V) und W_{2}, so daß U_{1} = U_{12} ⊕ W_{1} und U_{2} = U_{12} ⊕ W_{2} gilt. Dann folgt

(∗) U_{1} + U_{2} = (U_{12} ⊕ W_{1}) ⊕ W_{2}

Denn einerseits läßt sich jedes Element v ∈ U_{1} + U_{2} als

v = u_{1} + u_{2} = u_{12} + w_{1} + u′_{12} + w_{2} = (u_{12} + u′_{12}) + w_{1} + w_{2}

mit u_{1} ∈ U_{1}, u_{2} ∈ U_{2}, u_{12}, u′_{12} ∈ U_{12}, w_{1} ∈ W_{1} und w_{2} ∈ W_{2} schreiben und andererseits gilt (U_{12} ⊕ W_{1}) ∩ W_{2} = U_{1} ∩ (U_{2} ∩ W_{2}) = U_{12} ∩ W_{2} = \{\underline{0}\}.

Nach (3.21)(ii) folgt aus (∗): dim(U_{1} + U_{2}) = dim U_{12} + dim W_{1} + dim W_{2}, und aus U_{1} = U_{12} ⊕ W_{1}, U_{2} = U_{12} ⊕ W_{2}:

dim U_{1} = dim U_{12} + dim W_{1}
dim U_{2} = dim U_{12} + dim W_{2}

Subtrahiert man diese beiden Gleichungen von der vorangehenden, so folgt

dim(U_{1} + U_{2}) − dim U_{1} − dim U_{2} = − dim U_{12}

oder

dim(U_{1} + U_{2}) = dim U_{1} + dim U_{2} − dim U_{12},

wie behauptet.

Bez.: Ein Unterraum H ⊆ V heißt \underline{Hyperebene}, falls dim H = dim V − 1 gilt.

(3.23) Folgerung. Ist U ⊆ V Unterraum, H ⊆ V Hyperebene, so gilt entweder

dim(U ∩ H) = dim U − 1

oder U ⊆ H(⇔ U = U ∩ H ⇔ dim(U ∩ H) = dim U).

Bew.: Aus (3.22) folgt

(∗) dim(U ∩ H) = dim U + (dim V − 1) − dim(U + H).

Gilt dim(U + H) < dim V, so folgt aus (3.18)(iii) angewendet auf H ⊆ U + H, daß H = U +H, d.h. U ⊆ H gilt. Gilt dim(U +H) = dim V, so folgt aus (∗): dim(U ∩H) = dim U −1.

(3.24) Lemma. Ist K ein Körper und sind a_{1}, …, a_{n} ∈ K nicht alle = 0, so ist der Lösungsraum L_{I} ⊆ K^{n} der Gleichung

I a_{1}x_{1} + … + a_{n}x_{n} = 0

eine Hyperebene in K^{n}.

Bew.: Sei etwa a_{j} ≠ 0. Dann folgt durch Auflösen von I nach x_{j}:

L_{I} = \{x = (x_{1}, …, x_{n}) ∈ ℝ^{n} | x_{j} = ∑_{i≠j^{i=1}}^{n} (−\frac{a_{i}}{a_{j}} ) x_{i}\}.

Wir definieren für i ≠ j die Vektoren v_{i} = e_{i} − \frac{a_{i}}{a_{j}} e_{j} ∈ K^{n}. Dann gilt

L_{I} = span{v_{i} | i ∈ {1, …, n} \ {j}}.

Da die Vektoren v_{i}, i ≠ j, linear unabhängig sind (!), folgt dim L_{I} = n − 1.

(3.25) Satz. Sei K ein Körper und

a_{11} x_{1} + … + a_{1n} x_{n} = 0
I  ⋮  ⋮  ⋮
a_{k1} x_{1} + … + a_{kn} x_{n} = 0

ein homogenes lineares Gleichungssystem mit a_{ij} ∈ K für 1 ≤ i ≤ k, 1 ≤ j ≤ n. Dann gilt dim L_{I} ≥ n − k.

Beweis: Induktion nach k. k = 1: Nach (3.24) ist der Lösungsraum L_{I} ⊆ K^{n} einer einzigen linearen Gleichung (n−1)- dimensional, es sei denn, alle Koeffizienten der Gleichung sind 0 (und in diesem Fall gilt L_{I} = K^{n}). In jedem Fall gilt dim L_{I} ≥ n − 1.

k > 1: Es sei I′ das Gleichungssystem, das aus den ersten (k − 1) Gleichungen von I besteht, und I_{k} sei die k’te (=letzte) Gleichung von I. Dann gilt

L_{I} = L_{I′} ∩ L_{I_{k}}

Die Induktionsvoraussetzung besagt: dim L_{I′} ≥ n − k + 1. Sind alle Koeffizienten von I_{k} gleich 0, so gilt L_{I_{k}} = K^{n}, also L_{I} = L_{I′} und damit dim L_{I} = dim L_{I′} ≥ n − k + 1 > n − k. Sind nicht alle Koeffizienten von I_{k} gleich 0, so ist L_{I_{k}} nach (3.24) eine Hyperebene. Dann folgt aus (3.23), angewendet auf U = L_{I′}, H = L_{I_{k}}: dim L_{I} = dim(L_{I′} ∩ L_{I_{k}}) ≥ dim(L_{I′}) − 1 ≥ n − k.

Bez.: Eine Teilmenge A von V heißt \underline{k-dimensionaler} \underline{affiner} \underline{Unterraum}, falls es ein v ∈ V und einen k-dimensionalen Unterraum U ⊆ V gibt, so daß A = {v + u | u ∈ U} =: v + U gilt. Ist k = 1, so nennt man A eine affine Gerade, ist k = 2, eine affine Ebene und ist k = dim V − 1, eine affine Hyperebene.

Bem.: Ein affiner Unterraum A von V ist genau dann ein Unter(vektor)raum von V, wenn \underline{0} ∈ A gilt. Sind v_{0}, v_{1} ∈ V und sind U_{0}, U_{1} Unterräume von V, so gilt v_{0} + U_{0} = v_{1} + U_{1} genau dann, wenn U_{0} = U_{1} und v_{1} − v_{0} ∈ U_{0} gilt.

(3.26) Folgerung. Sei K ein Körper und I ein inhomogenes lineares Gleichungssystem mit k Gleichungen für n Unbekannte. Dann gilt entweder L_{I} = ∅ oder L_{I} ist ein affiner Unterraum von K^{n} der Dimension ≥ n − k. Insbesondere besitzt I höchstens dann genau eine Lösung (d.h. #L_{I} = 1), wenn k ≥ n gilt.

Bew.: Die Behauptung folgt durch Kombination von (1.6) mit (3.25).

Bem.: Die Aussagen von (3.25) und (3.26) kann man auch direkt mit dem Gaußschen Eliminationsverfahren einsehen.

Exkurs: Fehlerkorrigierende Codes

Lit.: MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, North-Holland, Amsterdam 1978. van Lint, J.H.: Introduction to Coding Theory (3. Aufl.), Springer 1999.

Problem: bei der Übermittlung von Daten entstehen Fehler. Gesucht ist eine Methode, die die (meisten) Fehler automatisch korrigiert.

Daten ⟶^{Kodierung} endl. Folge der Länge n von 0, 1 ⟶^{Übermittlung} fehlerhafter Folge von 0, 1 ⟶^{automat. Fehlerkorrektur} ursprüngl. Folge von 0, 1 ⟶^{Dekodierung} ursprüngl. Daten.

Das kann nur funktionieren, wenn bei der Kodierung nur spezielle Folgen von 0, 1 (“die Wörter des Codes”) verwendet werden.

Mathematische Formulierung:

{0, 1}^{n} = {(x_{1}, …, x_{n}) | x_{1} ∈ {0, 1}, …, x_{n} ∈ {0, 1}}

Folgen von 0, 1 der Länge n, z.B. (0, 1, 0, 1, 0, 1, 0) ∈ {0, 1}^{7}

Hamming-Abstand d von Elementen x, y ∈ {0, 1}^{n}

d(x, y) = #{i | 1 ≤ i ≤ n und x_{i} ≠ y_{i}} (⇒ d(x, y) ∈ {0, …, n})

Dabei wird mit #M die Anzahl der Elemente einer Menge M bezeichnet.

Bsp.: (n = 4) x = (0, 0, 1, 1), y = (0, 1, 1, 0) ⇒ d(x, y) = 2.

Eigenschaften von d: ∀x, y, z ∈ {0, 1}^{n} gilt:

(i) d(x, y) ≥ 0 und d(x, y) = 0 ⇔ x = y

(ii) d(x, y) = d(y, x) (“Symmetrie”)

(iii) d(x, y) ≤ d(x, z) + d(z, y) (“Dreiecksungleichung”) (i)-(iii) ⇔ “d ist Abstandsfunktion” Zu x ∈ {0, 1}^{n}, t ∈ ℕ sei

B(x, t) = {y ∈ {0, 1}^{n} | d(x, y) ≤ t}

der (d-)Ball um x vom Radius t. Bem.: B(x, 1) enthält genau (n + 1) Elemente. (E1) Def.:

(i) Ein Code der Länge n ist eine Teilmenge C ≠ ∅ von {0, 1}^{n}.

(ii) Ein Code C heißt t-fehlerkorrigierend ⇔

Ist x ∈ C, y ∈ C, x ≠ y, so gilt B(x, t) ∩ B(y, t) = ∅. Idee: Sei C t-fehlerkorrigierender Code. Als kodierte Nachrichten sind nur “Codewörter” x ∈ C erlaubt.

x ∈ C ⟶^{Übermittlung} \overline{x} ∈ \{0, 1\}^{n} ⟶^{automat. Korrektur} \overline{\overline{x}} ∈ C so, daß d(\overline{x}, \overline{\overline{x}}) minimal. Dann: Ist d(x, \overline{x}) ≤ t, so gilt \overline{\overline{x}} = x, da es nur ein x ∈ C mit d(\overline{x}, x) ≤ t gibt. D.h.: Sind bei der Übermittlung höchstens t Fehler aufgetreten, so ordnet die automatische Fehlerkorrektur der fehlerhaften Nachricht \overline{x} das ursprüngliche Codewort x zu. Bem.: 1) C ⊆ {0, 1}^{n} ist t-fehlerkorrigierend ⇔ Ist x ∈ C, y ∈ C und x ≠ y, so gilt d(x, y) ≥ 2t + 1 (Dreiecksungleichung!)

2) C ⊆ {0, 1}^{n} 1-fehlerkorriegierend ⇒ #C · (n + 1) ≤ 2^{n}(= #{0, 1}^{n}) Problem: Zeitaufwand Fehlerkorrektur ≈ #C · n ≈ 2^{n} Lineare Codes {0, 1}^{n} ist Vektorraum über dem Körper {0, 1} = ℤ_{2} (E2) Def. C ⊆ {0, 1}^{n} heißt linearer Code ⇔ C ist Unterraum von {0, 1}^{n} (⇔ \underline{0} ∈ C und ∀x, y ∈ C : x + y ∈ C) Sei p ∈ ℕ und n := 2^{p} − 1 (z.B. p = 5, n = 31 ⇒ 2^{n} = 3^{31} = 2 · (2^{10})^{3} = 2 · (1024)^{3} ≈ 2 · 10^{9}) Seien v_{1}, …, v_{n} die von \underline{0} ∈ \{0, 1\}^{p} verschiedenen Elemente von \{0, 1\}^{p} und F : \{0, 1\}^{n} → {0, 1}^{p} definiert durch

F (x_{1}, …, x_{n}) = x_{1}v_{1} + x_{2}v_{2} + … + x_{n}v_{n} ∈ {0, 1}^{p}

Dann gilt für alle x, y ∈ {0, 1}^{n} : F (x + y) = F (x) + F (y). Daraus folgt: C := \{x ∈ \{0, 1\}^{n} | F (x) = \underline{0}\} ist Unterraum (=linearer Code).

33

C heißt der n’te Hammingcode.

(E3) Satz. Der n’te Hammingcode ist ein 1-fehlerkorrigierender Code der Länge n

mit #C = \frac{2^{n}}{n + 1}(“C ist perfekt”)

Bew.: Seien x, y ∈ C, x ≠ y. Zu zeigen: d(x, y) ≥ 3

x, y ∈ C ⇒ (∗) (x_{1} − y_{1})v_{1} + … + (x_{n} − y_{n})v_{n} = \underline{0}.

Wegen x ≠ y existiert ein i ∈ \{1, …, n\} : x_{i} ≠ y_{i}. Dann (x_{i} − y_{i})v_{i} = v_{i} ≠ \underline{0}. Wegen (∗) existiert ein j ≠ i mit x_{j} ≠ y_{j}, also (x_{j} − y_{j})v_{j} = v_{j}. Wenn alle anderen Komponenten von x und y übereinstimmten, so wäre (∗) die Gleichung

v_{i} + v_{j} = \underline{0}

Da in ℤ_{2} 1+1 = 0 gilt, gilt v +v = \underline{0} für alle v ∈ \{0, 1\}^{n}. D.h. aus v_{i} +v_{j} = \underline{0}, folgt v_{i} = v_{j}, im Widerspruch dazu, daß die v_{i} alle verschieden sind. Also gibt es mindestens eine weitere Komponente, in der x und y nicht übereinstimmen, d.h. d(x, y) ≥ 3, wie behauptet.

Ist x ∈ \{0, 1\}^{n} und F (x) ≠ \underline{0}, so gilt F (x) = v_{i} für ein i ∈ \{1, …, n\}. Daraus folgt F (x − e_{i}) = F (x) − F (e_{i}) = \underline{0}, d.h. x − e_{i} ∈ C und d(x, x − e_{i}) = 1. Also ⋃_{x∈C} B(x, 1) = {0, 1}^{n} und damit #C · (n + 1) = 2^{n}.

Algorithmus zur Korrektur \underline{eines} Fehlers:

Sei \overline{x} ∈ \{0, 1\}^{n} die empfangene Nachricht. Berechne F (\overline{x}) ∈ \{0, 1\}^{p}.

\begin{aligned}F (\overline{x}) = \underline{0} & ⇒ & \overline{\overline{x}} := \overline{x} \\ F (\overline{x}) = v_{i} & ⇒ & \overline{\overline{x}} := \overline{x} + e_{i} \end{aligned}

Zeitaufwand ≈ n^{2}p (= 31^{2} · 5 ≈ 5 · 10^{3}) ≪ 2^{n} ≈ 2 · 10^{9})