Lösung Klausur I Lineare Algebra für Informatiker

Aufgabe 1.

(1) Es ist σ = (1, 9)(3, 4, 6, 5, 8), von Ordnung 10 und τ = (1, 3)(2, 4)(7, 9, 8), von Ordnung 6.

(2) Es ist σ^{5} ∘ τ^{2} = (1, 9) ∘ (7, 8, 9) = (1, 9, 7, 8).

(3) Es ist ε_{σ} = −1 und ε_{σ ∘ τ ∘ σ} = ε_{σ}ε_{τ} ε_{σ} = ε_{τ} = +1.

(4) Zum Beispiel kann man τ = (2, 3) ∘ (1, 2) ∘ (3, 4) ∘ (2, 3) ∘ (8, 9) ∘ (7, 8) schreiben.

(5) Untergruppen U ≤ S_{9} mit #U = 25 gibt es keine, da 25 kein Teiler von 9! ist, es nach Lagrange aber sein müßte.

Aufgabe 2.

(1) Der Möglichkeiten sind folgende : x ∈ {2, −3, −4, −5}. Zum Beispiel ergibt sich

{2^{m} | m ∈ Z} = {2^{m} | m ∈ [0, 9]} = {1, 2, 4, −3, 5, −1, −2, −4, 3, −5} .

(2) Da 23 eine Primzahl ist, ist F_{23} = Z/23Z ein Körper.

(3) Man kann z.B. das irreduzible Polynom f(X) = X^{2} − 3 ∈ F_{5}[X] von Grad 2 verwenden. Dies ist in der Tat irreduzibel, da es von Grad ≤ 3 ist, und da es keine Nullstellen in F_{5} = {−2, −1, 0, 1, 2} hat. Vielmehr werden f(0) = 2, f(−1) = f(1) = −2 und f(−2) = f(2) = 1. Der gesuchte Körper ergibt sich also z.B. zu F_{5}[X]/(X^{2} − 3)F_{5}[X].

(4) Es ist {(x, y, z) ∈ Z × Z × Z | x^{4} + y^{4} = 4z^{4}} = {(0, 0, 0)}. Wir haben die Annahme, es gäbe noch eine weitere Lösung, zum Widerspruch zu führen, und dürfen nach Division durch den größten gemeinsamen Teiler ohne Einschränkung von einem teilerfremden Tupel (x, y, z) ∈ Z × Z × Z ausgehen, für welches x^{4} + y^{4} = 4z^{4} ist. Modulo 5 ist x^{4} ∈ {0, 1}, und also x^{4} + y^{4} ∈ {0, 1, 2}. Modulo 5 ist aber auch 4z^{4} ∈ {0, 4}, so daß modulo 5 auf beiden Seiten 0 stehen muß. Dies führt wiederum zu x^{4} ≡_{5} y^{4} ≡_{5} z^{4} ≡_{5} 0, und dies schließlich zu x ≡_{5} y ≡_{5} z ≡_{5} 0, im Widerspruch zu (x, y, z) teilerfremd.

Aufgabe 3.

(1) Eine Basis von T ∩ U ist z.B. durch ((\begin{matrix}1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix})) gegeben.

Damit wird dim_{F_{2}}(T + U) = dim_{F_{2}} T + dim_{F_{2}} U − dim_{F_{2}}(T ∩ U) = 3 + 3 − 2 = 4. Ferner ist die Summe T + U wegen T ∩ U ≠ 0 nicht direkt.

(2) Eine ergänzte Basis von T ist z.B. durch ((\begin{matrix}1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 1 \\ 1 \\ 1 \end{matrix})) gegeben, eine ergänzte Basis von U z.B. durch

((\begin{matrix}1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix})), und folglich eine ergänzte Basis von T + U z.B. durch ((\begin{matrix}1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 1 \\ 1 \\ 1 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix})).

Aufgabe 4.

(1) Bezüglich der Standardbasis \underline{e} von R^{3} ist A(φ)_{\underline{e},\underline{e}} = (\begin{matrix}0 & 1 & 1 \\ −1 & 2 & 1 \\ 1 & −1 & 0 \end{matrix}) und dementsprechend A(φ^{2})_{\underline{e},\underline{e}} = (A(φ)_{\underline{e},\underline{e}})^{2} =

(\begin{matrix}0 & 1 & 1 \\ −1 & 2 & 1 \\ 1 & −1 & 0 \end{matrix}). Es ist z.B. ((\begin{matrix}−1 \\ −1 \\ 1 \end{matrix})) eine Basis von Kern φ und z.B. ((\begin{matrix}0 \\ −1 \\ 1 \end{matrix}) , (\begin{matrix}1 \\ 2 \\ −1 \end{matrix})) eine Basis von Im φ.

(2) Es ist φ(1) = 0, φ(X) = 1 und φ(X^{2}) = 2X+2, und somit ist bezüglich der Basis \underline{y} = (1, X, X^{2}) die beschreibende

Matrix gegeben durch A(φ)_{\underline{y},\underline{y}} = (\begin{matrix}0 & 1 & 2 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{matrix}), und somit A(φ^{2})_{\underline{y},\underline{y}} = (A(φ)_{\underline{y},\underline{y}})^{2} = (\begin{matrix}0 & 0 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}). Es ist z.B. (1) eine Basis von Kern φ und z.B. (1, X) eine Basis von Im φ.

(3) Es ist φ(1) = 1 + β, φ(β) = β^{4} + β^{2} = β und φ(β^{2}) = β^{8} + β^{3} = 1. Bezüglich der Basis \underline{y} = (1, β, β^{2}) von V

erhalten wir somit A(φ)_{\underline{y},\underline{y}} = (\begin{matrix}1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}) und somit A(φ^{2})_{\underline{y},\underline{y}} = (A(φ)_{\underline{y},\underline{y}})^{2} = (\begin{matrix}1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix}). Es ist z.B. (1 + β + β^{2}) eine Basis von Kern φ und z.B. (1, β) eine Basis von Im φ.

Aufgabe 5.

(1) Mit A := (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & α & α \end{matrix}) wird A^{2} = (\begin{matrix}1 & α & α \\ 0 & 1 & 0 \\ α & 1 & α \end{matrix}), A^{3} = (\begin{matrix}α & 1 & α \\ 0 & 1 & 0 \\ α & α & 1 \end{matrix}), A^{4} = (\begin{matrix}α & α & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}) und A^{5} = (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}).

Also ist die gefragte Ordnung gleich 5.

(2) Es ist GL_{2}(F_{2}) = \{(\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) , (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}) , (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , (\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}) , (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}) , (\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix})\}.

Von diesen Elementen haben (\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}) und (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}) die Ordnung 3.

Aufgabe 6.

(1) Da jeder der beiden Standardbasisvektoren beliebig auf einen der 2^{3} Vektoren in W abgebildet werden kann, gibt es (2^{3})^{2} = 2^{6} = 64 lineare Abbildungen von V nach W. Alternative Begründung: Die Menge der linearen Abbildungen von F_{2}^{2} nach F_{2}^{3} steht über die beschreibende Matrix in Bijektion zu F_{2}^{3×2}, und diese Menge hat 2^{3·2} Elemente.

(2) Für die Injektivität muß das Bildtupel der Basis linear unabhängig sein. Dafür gibt es (2^{3} − 1)(2^{3} − 2) = 42 Möglichkeiten. Es gibt also 42 injektive lineare Abbildungen von F_{2}^{2} nach F_{2}^{3}. Für die Surjektivität müßte das Bildtupel erzeugend in F_{2}^{3} sein. Dies geht nicht, da in F_{2}^{3} jedes erzeugende Tupel von Länge > 3 ist. Folglich gibt es keine surjektiven linearen Abbildungen von F_{2}^{2} nach F_{2}^{3}. Alternative Begründung: Es gibt überhaupt keine surjektiven Abbildungen von F_{2}^{2} nach F_{2}^{3}, da #(F_{2}^{2}) = 4 < 8 = #(F_{2}^{3}).

(3) Von Dimension 0 gibt es einen Untervektorraum, von Dimension 3 ebenso. Von Dimension 1 gibt es (8 − 1)/(2 − 1) = 7 Untervektorräume. Von Dimension 2 gibt es ((8 − 1)(8 − 2))/((4 − 1)(4 − 2)) = 7 Untervektorräume. Insgesamt gibt es in F_{2}^{3} also 16 Untervektorräume.

Aufgabe 7.

(1) Aussage ist falsch. Seien etwa K = R, V = R^{2}, W = R^{1}, n = 2, (x_{1}, x_{2}) = ((\begin{matrix}1 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 0 \end{matrix})) und

f : V \overline{}W : (\begin{matrix}ξ_{1} \\ ξ_{2} \end{matrix} ) \overline{}(ξ_{1}). Es ist (f(x_{1}), f(x_{2})) = ((1), (0)) erzeugend in W, wiewohl (x_{1}, x_{2}) nicht erzeugend in V ist. Kleineres Gegenbeispiel: K = R, V = R^{1}, W = R^{0} = 0, n = 1, (x_{1}) = ((0)) und f : V \overline{}W : (ξ_{1}) \overline{}0.

(2) Aussage ist wahr. In der Tat ist zunächst

dim_{K}(U_{1} ∩ U_{2}) = dim_{K} U_{1} + dim_{K} U_{2} − dim_{K}(U_{1} + U_{2}) ≥ 3 + 3 − 4 = 2 ,

und daher

dim_{K}((U_{1} ∩ U_{2}) ∩ U_{3}) = dim_{K}(U_{1} ∩ U_{2}) + dim_{K} U_{3} − dim_{K}((U_{1} ∩ U_{2}) + U_{3}) ≥ 2 + 3 − 4 = 1 .

(3) Aussage ist falsch. Seien etwa G = S_{3} und m = 6 = #G. Die Elemente von S_{3} haben Ordnung 1, 2 oder 3, aber nicht 6.

(4) Aussage ist wahr. Denn durch Abdividieren sämtlicher Nullstellen in F_{p} sieht man, daß

X^{p} − X = f(X) · ∏_{a∈F_{p}}(X − a)

ist für ein f(X) ∈ F_{p}[X]. Vergleich von Graden und Leitkoeffizienten gibt f(X) = 1.

(5) Aussage ist wahr. Schreibe f(X) := ∑_{j≥0} a_{j}X^{j}, m := deg f und f̃(X) := ∑_{j≥0} a_{j}^{3}X^{j}. Aus f(X) normiert folgt f̃(X) normiert. Sei f̃(X) = g(X) · h(X) angesetzt, g(X) = ∑_{j≥0} b_{j}X^{j}, h(X) = ∑_{j≥0} c_{j}X^{j}. Wir haben zu zeigen, daß deg g = 0 oder deg h = 0 ist. Nun ist aber

f(X) = ∑_{j≥0} a_{j}X^{j} = ∑_{j≥0}(a_{j}^{3})^{3}X^{j} = (∑_{j≥0} b_{j}^{3}X^{j}) (∑_{j≥0} c_{j}^{3}X^{j}) ,

und aus f(X) irreduzibel folgt deg (∑_{j≥0} b_{j}^{3}X^{j}) = 0 oder deg (∑_{j≥0} c_{j}^{3}X^{j}) = 0, und mithin deg g = 0 oder deg h = 0.