Aufgabenblatt 1 (Lineare Algebra I) zur Vordiplom-Klausur Mathematik II (15. 3. 1999)

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

Aufgabe 1. Gegeben seien zwei Vektorräume V und W, ein Untervektorraum U von W und eine lineare Abbildung φ: V → W. Beweisen Sie: φ^{−1}(U) := {v ∈ V | φ(v) ∈ U} ist ein Untervektorraum von V. 4 Punkte

Aufgabe 2. Untersuchen Sie

(a) im Fall V = ℚ^{1×2},

(b) im Fall V = 𝔽_{2}^{1×2}, ob die Abbildung φ: V → V, [ a, b] ↦ [ a + b, a^{2} + b^{2} ] linear ist. 2 + 3 = 5 Punkte

Aufgabe 3.

(a) Gegeben seien zwei lösbare, nicht homogene lineare Gleichungssysteme über einem endlichen Körper K, das eine mit 2 Gleichungen und 4 Unbekannten, das andere mit 4 Gleichungen und 2 Unbekannten. Können die beiden Systeme gleich viele Lösungen haben?

(b) Untersuchen Sie die gleiche Frage für den Fall, dass die beiden Systeme über verschiedenen

endlichen Körpern K_{1} und K_{2} gegeben sind. Antwort jeweils mit Beweis der Unmöglichkeit oder konkretem Beispiel. 4 + 3 = 7 Punkte

Aufgabe 4.

Gegeben sei die Matrix A = [ \begin{matrix}2 & 1 & a & 3 \\ 2 & a & 1 & 0 \\ a & 2 & 0 & 4 \\ 2 & 1 & 3 & 0 \end{matrix} ] ∈ ℝ^{4×4}.

(a) Berechnen Sie die Determinante von A mit Hilfe des Laplaceschen Entwicklungssatzes. Entwickeln Sie dabei |A| und alle vorkommenden 3 × 3-Unterdeterminanten jeweils nach der letzten Spalte. (Also keine vorherigen elementaren Umformungen, Entwicklung nach anderen Spalten oder Zeilen oder Anwendung der Regel von Sarruss.)

(b) Für welche a ∈ ℝ ist A invertierbar, für welche nicht?

(c) Für welche a ∈ ℤ ist A ganzzahlig invertierbar? Antwort jeweils mit Begründung. 4 + 1 + 1 = 6 Punkte

Aufgabe 5. Es sei K ein Körper mit char (K) ≠ 2, und es sei A ∈ K^{n×n} mit n ∈ ℕ.

(a) Es sei det (A) = d. Berechnen Sie det (−A).

(Geben Sie nicht nur das Ergebnis an, sondern begründen Sie es.)

(b) Zeigen Sie: Wenn n eine ungerade Zahl ist, gilt: Ist A^{t} = −A, so ist A nicht invertierbar. (Wo geht hier die Charakteristik von K ein?)

(c) Zeigen Sie: Wenn n eine gerade Zahl ist, gilt die Aussage in (b) nicht. (Betrachten Sie zunächst den Fall n = 2.) 2 + 3 + 3 = 8 Punkte

Aufgabenblatt 2 (Lineare Algebra I) zur Vordiplom-Klausur Mathematik II (15. 3. 1999)

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

Aufgabe 6. Im ℝ-Vektorraum V der reellen Polynome vom Grad ≤ 3 seien zwei Basen B = (v_{1}, v_{2}, v_{3}, v_{4}) und

C = (w_{1}, w_{2}, w_{3}, w_{4}) mit der Basiswechselmatrix M_{B}^{C}(id_{V}) = [ \begin{matrix}1 & −1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ −1 & 1 & 0 & 0 \\ 1 & −1 & 1 & 0 \end{matrix} ] sowie zwei Untervektorräume

U_{1} = ⟨ v_{1} + 3v_{2} + v_{4}, v_{1} − 3v_{3} + v_{4}, v_{1} + 4v_{2} + v_{3} + v_{4} ⟩,

U_{2} = ⟨ w_{1} − w_{3} + w_{4}, w_{2} + 2w_{3} − 2w_{4} ⟩

gegeben.

(a) Stellen Sie die Erzeugenden von U_{2} als Linearkombinationen aus B dar.

(b) Berechnen Sie mit Hilfe des Zassenhaus-Algorithmus eine Basis von U_{1} ∩ U_{2} und eine Basis von U_{1} + U_{2}. (Erläutern Sie Ihre Rechnung außerhalb des eigentlichen Zassenhaus-Schemas, insbesondere den Ansatz, und geben Sie die resultierenden Basen an.)

(c) Berechnen Sie nun die Basiswechselmatrix M_{C}^{B}(id_{V}).

(d) Es seien w_{1} = X^{3} − X^{2} + 1 und w_{2} = X^{2} − X + 1. Berechnen Sie eine Darstellung des Durchschnitts U_{1} ∩ U_{2} als \underline{Men}g\underline{e} von Polynomen. (Wenn Sie sich beim Zassenhaus-Algorithmus nicht verrechnet haben, geht das.) 4 + 5 + 3 + 3 = 15 Punkte

Aufgabe 7.

Es sei ℂ der Körper der komplexen Zahlen und A = [ \begin{matrix}0 & 0 & −1 \\ 2 & 2 & 1 \\ 3 & −1 & 0 \end{matrix} ] ∈ ℂ^{3×3}.

(a) Berechnen Sie die Eigenwerte von A.

(b) Zeigen Sie, ohne irgendwelche Potenzen von A auszurechnen, dass A^{5} gleich 16 ·A ist. (Auf die Argumentation kommt es an.) 4 + 3 = 7 Punkte

Aufgabe 8. Es sei V = ℝ^{1×3} und φ: V → V der durch φ( [ a, b, c] ) = [ 5a + 2c, 2a + 3b + 2c, −4a − c] definierte Endomorphismus von V.

(a) Bestimmen Sie die Abbildungsmatrix M_{B}(φ) von φ bezüglich der Standardbasis B von V.

(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.

1 + 3 + 4 + 3 = 11 Punkte

Aufgabe 9. Es sei K ein Körper, a ∈ K und A = [ \begin{matrix}a & 0 \\ 0 & a \end{matrix} ]. Bestimmen Sie die Menge aller zu A ähnlichen Ma-

trizen aus K^{2×2}. (Antwort mit Beweis.) 3 Punkte

Aufgabenblatt 3 (Diskrete Strukturen) zur Vordiplom-Klausur Mathematik II (15. 3. 1999)

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

Aufgabe 10. Es seien a_{1}, ..., a_{n} beliebige natürliche Zahlen. Zeigen Sie die folgenden Aussagen.

a) Zwei der Zahlen aus der Menge N = {0, a_{1}, a_{1} + a_{2}, ..., a_{1} + a_{2} + ... + a_{n}} ergeben bei Division durch n denselben Rest.

b) Es gibt zwei Zahlen 0 ≤ k < l ≤ n, so dass ∑_{i=k+1}^{l} a_{i} ein Vielfaches von n ist. 8 Punkte

Aufgabe 11. Es sei a_{n} für n ∈ ℕ die Anzahl der Mengen S ⊆ {1, ..., n} mit der Eigenschaft, dass

{x, x + 1| x ∈ S} = {1, ..., n}

ist. Drücken Sie die Zahlen a_{n} für n ∈ ℕ mit Hilfe der Fibonacci-Zahlen aus. (Hinweis: Beweisen Sie eine Rekursion für die a_{n}.) 8 Punkte

Aufgabe 12. Gegeben sei eine Folge von Graphen (G_{n})_{n≥1}, so dass G_{1} = ({v_{1}}, ∅) und für n ≥ 2 der Graph G_{n} = (V_{n}, E_{n}) aus G_{n−1} = (V_{n−1}, E_{n−1}) entsteht, indem man zu V_{n−1} eine Ecke v_{n} hinzufügt und mit mehr als \frac{n−1}{2} Ecken von G_{n−1} verbindet, d.h. |N(v_{n})| > \frac{n−1}{2}. Zeigen Sie, dass G_{n} für n ≥ 3 hamiltonsch ist. 8 Punkte

Aufgabe 13. Zeigen Sie, dass P_{n,k} für n, k ∈ ℕ die Anzahl der ungeordneten Zahlpartitionen

n + k^{2} − k = n_{1} + n_{2} + ... + n_{k}

von n + k^{2} − k in genau k Summanden ist, für die |n_{i} − n_{j}| ≥ 2 für alle 1 ≤ i < j ≤ k gilt. 9 Punkte

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

7 Punkte

Aufgabenblatt 4 (Diskrete Strukturen) zur Vordiplom-Klausur Mathematik II (15. 3. 1999)

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

Aufgabe 15. Die Mengen A_{1}, ..., A_{n} ⊆ {1, ..., n} mit n ∈ ℕ bilden eine ”Kette“, falls A_{i} ⊆ A_{i+1} und A_{i} ≠ A_{i+1} für 1 ≤ i ≤ n − 1 gilt. Zeigen Sie die folgenden Aussagen.

a) Für jede Kette A_{1}, ..., A_{n} gilt |A_{i}| = i für 1 ≤ i ≤ n, und es gibt genau n! verschiedene Ketten.

b) Zu einer Menge B ⊆ {1, ..., n} gibt es genau |B|! · (n − |B|)! verschiedene Ketten A_{1}, ..., A_{n} mit A_{|B|} = B.

c) Gilt für die Mengen B_{1}, ..., B_{m} ⊆ {1, ..., n}, dass B_{i} ⊈ B_{j} für 1 ≤ i ≠ j ≤ m, dann gilt

∑_{i=1}^{m} \frac{1}{\binom{n}{|B_{i}|}} ≤ 1. 12 Punkte

Aufgabe 16. Es sei G = (U ∪ W, E) ein bipartiter Graph mit den Partitionsmengen U und W mit |U| = |W | = n. Es sei d(x, G) = |N(x, G)| ≥ \frac{n}{2} für alle x ∈ U ∪ W. Zeigen Sie, dass G ein perfektes Matching besitzt. (Hinweis: Betrachten Sie eine minimale Eckenüberdeckung.) 8 Punkte

Aufgabe 17. Bestimmen Sie einen maximalen Fluss und einen minimalen Schnitt in dem Netzwerk N = (V, B, q, s, c)

mit V = {q = 1, 2, 3, ..., 8, s = 9},

B = {(1, 2), (1, 5), (2, 3), (2, 6), (2, 9), (3, 4), (4, 7), (5, 4),
(5, 7), (5, 8), (6, 3), (6, 7), (7, 9), (8, 6), (8, 9)},

c((1, 2)) = 5, c((1, 5)) = 10, c((2, 3)) = 1, c((2, 6)) = 2, c((2, 9)) = 1, c((3, 4)) = 2, c((4, 7)) = 7, c((5, 4)) = 5, c((5, 7)) = 2, c((5, 8)) = 3, c((6, 3)) = 3, c((6, 7)) = 1, c((7, 9)) = 8, c((8, 6)) = 2 und c((8, 9)) = 1. 8 Punkte