Aufgabenblatt 1 (Lineare Algebra I) zur Vordiplom-Klausur Mathematik II (17. 9. 1998)

Professor Dr. G. Hiß, Lehrstuhl D für Mathematik Professor Dr. E. Triesch, Lehrstuhl II für Mathematik RWTH Aachen

Aufgabe 1. Beweisen Sie: Ist V ein 4-dimensionaler Vektorraum, so gibt es in V drei 2-dimensionale Untervektorräume, so daß die Summe von je zweien dieser Untervektorräume ganz V ist. (Es kommt auf eine klare Formulierung der logischen Zusammenhänge an.) 4 Punkte

Aufgabe 2. Es sei K = 𝔽_{2} der Körper mit zwei Elementen, A ∈ K^{2×5} und b ∈ K^{2×1}.

(a) Welche notwendige und hinreichende Bedingung müssen die Matrix A und die Spalte b erfüllen, damit das lineare Gleichungssystem Ax = b genau 8 Lösungen hat? (Antwort mit Beweis.)

(b) Wie viele verschiedene homogene lineare Gleichungssysteme mit 2 Gleichungen, 5 Unbekannten und genau 8 Lösungen gibt es über K? (Dabei bezeichnen wir zwei lineare Gleichungssysteme als verschieden, wenn die zugehörigen erweiterten Matrizen verschieden sind.)

(c) Wie viele verschiedene nicht homogene lineare Gleichungssysteme mit 2 Gleichungen, 5 Unbe-

kannten und genau 8 Lösungen gibt es über K? (Es kommt jeweils auf die sorgfältige Argumentation an.) 3 + 3 + 3 = 9 Punkte

Aufgabe 3. Es sei K ein Körper und n ∈ ℕ. In K^{n×n} seien symmetrische Matrizen A und B gegeben, d. h., es sei A^{t} = A ∈ K^{n×n} und B^{t} = B ∈ K^{n×n}. Beweisen Sie: Die Matrix AB ist genau dann symmetrisch, wenn AB = BA ist. 3 Punkte

Aufgabe 4. Invertieren Sie (mit dem Gauß-Algorithmus) die Matrix A = [ \begin{matrix}−9 & 2 & −6 \\ 6 & −1 & 4 \\ 19 & −4 & 13 \end{matrix} ] ∈ ℚ^{3×3}.

Sie brauchen dabei nicht anzugeben, welche elementaren Umformungen Sie benutzen, Sie müssen aber am Schluß die Matrix A^{−1} explizit angeben. Empfehlung: Vermeiden Sie bei der Rechnung Brüche. (Das Ergebnis ist ganzzahlig.) 4 Punkte

Aufgabe 5. Im Vektorraum V = ℝ^{2×2} seien die Untervektorräume

U_{1} = ⟨[ \begin{matrix}1 & 1 \\ −1 & 2 \end{matrix} ] , [ \begin{matrix}1 & 0 \\ 2 & −1 \end{matrix} ] , [ \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ]⟩ und U_{2} = ⟨[ \begin{matrix}−1 & 2 \\ 0 & 3 \end{matrix} ] , [ \begin{matrix}−1 & 2 \\ 2 & 2 \end{matrix} ] , [ \begin{matrix}0 & 1 \\ −3 & 3 \end{matrix} ]⟩

gegeben. Berechnen Sie je eine Basis für U_{1} ∩ U_{2} und U_{1} + U_{2}. Erläutern Sie dabei den Ansatz Ihrer Rechnung, und geben Sie die Basen konkret an. 5 Punkte

Aufgabenblatt 2 (Lineare Algebra I) zur Vordiplom-Klausur Mathematik II (17. 9. 1998)

Professor Dr. G. Hiß, Lehrstuhl D für Mathematik Professor Dr. E. Triesch, Lehrstuhl II für Mathematik RWTH Aachen

Aufgabe 6. Berechnen Sie die Determinante der Matrix A = [ \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 2 & 0 & 1 \\ 2 & 0 & 3 & 0 \end{matrix} ] ∈ ℤ^{4×4} mit Hilfe des Laplaceschen

Entwicklungssatzes. Entwickeln Sie dabei |A| und alle vorkommenden 3×3-Unterdeterminanten jeweils nach der letzten Zeile. (Also keine vorherigen elementaren Umformungen, Entwicklung nach anderen Zeilen oder Spalten oder Anwendung der Regel von Sarruss.) 3 Punkte

Aufgabe 7. Es seien f, g ∈ ℚ[X] mit f = X^{5} − 4X^{4} + 4X^{3} + X^{2} − 9X − 6 und g = X^{2} − 2X − 3.

(a) Dividieren Sie f mit Rest durch g. (Formulieren Sie das Ergebnis in einem Schlußsatz.)

(b) Berechnen Sie g(A) und f(A) für A = [ \begin{matrix}1 & 1 \\ 4 & 1 \end{matrix} ] ∈ ℚ^{2×2}.

4 + 3 = 7 Punkte

Für die Aufgaben 8 und 9 nehmen wir an, es sei V der Vektorraum V = ℝ^{2×2} mit der Standard-

basis B = \{v_{1}, v_{2}, v_{3}, v_{4}\} = \{[ \begin{matrix}1 & 0 \\ 0 & 0 \end{matrix} ] , [ \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} ] , [ \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ] , [ \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ]\}, und es sei T = [ \begin{matrix}0 & 1 \\ 2 & 1 \end{matrix} ] ∈ V.

Weiter sei eine Abbildung φ: V → V definiert durch φ(v) = T v für alle v ∈ V.

Aufgabe 8.

(a) Zeigen Sie, daß φ linear ist.

(b) Beweisen Sie, ohne die betreffenden Polynome zu berechnen: Die charakteristischen Polynome von T und φ sind verschieden, aber ihre Minimalpolynome sind gleich. Bestimmen Sie dazu der Reihe nach die Grade der Polynome χ_{T}, χ_{φ}, μ_{T}, μ_{φ}. (Die Begründungen sind wichtig.)

(c) Zeigen Sie, daß φ ein Automorphismus von V ist. 2 + 5 + 2 = 9 Punkte

Aufgabe 9.

(a) Nach Aufgabe 8 ist φ linear. Berechnen Sie die Abbildungsmatrix M_{B}(φ).

(b) Berechnen Sie die Eigenwerte von φ und ihre algebraischen Vielfachheiten.

(c) Berechnen Sie die Eigenräume von φ. (Achtung: Das müssen Untervektorräume von V sein.)

(d) Berechnen Sie eine Basis C von V, die aus Eigenvektoren von φ besteht, und geben Sie C, die

Basiswechselmatrix M_{B}^{C}(id_{V}) und die Abbildungsmatrix M_{C}(φ) an.

3 + 4 + 4 + 3 = 14 Punkte

Aufgabenblatt 3 (Diskrete Strukturen) zur Vordiplom-Klausur Mathematik II (17. 9. 1998)

Professor Dr. G. Hiß, Lehrstuhl D für Mathematik Professor Dr. E. Triesch, Lehrstuhl II für Mathematik RWTH Aachen

Aufgabe 10. Es sei a ≥ 1 eine natürliche Zahl. Drücken Sie die Anzahl der ungeordneten k-Zahlpartitionen n_{1} + n_{2} + ... + n_{k} = n mit n_{i} ≥ a für 1 ≤ i ≤ k durch die Partitionszahlen P_{n′,k′} aus.

7 Punkte

Aufgabe 11. Zeigen Sie, daß die Anzahl der ungeordneten k-Zahlpartitionen n_{1} + n_{2} + ... + n_{k} = n mit n_{i} ≤ ⌈\frac{n}{2}⌉ für 1 ≤ i ≤ k folgenden Wert hat:

P_{n,k} − ∑_{j=1}^{⌊ \frac{n}{2} ⌋} P_{⌊ \frac{n}{2} ⌋−j,k−1}.

9 Punkte

Aufgabe 12. Bestimmen Sie in folgendem Netzwerk N = (V, B, q, s, c) einen maximalen Fluß:

V = {x_{1}, ..., x_{9}} ∪ {q, s},
B = {(q, x_{i}), (x_{i}, s)|1 ≤ i ≤ 9} ∪ {(x_{i+1}, x_{i})|1 ≤ i ≤ 8},

c((q, x_{i})) = i, c((x_{i}, s)) = 10 − i für 1 ≤ i ≤ 9 und c((x_{i+1}, x_{i})) = 9 − i für 1 ≤ i ≤ 8. 10 Punkte

Aufgabe 13. Es sei T ein Baum mit zwei nicht adjazenten Ecken vom Grad d ≥ 3. Zeigen Sie, daß T mindestens 2d − 2 Endecken besitzt.

9 Punkte

Aufgabe 14. Die Folge (a_{n})_{n≥0} genüge der Rekursion a_{n+1} + a_{n+2} = 2a_{n} mit den Anfangsbedingungen a_{0} = 3 und a_{1} = 0. Bestimmen Sie eine explizite Darstellung dieser Folge.

7 Punkte

Aufgabenblatt 4 (Diskrete Strukturen) zur Vordiplom-Klausur Mathematik II (17. 9. 1998)

Professor Dr. G. Hiß, Lehrstuhl D für Mathematik Professor Dr. E. Triesch, Lehrstuhl II für Mathematik RWTH Aachen

Aufgabe 15. Es sei f(z) = ∑_{n=0}^{∞} a_{n} · z^{n} die erzeugende Funktion der Folge (a_{n})_{n≥0} mit a_{n} = 3 + (−2)^{n}. Welche Folge (b_{n})_{n≥0} hat die erzeugende Funktion

g(z) = \frac{f(\sqrt{z}) + f(−\sqrt{z})}{2}?

(Hinweis: Versuchen Sie es nach Möglichkeit zu vermeiden, die Funktionen f und g explizit zu berechnen.)

10 Punkte

Aufgabe 16. Die Folge (c_{n})_{n≥0} genüge der Rekursion

c_{n+3} + 3 · 10 · c_{n+2} + 3 · 100 · c_{n+1} + 1000 · c_{n} = 0

mit den Anfangsbedingungen c_{0} = 0, c_{1} = −10, c_{2} = 200 und c_{4} = 40000. Bestimmen Sie eine explizite Darstellung dieser Folge. (Beachten Sie, daß c_{3} nicht gegeben ist).

9 Punkte

Aufgabe 17. Zeigen Sie, daß ein Graph G genau dann bipartit ist, wenn für alle seine Teilgraphen H eine Menge V_{H} ⊆ V (H) mit |V_{H}| ≥ \frac{|V (H)|}{2} existiert, so daß keine zwei Ecken aus V_{H} in H adjazent sind. (Hinweis: Betrachten Sie einen Kreis ungerader Länge.) 9 Punkte