G. Nebe, M. Künzer 01.09.2006

Diskrete Strukturen, SS 06

Lösung zur Vordiplomsklausur

Aufgabe 1

(1) Wir haben (\begin{matrix}5 \\ 3 \end{matrix}) = 10 Möglichkeiten.

(2) Die Konjugationsklasse von (1, 2)(3, 4)(5, 6) in S_{8} enthält \frac{8!}{2^{3}·2!·3!} = 420 Elemente.

(3) Die Anzahl der surjektiven Abbildungen von {1, 2, 3, 4, 5} nach {1, 2, 3, 4} ergibt sich zu

∑_{i=0}^{4}(−1)^{i} (\begin{matrix}4 \\ i \end{matrix}) (4 − i)^{5} = 1 · 4^{5} − 4 · 3^{5} + 6 · 2^{5} − 4 · 1^{5} + 1 · 0^{5} = 240 .

(4) Die Anzahl der normierten irreduziblen Polynome von Grad 8 in F_{3}[X] ergibt sich zu

\frac{1}{8} ∑_{d|8} 3^{d}μ(8/d) = \frac{1}{8} (−3^{4} + 3^{8}) = 810 .

Aufgabe 2 Wir erstellen einen Baum zur Berechnung von G · 2 und von Stab_{G}(2).

[figure: •; 2; a; b; •; 6; a; b; ^{•^{2} a^{2} · 2 = 2, redundant}; ^{•^{6} ba · 2 = a · 2, Erzeuger a^{−1}ba = (4, 5)}; •^{2} b · 2 = 2, Erzeuger b = (1, 3)]

Somit ist G · 2 = {2, 6}, und |G · 2| = 2 (Antwort zu (1)). Ferner ist Stab_{G}(2) = ⟨b = (1, 3), c := (4, 5)⟩. Wir erstellen einen Baum zur Berechnung von Stab_{G}(2) · 1 und von Stab_{G}(1).

[figure: •; 1; b; c; •; 3; b; c; ^{•^{1} b^{2} · 1 = 1, redundant}; ^{•^{3} cb · 1 = b · 2, Erzeuger b^{−1}cb = (4, 5)}; •^{1} c · 1 = 1, Erzeuger c = (4, 5)]

Somit ist Stab_{G}(2) · 1 = {1, 3}, und | Stab_{G}(2) · 1| = 2 (Antwort zu (2)). Ferner ist Stab_{G}(1, 2) = ⟨c = (4, 5)⟩. Direkt erkennen wir, daß Stab_{G}(1, 2) · 4 = {4, 5} und | Stab_{G}(1, 2) · 4| = 2 (Antwort zu (3)). Insgesamt wird |G| = \frac{|G|}{| Stab_{G}(1)|} · \frac{| Stab_{G}(1)|}{| Stab_{G}(1,2)|} · | Stab_{G}(1, 2)| = |G · 2| · | Stab_{G}(2) · 1| · | Stab_{G}(1, 2)| = 2 · 2 · 2 = 8 (Antwort zu (4)). Aufgabe 3

(1) Mittels des Euklidschen Algorithmus bestimmen wir Polynome s(X) und t(X) so, daß

1 = s(X) · (X^{5} + X^{2} + 1) + t(X) · (X^{2} + 1) .

Wir erhalten z.B.

1 = X · (X^{5} + X^{2} + 1) + (X^{4} + X^{2} + X + 1) · (X^{2} + 1) .

Einsetzen von δ gibt

1 = δ · (δ^{5} + δ^{2} + 1) + (δ^{4} + δ^{2} + δ + 1) · (δ^{2} + 1) = (δ^{4} + δ^{2} + δ + 1) · (δ^{2} + 1) ,

und also (δ^{2} + 1)^{−1} = δ^{4} + δ^{2} + δ + 1.

(2) Es ist F_{32}^{∗} ≃ C_{31}. Da 31 prim ist, ist diese Gruppe von jedem Element ungleich 1 erzeugt. Da δ^{2} + 1 ≠ 1, ist insbesondere δ^{2} + 1 ein Erzeuger von F_{32}^{∗}.

Aufgabe 4 Die Inzidenzmatrix unseres Graphen ist A := (\begin{matrix}1 & 2 & 1 \\ 2 & 0 & 2 \\ 1 & 2 & 1 \end{matrix}). Der Eintrag an Position (i, j) von A^{2} gibt die Anzahl der Kantenzüge der Länge 2 von i nach j. Wir müssen also alle Einträge von A^{2} aufaddieren. Da A^{2} = (\begin{matrix}6 & 4 & 6 \\ 4 & 8 & 4 \\ 6 & 4 & 6 \end{matrix}), erhalten wir 48 Kantenzüge der Länge 2. Aufgabe 5

(1) Es ist (11 − 1) · (7 − 1) = 60. Mittels Euklid ermittelt man, daß 1 = 2 · 60 − 17 · 7. Das Inverse von v = 7 in Z/60Z wird also repräsentiert von −17, oder aber, im vorgeschriebenen Intervall, von e = 43.

(2) Es ist 5^{7} ≡_{11·7} 47.

(3) Es ist 2^{43} ≡_{11·7} 30. Aufgabe 6

(1) Die Erzeugermatrix in Zeilenstufenform ist (\begin{matrix}1 & 0 & ω & ω \\ 0 & 1 & 0 & 1 \end{matrix}). Dies liefert z.B. die Prüfmatrix (\begin{matrix}ω & ω \\ 0 & 1 \\ 1 & 0 \\ 0 & 1 \end{matrix}).

(2) Es gibt in der Prüfmatrix kein linear abhängiges Zeilentupel der Länge 1 (d.h. keine Nullzeile), wohl aber ein linear abhängiges Zeilentupel der Länge 2, bestehend aus der 2-ten und der 4-ten Zeile. Somit erhalten wir den Minimalabstand d(C) = 2.

Aufgabe 7

(1) Als Nullstelle ergibt sich durch Probieren zunächst etwa β^{3}. Daraus erhalten wir die weiteren Nullstellen (β^{3})^{2} = β^{6} und (β^{3})^{4} = β^{12} = β^{5}. Da deg f = 3 ist, erhalten wir {β^{3}, β^{5}, β^{6}} als Nullstellenmenge von f(X). Alternativ hat diese Menge auch die Form {β + 1, β^{2} + β + 1, β^{2} + 1}.

(2) Es ist β eine primitive 7-te Einheitswurzel (da β ≠ 1). Deren 2 aufeinanderfolgende Potenzen β^{5} und β^{6} sind Nullstellen von f(X). Also beträgt der designierte Minimalabstand 2 + 1 = 3.

(3) Eine Prüfmatrix von C ist gegeben durch

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

In dieser ist jedes aus 2 Zeilen bestehende Tupel linear unabhängig, wie eine direkte Prüfung ergibt. Also ist d(C) ≥ 3. Hierfür kann man alternativ auch das Ergebnis aus (2) heranziehen.

Hingegen ist das aus der 1-ten, der 2-ten und der 4-ten Zeile gebildete Tupel linear abhängig. Also ist auch d(C) ≤ 3.

Im vorliegenden Fall stimmen also Minimalabstand und designierter Minimalabstand überein.

Alternativ kann man auch mit (2) und der Standarderzeugermatrix arbeiten.

(4) Der Minimalabstand ist d = d(C) = 3, die Länge ist N = 7. Die Hammingschranke ergibt sich für diese Parameter zu 7 − log_{2}(V_{2}(7, 1)) = 7 − log_{2}((\begin{matrix}7 \\ 0 \end{matrix}) + (\begin{matrix}7 \\ 1 \end{matrix})) = 7 − 3 = 4. Die Dimension von C ist ebenfalls gleich 4. Die Hammingschranke, die eine obere Schranke für diese Dimension darstellt, wird also angenommen.

Aufgabe 8

Die Aussage ist richtig. Es ist U ∩ V eine Untergruppe von U, und folglich |U ∩ V | ein Teiler von |U|. Genauso ist U ∩ V eine Untergruppe von V, und folglich |U ∩ V | ein Teiler von |V |. Da der größte gemeinsame Teiler von |U| und |V | gleich 1 ist, folgt |U ∩ V | = 1, und also U ∩ V = {1}.