G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 3

Aufgabe 1.

(a) Für 1 ≤ i ≤ 8 sei b_{i} := e_{i} − e_{i+1} und setze X := ⟨b_{1}, …, b_{8}, v⟩_{ℤ}. In Aufgabe 1 auf Blatt 2 wurden 𝔸_{8} = ⟨b_{1}, …, b_{8}⟩_{ℤ} und 𝔸_{8}^{#} = ⟨b_{1}, …, b_{8}, u⟩_{ℤ} gezeigt, wobei u = \frac{1}{9}(8e_{1} − ∑_{i=2}^{9} e_{i}). Es ist

−3v = 2b_{1} + 4b_{2} + 6b_{3} + 5b_{4} + 4b_{5} + 3b_{6} + 2b_{7} + b_{8}

Damit ist b_{8} ∈ ⟨b_{1}, …, b_{7}, v⟩_{ℤ} und daher ist B_{1} := (b_{1}, …, b_{7}, v) eine ℤ-Basis von X. Bezüglich dieser ergibt sich die Grammatrix

( \begin{matrix}2 & −1 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & 2 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & −1 & 2 & −1 & 0 & 0 & 0 & −1 \\ 0 & 0 & −1 & 2 & −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & −1 & 2 & −1 & 0 & 0 \\ 0 & 0 & 0 & 0 & −1 & 2 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & −1 & 2 & 0 \\ 0 & 0 & −1 & 0 & 0 & 0 & 0 & 2 \end{matrix} )

wie behauptet. Also sind X und 𝔼_{8} isometrisch und wir identifizieren nun X mit 𝔼_{8}. Es ist 3u + v = 2e_{1} − e_{2} − e_{3} = 2b_{1} + b_{2} ∈ 𝔸_{8}, also 𝔼_{8} ≤ 𝔸_{8}^{#} und v + 𝔸_{8} = 3u + 𝔸_{8}. Insbesondere folgt wegen 𝔸_{8}^{#}/𝔸_{8} ≅ ℤ/9ℤ damit [𝔸_{8}^{#} : 𝔼_{8}] = [𝔼_{8} : 𝔸_{8}^{#}] = 3. Da X ganz ist, folgt 𝔸_{8} ⪇ 𝔼_{8} ≤ 𝔼_{8}^{#} ⪇ 𝔸_{8}^{#} und also 𝔼_{8} = 𝔼_{8}^{#}.

(b) Es ist z.B. B_{2} := (e_{1} − e_{2}, e_{2} − e_{3}, …, e_{6} − e_{7}, v) eine Basis von ⟨w⟩_{ℤ}^{⊥,𝔼_{8}}. Die Grammatrix bezüglich dieser Basis ist gegeben durch

( \begin{matrix}2 & −1 & 0 & 0 & 0 & 0 & 0 \\ −1 & 2 & −1 & 0 & 0 & 0 & 0 \\ 0 & −1 & 2 & −1 & 0 & 0 & −1 \\ 0 & 0 & −1 & 2 & −1 & 0 & 0 \\ 0 & 0 & 0 & −1 & 2 & −1 & 0 \\ 0 & 0 & 0 & 0 & −1 & 2 & 0 \\ 0 & 0 & −1 & 0 & 0 & 0 & 2 \end{matrix} )

wie behauptet. Also sind 𝔼_{7} und ⟨w⟩_{ℤ}^{⊥,𝔼_{8}} isometrisch. Es ist ⟨w⟩_{ℤ} < 𝔼_{8} ein reines Teilgitter, denn bezüglich der Basis B_{1} hat w die Koordinaten

(^{2} ^{4} ^{6} ^{5} ^{4} ^{3} ^{2} ^{3} )

und diese 1 × 8-Matrix hat Elementarteiler 1. Mit Satz 1.29 folgt nun det(𝔼_{7}) = det(⟨w⟩^{⊥,𝔼_{8}}) = det(⟨w⟩) = (w, w) = 2.

(c) Es ist z.B. B_{3} := (e_{1} − e_{2}, e_{2} − e_{3}, …, e_{5} − e_{6}, v) eine Basis von ⟨w, w′⟩_{ℤ}^{⊥,𝔼_{8}}. Die Grammatrix bezüglich dieser Basis ist gegeben durch

( \begin{matrix}2 & −1 & 0 & 0 & 0 & 0 \\ −1 & 2 & −1 & 0 & 0 & 0 \\ 0 & −1 & 2 & −1 & 0 & −1 \\ 0 & 0 & −1 & 2 & −1 & 0 \\ 0 & 0 & 0 & −1 & 2 & 0 \\ 0 & 0 & −1 & 0 & 0 & 2 \end{matrix} )

wie behauptet. Also sind 𝔼_{6} und ⟨w, w′⟩_{ℤ}^{⊥,𝔼_{8}} isometrisch. Es ist ⟨w, w′⟩_{ℤ} < 𝔼_{8} ein reines Teilgitter, denn bezüglich der Basis B_{1} hat die Basis (w, w′) die Koordinaten

( \begin{matrix}2 & 4 & 6 & 5 & 4 & 3 & 2 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 \end{matrix} )

und diese Matrix hat Elementarteiler 1. Mit Satz 1.29 folgt nun det(𝔼_{6}) = det(⟨w, w′⟩^{⊥,𝔼_{8}}) = det(⟨w, w′⟩_{ℤ}) = det ( \begin{matrix}2 & −1 \\ −1 & 2 \end{matrix} ) = 3.

Aufgabe 2.

(a) Seien S = ( \begin{matrix}1 & 1 & 1 \\ 1 & 0 & −2 \\ 2 & 1 & 1 \end{matrix} ) und T := ( \begin{matrix}1 & 4 & −3 \\ 3 & −2 & 3 \\ 2 & −2 & 2 \end{matrix} ). Dann sind π_{1} und π_{2} bezüglich der Standard-

basis von V = ℝ^{3} gegeben durch S_{1} := S^{−1} Diag(1, 0, 0)S = \frac{1}{2} ( \begin{matrix}−2 & −2 & −2 \\ 5 & 5 & 5 \\ −1 & −1 & −1 \end{matrix} ) bzw. S_{2} :=

S^{−1} Diag(0, 1, 1)S = \frac{1}{2} ( \begin{matrix}4 & 2 & 2 \\ −5 & −3 & −5 \\ 1 & 1 & 3 \end{matrix} ).

Daher bilden die Zeilen von T S_{i} ein Erzeugendensystem von L′_{i} = Lπ_{i}. Wegen T S_{1} = \frac{1}{2} ( \begin{matrix}21 & 21 & 21 \\ −19 & −19 & −19 \\ −16 & −16 & −16 \end{matrix} )

ist also B_{1} = (\frac{1}{2}(1, 1, 1)) eine ℤ-Basis von L′_{1}.

Weiter ist T S_{2} = \frac{1}{2} ( \begin{matrix}−19 & −13 & −27 \\ 25 & 15 & 25 \\ 20 & 12 & 20 \end{matrix} ). Durch elementare Zeilenumformungen findet man nun ein

x ∈ GL_{3}(ℤ) mit xT S_{2} = \frac{1}{2} ( \begin{matrix}1 & −1 & −7 \\ 0 & 8 & 40 \\ 0 & 0 & 0 \end{matrix} ). Daher ist B_{2} = (\frac{1}{2}(1, −1, −7), (0, 4, 20)) eine ℤ-Basis von L′_{2}.

Es ist L ∩ U_{1} der Kern von L →^{π_{2}} L′_{2}. Mit dem Elementarteilersatz findet man

( \begin{matrix}1 & 0 & 0 \\ −1 & 1 & −1 \\ 0 & −4 & 5 \end{matrix} ) · T · S_{2} · ( \begin{matrix}0 & 5 & 2 \\ 2 & 1 & −5 \\ −1 & −4 & 1 \end{matrix} ) = Diag(1/2, 4, 0) .

Also erzeugt (0, 4, −5) · T = (2, 2, 2) das Gitter L_{1} = L ∩ U_{1}.

Analog ist L ∩ U_{2} der Kern von L →^{π_{1}} L′_{1}. Mit dem Elementarteilersatz findet man

( \begin{matrix}−1 & −2 & 1 \\ 2 & −2 & 5 \\ 3 & 5 & −2 \end{matrix} ) · T · S_{1} · ( \begin{matrix}1 & −1 & −1 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ) = Diag(1/2, 0, 0) .

Also bilden (2, −2, 5) · T = (6, 2, −2) und (3, 5, −2) · T = (14, 6, 2) eine ℤ-Basis von L′_{2}.

(b) Sicher ist L′_{1}/L_{1} ≅ ℤ/4ℤ.

Bezüglich der in (a) gefundenen Basen wird die Inklusion L_{2} → L′_{2} beschrieben durch ( \begin{matrix}12 & 2 \\ 28 & 5 \end{matrix} ) und diese Matrix hat Elementarteiler (1, 4). Also ist L′_{2}/L_{2} ≅ ℤ/4ℤ.

Die Einbettung L → L′_{1} ⊕L′_{2} wird bezüglich der der in (a) gefundenen Basen beschrieben durch ( \begin{matrix}21 & −19 & −4 \\ −19 & 25 & 5 \\ −16 & 20 & 4 \end{matrix} ). Diese Matrix hat Elementarteiler (1, 1, 4). Also ist L′_{1} ⊕ L′_{2}/L ≅ ℤ/4ℤ.

Die Einbettung L_{1} ⊕L_{2} → L wird bezüglich der der in (a) gefundenen Basen beschrieben durch ( \begin{matrix}0 & 4 & −5 \\ 2 & −2 & 5 \\ 3 & 5 & −2 \end{matrix} ). Diese Matrix hat Elementarteiler (1, 1, 4). Also ist ebenfalls L/L_{1} ⊕ L_{2} ≅ ℤ/4ℤ.

Aufgabe 3.

(a) Eine Erzeugermatrix in strikter Zeilenstufenform ist z.B. gegeben durch

( \begin{matrix}1 & ω & 0 & ω & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & ω \end{matrix} ) .

Damit wird

P := ( \begin{matrix}ω & ω & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & ω \\ 0 & 0 & 1 \end{matrix} )

eine Prüfmatrix von C.

In dieser sind alle Zeilentupel der Länge 1 linear unabhängig (d.h. es gibt keine Nullzeile). Wohl aber ist das Zeilentupel der Länge 2, welches aus der 3ten und der 4ten Zeile besteht, linear abhängig. Es folgt d(C) = 2.

(b) Angenommen, es gibt eine (ohne Einschränkung) nicht-negative ganze Zahl e so, daß es zu jedem a ∈ 𝔽_{4}^{1×6} genau ein c ∈ C mit d(c, a) ≤ e gibt. Wegen C ≠ 𝔽_{4}^{1×6} ist e ≥ 1. Aber für a = (0, 0, 1, 0, 0, 0) ist dann d(0, a) = d((0, 0, 1, 1, 0, 0), a) = 1 ≤ e ein Widerspruch. Also ist C nicht perfekt.

(c) Für einen MDD haben wir in jeder Nebenklasse in 𝔽_{4}^{1×6}/C ein Element minimaler Länge zu bestimmen. Es genügt, dies bis auf 𝔽_{4}^{∗}-Vielfache durchzuführen. Betrachtet man nun sukzessive Linearkombinationen von 0, 1, 2, 3, … Zeilen von P, so ergibt sich z.B.

Syndrom s bzgl. P

Vertreter minimalen Gewichts in {x ∈ 𝔽_{4}^{1×6} | xP = s}
(0, 0, 0)  (0, 0, 0, 0, 0, 0)
(0, 0, 1)  (0, 0, 0, 0, 0, 1)
(0, 1, 0)  (0, 0, 1, 0, 0, 0)
(0, 1, 1)  (0, 0, 1, 0, 0, 1)
(0, 1, ω)  (0, 0, 0, 1, 1, 0)
(0, 1, ω^{2})  (0, 0, 0, 1, ω, 0)
(1, 0, 0)  (0, 1, 0, 0, 0, 0)
(1, 0, 1)  (0, 1, 0, 0, 0, 1)
(1, 0, ω)  (0, 1, 0, 0, 0, ω)
(1, 0, ω^{2})  (0, 1, 0, 0, 0, ω^{2})
(1, 1, 0)  (0, 1, 1, 0, 0, 0)
(1, 1, 1)  (ω^{2}, 0, 0, 0, 1, 0)
(1, 1, ω)  (ω^{2}, 0, 0, 0, ω^{2}, 0)
(1, 1, ω^{2})  (ω^{2}, 0, 0, 0, 0, 0)
(1, ω, 0)  (0, 1, ω, 0, 0, 0)
(1, ω, 1)  (1, ω^{2}, 0, 0, 0, 0)
(1, ω, ω)  (0, 1, ω, 0, 1, 0)
(1, ω, ω^{2})  (ω^{2}, 0, ω^{2}, 0, 0, 0)
(1, ω^{2}, 0)  (0, 1, ω^{2}, 0, 0, 0)
(1, ω^{2}, 1)  (0, 1, ω^{2}, 0, 0, 1)
(1, ω^{2}, ω)  (ω, ω, 0, 0, 0, 0)
(1, ω^{2}, ω^{2})  (ω^{2}, 0, ω, 0, 0, 0)

(d) Das Syndrom von x = (1, ω^{2}, 1, 1, ω, 0) ist xP = (1, ω, ω). Folglich decodiert x bzgl. unseres

MDD aus (c) zu

x − (0, 1, ω, 0, 1, 0) = (1, ω, ω^{2}, 1, ω^{2}, 0) .