Aufgabenblatt 1 (Lineare Algebra I) zur Vordiplom-Klausur Mathematik II (16. 9. 1999)

Professor Dr. U. Schoenwaelder, Lehrstuhl D für Mathematik Priv.-Doz. Dr. R. Winkel, Lehrstuhl für Mathematik und Institut für Reine und Angewandte Mathematik, RWTH Aachen

Aufgabe 1.

(a) Geben Sie ein Beispiel V eines 16-dimensionalen Vektorraums, dessen Elemente Abbildungen sind. (Vergessen Sie nicht die formal korrekte Angabe der Operationen.)

(b) Geben Sie Teilräume A, B Ihres Vektorraums V an, die die Dimensionen 3 und 4 haben und wo S := A + B die Dimension 5 hat. Welche Dimension hat D := A ∩ B? 4 + 2 = 6 Punkte

Aufgabe 2. Stellen Sie sich einen Vektorraum mit einer endlichen Basisfolge B als gegeben vor. Weiter seien Teilräume A und B durch endliche Folgen von Erzeugenden gegeben, die überdies als Linearkombinationen in der Basisfolge B dargestellt sind. Wie prüft man, ob A ein Teilraum von B ist? 4 Punkte

Aufgabe 3. Je nach Wahl des reellen Parameters t hat das lineare Gleichungssystem

\begin{aligned}1 & · & x_{1} & + & 0 & · & x_{2} & − & (t + 1) & · & x_{3} & = & −2 \\ 0 & · & x_{1} & + & t & · & x_{2} & + & 0 & · & x_{3} & = & t \\ 1 & · & x_{1} & − & t & · & x_{2} & + & 0 & · & x_{3} & = & 2 − t \end{aligned}

unterschiedliche Lösungsmengen.

(a) Für welche Werte von t ist das Gleichungssystem lösbar?

(b) Berechnen Sie in den lösbaren Fällen jeweils die Lösungsmenge M und schreiben Sie sie als

Element eines Faktorraums F von ℝ^{3×1}. Welche Dimension hat F?

3 + 6 = 9 Punkte

Aufgabe 4. Lösen Sie das folgende lineare Gleichungssystem so gut wie es geht.

\begin{aligned}3 x & + & 5 y & = & 1 \\ 6 x & + & 10 y & = & 7. \end{aligned}

5 bis 7 Punkte

Aufgabe 5. Wir betrachten die quadratischen Matrizen

A_{1} = [ \begin{matrix}1 & 2 & 0 \\ 0 & 1 & 0 \\ 3 & −1 & 0 \end{matrix} ] , A_{2} = [ \begin{matrix}3 & 3 & 8 \\ 3 & 2 & 8 \\ 8 & 8 & 22 \end{matrix} ] , A_{3} = [ \begin{matrix}1 & 0 & −1 \\ 0 & 2 & 2 \\ −1 & 2 & 3 \end{matrix} ] ∈ ℝ^{3×3}.

(a) Berechnen Sie (multiplikativ) inverse Matrizen zu diesen Matrizen.

(b) Welche der durch α_{i} := (x ↦ A_{i} x für x ∈ ℝ^{3×1}) : ℝ^{3×1} → ℝ^{3×1} definierten Abbildungen α_{1}, α_{2}, α_{3} sind linear, welche injektiv, welche Isomorphismen?

(c) Auf einem 3-dimensionalen ℝ-Vektorraum V mit einer Basisfolge B seien zwei Skalarprodukte Φ und Ψ durch ihre Matrizen ^{B}Φ_{B} = A_{2} und ^{B}Ψ_{B} = A_{3} gegeben. Welche dieser Skalarprodukte sind nicht ausgeartet, welche positiv definit? (Begründung.)

6 + 3 + 5 = 14 Punkte

Aufgabenblatt 2 (Lineare Algebra I) zur Vordiplom-Klausur Mathematik II (16. 9. 1999)

Professor Dr. U. Schoenwaelder, Lehrstuhl D für Mathematik Priv.-Doz. Dr. R. Winkel, Lehrstuhl für Mathematik und Institut für Reine und Angewandte Mathematik, RWTH Aachen

Aufgabe 6. Es sei V = ℝ^{1×5}.

Gibt es eine lineare Abbildung φ: V → V mit Kern φ < Bild φ?

Gibt es eine lineare Abbildung φ: V → V mit Kern φ = Bild φ?

Gibt es eine lineare Abbildung φ: V → V mit Kern φ > Bild φ? (Antwort jeweils mit Beispiel oder Beweis.) 3 Punkte

Aufgabe 7.

Zur reellen 3 × 5-Matrix A = [ \begin{matrix}1 & 1 & 0 & 3 & 1 \\ 1 & −1 & −2 & −1 & −1 \\ −1 & 0 & 1 & −1 & 0 \end{matrix} ] betrachten wir die lineare Abbildung φ =

(x ↦ Ax für x ∈ ℝ^{5×1}): ℝ^{5×1} → ℝ^{3×1}. Berechnen Sie eine Basisfolge von ℝ^{3×1}/Bild φ. 6 Punkte

Aufgabe 8. In einem n-dimensionalen K-Vektorraum V seien Basisfolgen B, C und D sowie eine lineare Abbildung φ und eine Bilinearform Φ gegeben, so dass _{D}id_{B} = ^{C}Φ_{C} = A ∈ K^{n×n} und _{D}id_{C} = _{B}φ_{B} = B ∈ K^{n×n} gilt. Berechnen Sie für die Matrizen _{C}φ_{C} und ^{B}Φ_{B} jeweils eine Formel, die die gesuchte Matrix in A und B ausdrückt (und keine Klammern enthält). 5 Punkte

Aufgabe 9.

(a) Geben Sie ein Beispiel eines ℝ-Vektorraums V mit einer nicht ausgearteten Bilinearform Φ und einem Teilraum W ≤ V, für den V nicht die (innere) direkte Summe der Teilräume W und W^{⊥} ist.

(b) Gilt in Ihrem Beispiel die Formel dim W + dim W^{⊥} = dim V ? 4 + 1 = 5 Punkte

Aufgabe 10. Auf dem reellen Intervall I = [ 0, 1 ] sei die Funktion f = (x ↦ −x^{2} + 1) : I → I gegeben. Stellen sie sich vor, jemand fragt Sie: Welche der beiden Polynomfunktionen g = (x ↦ −x + 1) : I → I und h = (x ↦ −x + \frac{5}{4}) : I → I vom Grad 1 approximiert f ”besser“? Da Sie wegen Ihrer Klausur wenig Zeit haben, überlassen Sie ihm das Rechnen und sagen ihm nur, welche Ausdrücke er ausrechnen soll. Welche? 4 Punkte

Aufgabe 11. Wie viele Geraden hat ein 3-dimensionaler affiner Raum (also ein affiner Raum über einem 3-dimen-sionalen Vektorraum) über dem Körper ℤ_{2}? (Wie ergibt sich diese Anzahl?) 4 Punkte

Aufgabe 12. Wegen 4711 = 7·673 ist der Restklassenring ℤ_{4711} = ℤ/4711 ℤ kein Körper. Trotzdem besitzt die Restklasse, in der die Zahl 205 liegt, ein (multiplikativ) inverses Element (warum?). Berechnen Sie es (und erläutern Sie dabei Ihre Rechnung). 5 Punkte

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

Professor Dr. U. Schoenwaelder, Lehrstuhl D für Mathematik Priv.-Doz. Dr. R. Winkel, Lehrstuhl für Mathematik und Institut für Reine und Angewandte Mathematik, RWTH Aachen

Aufgabe 13. Formulieren Sie den Satz von Dilworth für den Spezialfall eines Spernerposets P, und verifizieren Sie ihn am Hassediagramm eines rangsymmetrischen Spernerposets ihrer Wahl, welches B_{3} (=Poset der Teilmengen von {1, 2, 3}) als echtes induziertes Unterposet enthält. 7 Punkte

Aufgabe 14.

(a) Zeichnen Sie die Hassediagramme des Posets P = \underline{1} ⊕ (\underline{2} + \underline{2}) ⊕ \underline{1} und des Posets O(P) aller Ideale von P. Geben Sie den Elementen von P geeignete Namen und notieren Sie an jedem Element von O(P) die Elemente des entsprechenden Ideals von P; unterstreichen Sie dabei die Elemente der erzeugenden Antikette.

(b) Charakterisieren Sie für beliebige Posets P und Q die Elemente von O(P ⊕ Q) mit Hilfe der Elemente von O(P) und O(Q). 6 + 4 = 10 Punkte

Aufgabe 15. Beweisen Sie einmal algebraisch und dann kombinatorisch mit Hilfe von Teilmengen:

\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n − k}{r − k} für n, r, k ∈ ℕ_{0} = \{0, 1, 2, …\}

und leiten Sie daraus ab:

∑_{k=0}^{r} \binom{n}{k}\binom{n − k}{r − k} = 2^{r}\binom{n}{r} .

8 Punkte

Aufgabe 16. N.N. behauptet: “Die Anzahl der k-Multimengen, die man aus einer n-Menge bilden kann, ist \frac{n^{k}}{k!} , weil ....”

(a) Was hat N.N. vermutlich als Begründung gegeben und was ist daran verkehrt?

(b) Welches ist die richtige Anzahl? Ist diese ≥ oder ≤ als \frac{n^{k}}{k!} , oder hängt das von n und k ab?

(c) Geben Sie einen Beweis des richtigen Ergebnisses. 4 + 2 + 3 = 9 Punkte

Aufgabe 17. Eine Zählfunktion f : ℕ_{0} ⟶ ℂ habe die rationale erzeugende Funktion

∑_{n≥0} f(n)x^{n} = \frac{p(x)}{q(x)} = \frac{−4x^{3} + 4x^{2} + 7x + 2}{4x^{4} − 4x^{3} − 3x^{2} + 2x + 1} .

Bestimmen Sie eine Rekursionformel (inklusive Anfangsbedingungen) und eine explizite Darstellung für f. 12 Punkte

Aufgabenblatt 4 (Diskrete Strukturen) zur Vordiplom-Klausur Mathematik II (16. 9. 1999)

Professor Dr. U. Schoenwaelder, Lehrstuhl D für Mathematik Priv.-Doz. Dr. R. Winkel, Lehrstuhl für Mathematik und Institut für Reine und Angewandte Mathematik, RWTH Aachen

Aufgabe 18. Für jede natürliche Zahl n sei

L_{n} := {(l_{1}, …, l_{n}) ∈ ℕ_{0}^{n} | 0 ≤ l_{i} ≤ n − i, i = 1, …, n}

und S_{n} die Menge der Permutationen von {1, …, n}.

(a) Zeigen Sie, dass die Abbildung L : S_{n} ⟶ L_{n} definiert durch

l_{i} = l_{i}(π) := ♯{j | i < j, π(i) > π(j)} für i = 1, …, n

eine Bijektion mit l_{1} + … + l_{n} = l(π) [l(π) die Länge von π] ist.

(b) Berechnen Sie L(π) für π = 4163752 ∈ S_{7} und L^{−1}(3, 6, 4, 0, 2, 1, 1, 0) ∈ S_{8}.

6 + 2 = 8 Punkte

Aufgabe 19. Bestimmen Sie für das nachstehend abgebildete Netzwerk zwei maximale Flüsse mit verschiedenen zugehörigen minimalen Schnitten L = (A, \overline{A}):

[figure: a; c_{1}; c_{2}; c_{3}; b; d; g; h; j; m_{1}; m_{2}; z] 1520 25  15 15 1015 20 10  15 1515 15 15  20 10  10 1515 5  10  25 25

Überprüfen Sie, dass es sich bei Ihren Lösungen tatsächlich um Flüsse handelt und dass in beiden Fällen die maximalen Flussstärken mit den minimalen Kapazitäten übereinstimmen; markieren Sie alle für die Berechnung der Kapazität relevanten Kanten. 12 Punkte

Aufgabe 20.

(a) Geben Sie den Satz von Turan an und folgern Sie daraus, dass jeder Graph mit 2n Ecken und n^{2} + 1 oder mehr Kanten einen K_{3} als Untergraph enthält.

(b) Zeigen Sie, dass jeder 3-reguläre Graph G eine gerade Eckenzahl hat, und bestimmen Sie die Anzahl der Kanten von G.

(c) Zeigen Sie mit Hilfe von (a) und (b), dass es (bis auf Isomorphie) nur einen 3-regulären Graphen mit 4 Ecken geben kann. 4 + 2 + 2 = 8 Punkte