Probeklausur

MATHEMATIK FÜR INFORMATIKER I (WS 2000/01)

1. Aufgabe: Kreuze bei den folgenden Aussagen an, ob sie richtig oder falsch sind. Eine Begründung ist nicht erforderlich! (Für eine falsche Antwort gibt es keine Minuspunkte!)

Aussage  richtig falsch

1 Für jede reelle Zahl x gilt ⌊x⌋ ≠ ⌈x⌉

√

2 Es gibt eine injektive Abbildung {1, 2, 3, 4, 5, 6} ⟶ {2, 4, 6, 8, 10}

√

3 Die Aussage (P ∨ Q) ∨ (¬P ∧ ¬Q) ist allgemeinrichtig

√

4 Jedes homogene LGS, das weniger Gleichungen als Unbekannte hat, besitzt eine Lösung, die von der Nullspalte verschieden ist

√

5 Die Menge {1, 2, 3, 5, 6} besitzt genau 64 Teilmengen

√

6 Eine Äquivalenzrelation ist insbesondere antisymmetrisch

√

7 Die Lösungsmenge eines inhomogenen LGS’s für n Unbekannte über einem Körper K ist ein Unterraum von K^{n}

√

8 Die Mengen IN und IN \ {100} sind gleichmächtig

√

9 P(M) ist eine Teilmenge von M

√
10 Es ist φ(101) = 100  √

11 Die Restklasse von 9 modulo 24 ist invertierbar

√

12 Eine (6 × 7)–Matrix kann den Rang 7 haben

√

13 Der Rang einer Matrix A ist gleich der Anzahl der Einheitsvektoren, die unter den Spalten der Treppenmatrix T (A) vorkommen

√

Lösungsvorschlag: Die richtigen Antworten sind in der obigen Tabelle markiert.

Einige Anmerkungen zur Begründung (sind zur Lösung der Aufgabe ausdrücklich nicht gefordert):

1. Vgl. 2. Übungsblatt, Aufgabe 4: ⌈x⌉ = ⌊x⌋ genau dann, wenn x ∈ ℤ ⊂ ℝ.

2. Der Definitionsbereich hat 6 Elemente, der Wertebereich nur 5. Da jede injektive Abbildung jedes Element des Definitionsbereichs auf ein anderes Element des Wertebereichs abbildet, muss das Bild einer injektiven Abbildung hier mindestens 6 Elemente umfassen. Aber 5 < 6, also keine injektive Abbildung möglich.

3. Verwende Satz 2.3 aus der Vorlesung: (P ∨ Q) ∨ (¬P ∧ ¬Q) ⇔ (P ∨ Q) ∨ ¬(P ∨ Q), siehe f). Nach a) ist aber ein logischer Ausdruck vom Typ A ∨ ¬A allgemeingültig.

4. Nach Folgerung 10.34 besitzt jedes homogene LGS mindestens eine Lösung. Mehr Unbekannte als Gleichungen heißt, dass die zugehörige Matrix A eine m×n-Matrix mit m < n ist. Dann kann der Rang von A höchstens m sein, und es gibt n − rg(A) ≥ n − m > 0 frei wählbare Parameter. Mit Folgerung 10.32 bedeutet dies, dass es neben dem Nullvektor weitere Lösungen geben muss.

5. Die Potenzmenge der 5-elementigen Menge {1, 2, 3, 5, 6} hat nach Satz 7.6 genau 2^{5} = 32 Elemente.

6. Vgl. die Bemerkung nach Definition 4.8 zu Äquivalenzrelation und Halbordnung!

7. Ein inhomogenes Gleichungssystem Ax = b kann nicht den Nullvektor o als Lösung haben, da A · o = o ist und b ≠ o nach Vorausetzung. Aber Definition 11.4 a) fordert für einen Unterraum U ausdrücklich o ∈ U. Die Lösungsmenge eines homogenen LGS ist hingegen ein Unterraum, siehe Beispiel 11.5 a).

8. Nach Definition 7.1 sind zwei unendliche Mengen gleichmächtig, wenn es eine bijektive Abbildung zwischen ihnen gibt. Man kann sich nun überlegen, dass z. B. die Abbildung

φ: ℕ → ℕ \ \{100\} mit φ(n) = \{ \begin{matrix}n & falls n < 100 \\ n + 1 & falls n ≥ 100 \end{matrix}

eine bijektive Abbildung zwischen beiden Mengen ist.

9. Nach Definition 3.6 ist M ein Element von P(M).

10. Die Eulersche Funktion ist in Definition 9.18 gegeben durch φ(n) = #{k ∈ ℕ: 1 ≤ k ≤ n, ggT(k, n) = 1}. Nun ist 101 eine Primzahl, damit ist 101 teilerfremd zu allen Zahlen 1 ≤ k < 101, also φ(101) = 100.

11. Es ist ggT(9, 24) = 3 ≠ 1. Nach Satz 9.40 ist damit 9 nicht invertierbar modulo 24.

12. Der Rang einer Matrix A ist höchstens das Minimum aus Spalten- und Zeilenzahl. Das folgt direkt aus der Definition des Rangs (Definition 10.26).

13. Der Rang ist gerade die Anzahl verschiedener Einheitsvektoren. Die Treppenmatrix

T (A) = ( \begin{matrix}1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix} )

hat den Rang 2, es gibt aber insgesamt drei Einheitsvektoren (wobei allerdings die in der ersten und der zweiten Spalte identisch sind).

2. Aufgabe: Finde eine Formel für die Summe

S_{n} = ∑_{i=1}^{n} \frac{1}{i(i + 1)} (n ∈ IN)

und beweise die gefundene Formel durch vollständige Induktion.

Lösungsvorschlag: Um eine Formel zu finden, berechnen wir die ersten Summen explizit:

S_{1} = \frac{1}{1·(1+1)} = \frac{1}{2}
S_{2} = \frac{1}{2} + \frac{1}{2·(2+1)} = \frac{1}{2} + \frac{1}{6} = \frac{4}{6} = \frac{2}{3}
S_{3} = \frac{2}{3} + \frac{1}{3·(3+1)} = \frac{2}{3} + \frac{1}{12} = \frac{9}{12} = \frac{3}{4}
S_{4} = \frac{3}{4} + \frac{1}{4·(4+1)} = \frac{3}{4} + \frac{1}{20} = \frac{16}{20} = \frac{4}{5}

Die vermutete Formel ist somit

S_{n} = \frac{n}{n + 1} für alle n ∈ ℕ_{≥1}.

Beweis per Induktion nach n:

• Induktionsanfang (IA): Für n = 1 gilt: S_{1} = ∑_{i=1}^{1} \frac{1}{i(i+1)} = \frac{1}{1·2} = \frac{1}{2}. Da aber zudem \frac{1}{1+1} = \frac{1}{2} ist, ist die Formel richtig für n = 1.

• Induktionsvoraussetzung (IV): Gelte für ein vorgegebenes n ∈ ℕ_{≥1} die Formel S_{n} = \frac{n}{n+1}.

• Induktionsbehauptung (IB): Dann gilt auch S_{n+1} = \frac{n+1}{n+2}.

• Induktionsschritt: [Erläuterungen, die nicht gefordert sind: Die Definition von S_{n+1} ist der Ausgangspunkt. In der Summe identifizieren wir ein Subproblem gleichen Typs, also hier S_{n}. Dann kann die Induktionsvoraussetzung angewendet werden. Abschließend wird der Term so umgeformt, dass die behauptete Form zu erkennen ist.]

S_{n+1} = ∑_{i=1}^{n+1} \frac{1}{i(i + 1)} = ∑_{i=1}^{n} \frac{1}{i(i + 1)} + \frac{1}{(n + 1)(n + 1 + 1)}
= S_{n} + \frac{1}{(n + 1)(n + 2)} =^{IV} \frac{n}{n + 1} + \frac{1}{(n + 1)(n + 2)}
= \frac{n(n + 2)}{(n + 1)(n + 2)} + \frac{1}{(n + 1)(n + 2)} = \frac{n^{2} + 2n + 1}{(n + 1)(n + 2)}
= \frac{(n + 1)^{2}}{(n + 1)(n + 2)} = \frac{n + 1}{n + 2}.

3. Aufgabe: Sei A := ( \begin{matrix}1 & 0 \\ 2 & 3 \end{matrix} ) ∈ M_{2}(IR). Die Abbildung f : IR^{2} ⟶ IR^{2} sei definiert durch

f(v) := A · v (∀ v ∈ IR^{2}). Beweise, daß f bijektiv ist, und bestimme die Umkehrabbildung f^{−1}.

Lösungsvorschlag: Wir beweisen die Bijektivität von f, indem wir explizit die Umkehrabbildung g = f^{−1} bestimmen. Ein Kandidat ist die Abbildung

g: ℝ^{2} → ℝ^{2} mit g(w) = A^{−1}w,

sofern A invertierbar ist. Das ist aber der Fall, wie man mit Hilfe des Gaußalgorithmus feststellt. Zugleich bekommt man so das Inverse von A:

( \begin{matrix}1 & 0 & 1 & 0 \\ 2 & 3 & 0 & 1 \end{matrix} ) ⇝ ( \begin{matrix}1 & 0 & 1 & 0 \\ 0 & 3 & −2 & 1 \end{matrix} ) ⇝ ( \begin{matrix}1 & 0 & 1 & 0 \\ 0 & 1 & −\frac{2}{3} & \frac{1}{3} \end{matrix} ) ,

also ist A invertierbar mit A^{−1} = ( \begin{matrix}1 & 0 \\ −\frac{2}{3} & \frac{1}{3} \end{matrix} ). Es bleibt zu überprüfen, dass g Umkehrabbildung

zu f ist. Für alle v, w ∈ ℝ^{2} gilt aber:

(f ∘ g)(w) = f(g(w)) = A · (A^{−1} · w) = E_{2} · w = w und
(g ∘ f)(v) = g(f(v)) = A^{−1} · (A · v) = E_{2} · v = v,

d. h., dass g ∘ f = f ∘ g = id_{ℝ^{2}} ist.

4. Aufgabe: Es seien M, N, P beliebige nichtleere Mengen und f : M ⟶ N und g : N ⟶ P Abbildungen.

a) Beweise: Ist g ∘ f injektiv, so ist auch f injektiv.

b) Zeige durch ein konkretes Gegenbeispiel, daß in a) die Abbildung g nicht notwendig injektiv sein muß .

Lösungsvorschlag:

a) Wir übersetzen die Aufgabe in Voraussetzung und Behauptung: Voraussetzung: g ∘ f injektiv Behauptung: f ist injektiv Wir wählen einen indirekten Beweis, d. h., wir zeigen, dass aus der negierten Behauptung die negierte Voraussetzung folgt. Also: Annahme: f ist nicht injektiv Dann existieren zwei verschiedene Elemente x ≠ y in M, so dass f(x) = w = f(y) gilt mit w ∈ N. Setzt man nun x und y in die Abbildung g ∘ f ein, so erhält man:

(g ∘ f)(x) = g(f(x)) = g(w) = g(f(y)) = (g ∘ f)(y).

Also haben x und y dasselbe Bild unter der Abbildung g ∘ f. Da x ≠ y nach Annahme, ist g ∘ f nicht injektiv.

Insgesamt folgt also: Aus f nicht injektiv folgt g ∘ f nicht injektiv. Das ist aber gleichbedeutend mit: Aus g ∘ f injektiv folgt f injektiv.

b) Wir wählen M = {1, 2}, N = {1, 2, 4} und P = {1, 2}. Definiere

f: M → N durch f(x) = x und g: N → P durch g(x) = x rem 3.

Dann ist g(f(1)) = g(1) = 1 rem 3 = 1 und g(f(2)) = g(2) = 2 rem 3 = 2, also g ∘ f injektiv. Aber g(1) = 1 = 4 rem 3 = g(4) und 1 ≠ 4, also ist g nicht injektiv.

5. Aufgabe: 10 Studis treffen sich zur Klausur.

a) Auf wieviele Weisen können sie sich an die zehn nummerierten Einzelplätze setzen?

b) Jeder Studi bekommt entweder das Aufgabenblatt A oder das Aufgabenblatt B. Auf wieviele Arten kann diese Verteilung erfolgen?

c) Auf jedem Aufgabenblatt sind 8 Aufgaben zu finden. Davon muss ein Studi genau 5 bearbeiten. Auf wieviele Arten kann er diese Auswahl vornehmen?

d) Die Korrektoren verteilen insgesamt 20 Punkte auf die 5 bearbeiteten Aufgaben eines Studis. Jede Aufgabe kann dabei höchstens 20 Punkte bekommen. Wieviele Möglichkeiten gibt es, die Punkte zu verteilen?

Lösungsvorschlag: [ Tipp: Bei Kombinatorikaufgaben sollte man immer versuchen, den Typ der Aufgabe herauszufinden oder ein bekanntes Problem gleichen Typs wie z. B. das Lotto-Problem. Oft ist es hilfreich, genau zu erläutern, warum die Situation der vorliegenden Aufgabe gerade diesem Typ entspricht. Vgl. auch die Denk-Vorstellungen in Kapitel 8 der Vorlesung.]

a) Die 10 Tische sind nummeriert, also unterscheidbar. Man kann dann die 10 unterscheidbaren Studis nacheinander, d. h. geordnet, eine Tischnummer ziehen lassen. Da keine zwei Studis an einem Einzeltisch gemeinsam sitzen dürfen, liegt Ziehen ohne Wiederholung vor. Somit haben wir eine Permutation ohne Wiederholung, und Satz 8.6 liefert

P (10, 10) = 10 · 9 ⋯ (10 − 10 + 1) = 10! [ = 3628800 ].

b) Jeder der 10 unterscheidbaren Studis kann unabhängig von den anderen zwischen 2 Klausuren “wählen”. Unterscheidbare Studis sind also geordnet, die Klausurwahl ist mit Wiederholung (zwei Studis können nacheinander A wählen.) Damit ist die Aufgabe vom Typ 10-Permutation mit Wiederholung. Satz 8.8 liefert

P_{w}(2, 10) = 2^{10} [ = 1024 ].

c) Die Auswahl von 5 aus 8, ohne das eine Aufgabe doppelt vorkommt, erinnert an das Lottoproblem. Die Reihenfolge ist nicht relevant: welche Aufgabe wann ausgewählt wurde, spielt keine Rolle, da nachher nur 5 bearbeitete Aufgaben abzugeben sind. Es handelt sich also um eine 5-Kombination aus einer 8-elementigen Menge. Satz 8.11 liefert

C(8, 5) = ( \begin{matrix}8 \\ 5 \end{matrix} ) = \frac{8!}{5! · (8 − 5)!} = \frac{8 · 7 · 6}{3 · 2 · 1} = 8 · 7 = 56.

d) Man kann das Problem wie folgt modellieren: Für jede der 5 bearbeitete Aufgabe wird eine Kugel (beschriftet mit der Aufgabennummer) in eine Urne gelegt. Für jeden der 20 Punkte wird jetzt einmal in die Urne gegriffen, der Punkt der gezogenen Aufgabe gutgeschrieben, und zum Schluss die Kugel zurückgelegt. Damit ist die Reihenfolge nicht relevant, und wir ziehen mit Wiederholung. Das ist gerade das Modell, wie es unter “Denk-Vorstellungen: k-Kombination mit Wiederholung von n Elementen” unter (1) skizziert ist. Der zum Modell gehörige Satz 8.13 liefert

C_{w}(5, 20) = ( \begin{matrix}5 + 20 − 1 \\ 20 \end{matrix} ) = \frac{24!}{20! · (24 − 20)!} = \frac{24 · 23 · 22 · 21}{4 · 3 · 2 · 1} = 23·22·21 [ = 10626 ].

6. Aufgabe: Sei a ∈ IN eine natürliche Zahl und a = a_{k}a_{k−1} … a_{0} deren Dezimaldarstellung. Das heißt

a = ∑_{i=0}^{k} a_{i} · 10^{i},

und 0 ≤ a_{i} < 10. Beachte, daß 10 ≡ 1(mod 9) ist. Beweise die Teilbarkeitsregel durch 9, die besagt, daß a genau dann durch 9 teilbar ist, wenn die Quersumme Q(a) = ∑_{i=0}^{k} a_{i} durch 9 teilbar ist.

Lösungsvorschlag: Wir formulieren die Behauptung der Aufgabe um mit Hilfe von Restklassen modulo 9. Dann ist zu zeigen:

a ≡ 0 mod 9 genau dann, wenn Q(a) ≡ 0 mod 9.

Der Tipp aus der Aufgabenstellung (10 ≡ 1 mod 9) ergibt zusammen mit den Rechenregeln aus Satz 9.37 gerade, dass

10^{i} ≡ 1^{i} = 1 mod 9 für alle i ∈ ℕ_{≥0}

gilt. Eingesetzt in die Dezimaldarstellung von a ergibt sich dann

a = ∑_{0≤i<n} a_{i} · 10^{i} ≡ ∑_{0≤i<n} a_{i} · 1 = Q(a) mod 9.

Mit diesem Zusammenhang folgt die Behauptung sofort, denn

a ≡ 0 mod 9  ∧ a ≡ Q(a) mod 9 ⇒ Q(a) ≡ 0 mod 9
Q(a) ≡ 0 mod 9 ∧ a ≡ Q(a) mod 9 ⇒ a ≡ 0 mod 9,

und genau das war zu beweisen.

7. Aufgabe: Seien A = ( \begin{matrix}0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 2 \\ 1 & 0 & 1 & −1 & 1 \\ 0 & 0 & 0 & 1 & −1 \end{matrix} ) ∈ M_{4,5}(IR) und b = ( \begin{matrix}1 \\ 3 \\ 2 \\ 0 \end{matrix} ) ∈ IR^{4}

a) Zeige durch eine geeignete Rangbestimmung, daß das LGS A · x = b lösbar ist.

b) Bestimme die Lösungsmenge des zugehörigen homogenen LGS’s A · x = o_{4}.

c) Bestimme die Lösungsmenge von A · x = b. Mache die Probe!

Lösungsvorschlag: [Die einzelnen Schritte sind im folgenden nur deshalb mit Maple ausgeführt worden, um Tipp- und Rechenfehler zu vermeiden.]

> with(linalg):

Aufgabe 7: Die Aufgabenstellung enthält die Matrix A und den Vektor b als:

> A:=matrix([[0,1,0,1,1],[1,1,1,0,2],[1,0,1,-1,1],[0,0,0,1,-1]]);

A := [ \begin{matrix}0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 2 \\ 1 & 0 & 1 & −1 & 1 \\ 0 & 0 & 0 & 1 & −1 \end{matrix} ]

> b:=vector([1,3,2,0]);

b := [1, 3, 2, 0]

Wir wenden den Gaußalgorithmus auf die erweiterte Koeffizientenmatrix (A, b) an, bis wir eine obere Dreiecksmatrix erhalten:

> A0:=concat(A,b);

A0 := [ \begin{matrix}0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 2 & 3 \\ 1 & 0 & 1 & −1 & 1 & 2 \\ 0 & 0 & 0 & 1 & −1 & 0 \end{matrix} ]

> A1:=swaprow(A0,1,2);

A1 := [ \begin{matrix}1 & 1 & 1 & 0 & 2 & 3 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & −1 & 1 & 2 \\ 0 & 0 & 0 & 1 & −1 & 0 \end{matrix} ]

> A2:=addrow(A1,1,3,-1);

A2 := [ \begin{matrix}1 & 1 & 1 & 0 & 2 & 3 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & −1 & 0 & −1 & −1 & −1 \\ 0 & 0 & 0 & 1 & −1 & 0 \end{matrix} ]

   > A3:=addrow(A2,2,3,1);

A3 := [ \begin{matrix}1 & 1 & 1 & 0 & 2 & 3 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 \end{matrix} ]

   > A4:=swaprow(A3,3,4);

A4 := [ \begin{matrix}1 & 1 & 1 & 0 & 2 & 3 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ]

a) An dieser Stelle kann man bereits ablesen, dass der Rang von A und der Rang von (A, b) beide gleich 3 sind. Daher ist das Gleichungssystem lösbar. Wir wenden jetzt weiter den Gaußalgorithmus an, um oberhalb der Diagonalen Nullen zu erzeugen.

   > A5:=addrow(A4,3,2,-1);

A5 := [ \begin{matrix}1 & 1 & 1 & 0 & 2 & 3 \\ 0 & 1 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ]

   > A6:=addrow(A5,2,1,-1);

A6 := [ \begin{matrix}1 & 0 & 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ]

Damit ist die Treppenmatrix berechnet.

b) Die Lösung des homogenen Gleichungssystems läßt sich jetzt durch Rückwärtseinsetzen bestimmen. Aus A6 resultiert das folgende LGS:

\begin{aligned}x_{1} & & +x_{3} & & & = 0 \\ & x_{2} & & & +2x_{5} & = 0 \\ & & & x_{4} & −x_{5} & = 0 \end{aligned}

In der letzten Gleichung setzen wir x_{5} = s ∈ IR beliebig. Es folgt dann x_{4} = s. Die mittlere Gleichung ergibt x_{2} = −2x_{5} = −2s , und in der obersten Gleichung setzen wir x_{3} = r ∈ IR beliebig und erhalten x_{1} = −x_{3} = −r (Es können also zwei Unbekannte frei gewählt werden, was mit 5 − 3 = 2 in Einklang steht: die Anzahl der frei wählbaren Parameter ist gleich der Differenz aus der Anzahl der Unbekannten und dem Rang der Matrix). Die allgemeine Lösung w des LGS’s Ax = o_{4} ist damit von der Form

v = ( \begin{matrix}−r \\ −2s \\ r \\ s \\ s \end{matrix} )

wobei r und s beliebige reelle Zahlen sein können. Die Lösungsmenge ist damit

Lös(A, o_{4}) = \{( \begin{matrix}−r \\ −2s \\ r \\ s \\ s \end{matrix} ) | r, s ∈ IR \}

c) Die Lösung des inhomogenen Gleichungssystems läßt sich ebenfalls durch Rückwärtseinsetzen bestimmen. Aus A6 resultiert das folgende LGS:

\begin{aligned}x_{1} & & +x_{3} & & & = 2 \\ & x_{2} & & & +2x_{5} & = 1 \\ & & & x_{4} & −x_{5} & = 0 \end{aligned}

In der letzten Gleichung setzen wir x_{5} = s ∈ IR beliebig. Es folgt dann x_{4} = s. Die mittlere Gleichung ergibt x_{2} = 1 − 2x_{5} = 1 − 2s , und in der obersten Gleichung setzen wir x_{3} = r ∈ IR beliebig und erhalten x_{1} = 2 − x_{3} = 2 − r (Es können also zwei Unbekannte frei gewählt werden, was mit 5 − 3 = 2 in Einklang steht: die Anzahl der frei wählbaren Parameter ist gleich der Differenz aus der Anzahl der Unbekannten und dem Rang der Matrix). Die allgemeine Lösung v des LGS’s Ax = b ist damit von der Form

v = ( \begin{matrix}2 − r \\ 1 − 2s \\ r \\ s \\ s \end{matrix} )

wobei r und s beliebige reelle Zahlen sein können. Die Lösungsmenge ist damit

Lös(A, b) = \{( \begin{matrix}2 − r \\ 1 − 2s \\ r \\ s \\ s \end{matrix} ) | r, s ∈ IR \}

Probe: Rechne nach: A · ( \begin{matrix}2 − r \\ 1 − 2s \\ r \\ s \\ s \end{matrix} ) = b , wobei r und s beliebige reelle Zahlen sind. Bemerkung: Für r = s = 0 erhalten wir eine spezielle Lösung

v_{0} = ( \begin{matrix}2 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix} ) ∈ Lös(A, b) und es gilt v = v_{0} + w mit w = ( \begin{matrix}−r \\ −2s \\ r \\ s \\ s \end{matrix} ) ∈ Lös(A, o_{4})

d.h. Lös(A, b) = {v_{0} + w|wLös(A, o_{4})}.

8. Aufgabe: Sei A ∈ M_{n}(K). Beweise die Äquivalenz der folgenden Aussagen:

a) A ist invertierbar

b) Das LGS A · x = b besitzt für jedes b ∈ K^{n} genau eine Lösung.

Lösungsvorschlag: Wir beweisen beide Implikationen getrennt:

• Voraussetzung: Sei A invertierbar.

Behauptung: Dann hat A · x = b für jedes b ∈ K^{n} genau eine Lösung. Beweis: Wir zeigen zuerst, dass es mindestens eine Lösung gibt. Dann zeigen wir in einem zweiten Schritt, dass es höchstens eine Lösung des LGS gibt. Daraus folgt, dass es genau eine Lösung gibt.

– Da A invertierbar ist, ist x_{0} = A^{−1}b ein wohldefinierter Vektor im K^{n}. Durch Einsetzen sieht man, dass x_{0} eine Lösung des LGS ist, denn

A · x_{0} = A · (A^{−1} · b) = (A · A^{−1}) · b = E_{n} · b = b.

Es gibt also mindestens eine Lösung.

– Seien nun x, y ∈ K^{n} zwei Lösungen des LGS. Dann gilt A · x = b und A · y = b, somit

x = E_{n} · x = (A^{−1} · A) · x = A^{−1} · (A · x) = A^{−1} · b
= A^{−1} · (A · y) = (A^{−1} · A) · y = E_{n} · y = y.

Es gibt also höchstens eine Lösung.

• Voraussetzung: Für jedes b ∈ K^{n} hat A · x = b genau eine Lösung. Behauptung: Dann ist A invertierbar. Beweis: Das Gleichungssystem ist lösbar. Nach Satz 10.32 gibt es immer n − rg(A) freie Parameter. Da die Lösung nach Voraussetzung eindeutig ist, muss also n − rg(A) = 0, d. h. n = rg(A) sein. Nach Definition 10.26 ist dann aber auch der Rang der Treppenmatrix T (A) von A gerade n. Die einzige Treppenmatrix in M_{n}(K) vom Rang n ist aber die Einheitsmatrix E_{n}, also T (A) = E_{n}. Nach Satz 10.24 existiert eine invertierbare Matrix G ∈ M_{n}(K), für die gerade G · A = T (A) gilt. Wir fassen zusammen und erhalten: Es existiert eine invertierbare Matrix G in M_{n}(K) mit

(⋆) G · A = E_{n},

Bleibt noch zu zeigen: A · G = E_{n}.

Multiplikation der Gleichung (⋆) von links mit G^{−1} (G ist invertierbar!) liefert A = G^{−1} , woraus A · G = G^{−1} · G = E_{n} folgt.

Also ist A invertierbar.