M. Künzer, J. Marhenke Lineare Algebra für Informatiker, WS 03/04

Lösung 9

Aufgabe 36.

(1) Für s ≠ 0 ist \{x ∈ R^{3} | Ax = b\} = (\begin{matrix}1−s \\ s^{−1} \\ 0 \end{matrix}) + ⟨(\begin{matrix}−1 \\ −1 \\ 1 \end{matrix})⟩. Für s = 0 ist \{x ∈ R^{3} | Ax = b\} = ∅.

(2) Für s ∉ \{0, 1\} ist \{x ∈ C^{4} | Ax = b\} = (\begin{matrix}0 \\ (s−1)^{−1} \\ 0 \\ 1 \end{matrix} ) + ⟨(\begin{matrix}−i \\ −(s−1)^{−1} \\ 1 \\ 0 \end{matrix} )⟩.

Für s = 0 ist \{x ∈ C^{4} | Ax = b\} = (\begin{matrix}0 \\ −1 \\ 0 \\ 0 \end{matrix}) + ⟨(\begin{matrix}0 \\ 0 \\ 0 \\ 1 \end{matrix}) , (\begin{matrix}−i \\ 1 \\ 1 \\ 0 \end{matrix})⟩. Für s = 1 erhält man \{x ∈ C^{4} | Ax = b\} = (\begin{matrix}−i \\ 0 \\ 1 \\ 1 \end{matrix}) + ⟨(\begin{matrix}0 \\ 1 \\ 0 \\ 0 \end{matrix})⟩.

(3) Für s ≠ 0 ist \{x ∈ K^{n} | Ax = b\} = (\begin{matrix}0 \\ 0 \\ β \\ 1 \end{matrix} ) + ⟨(\begin{matrix}β \\ 1 \\ 0 \\ 0 \end{matrix} )⟩. Für s = 0 ist \{x ∈ K^{n} | Ax = b\} = ⟨(\begin{matrix}β \\ 1 \\ 0 \\ 0 \end{matrix} ) , (\begin{matrix}0 \\ 0 \\ β \\ 1 \end{matrix} )⟩.

Aufgabe 37. Wir verwenden im folgenden A(φ)_{\underline{z},\underline{z}} = A(1_{V})_{\underline{z},\underline{y}}A(φ)_{\underline{y},\underline{y}}A(1_{V})_{\underline{y},\underline{z}}.

(1) Es ist A(1_{V})_{\underline{y},\underline{z}} = (\begin{matrix}2 & i \\ −i & 1 \end{matrix}) und A(1_{V})_{\underline{z},\underline{y}} ( = A(1_{V})_{\underline{y},\underline{z}}^{−1} ) = (\begin{matrix}1 & −i \\ i & 2 \end{matrix}). Folglich erhält man A(φ)_{\underline{z},\underline{z}} = (\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix}).

(2) Es ist A(1_{V})_{\underline{z},\underline{y}} = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{matrix}) und A(1_{V})_{\underline{y},\underline{z}} ( = A(1_{V})_{\underline{z},\underline{y}}^{−1} ) = (\begin{matrix}1 & −1 & 1 \\ 0 & 1 & −2 \\ 0 & 0 & 1 \end{matrix}). Folglich ist A(φ)_{\underline{z},\underline{z}} = (\begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 2 \end{matrix}).

Aufgabe 38.

(1) Jede Matrix läßt sich durch Multiplikation mit einem Element aus GL_{3}(F_{2}) auf Zeilenstufenform bringen. Damit liegt in jeder Äquivalenzklasse wenigstens eine Matrix in Zeilenstufenform.

Es gibt in F_{2}^{3×3} insgesamt 16 Matrizen in Zeilenstufenform. Wir behaupten, daß es 16 Äquivalenzklassen gibt und haben dazu noch zu zeigen, daß zwei äquivalente Matrizen in Zeilenstufenform bereits übereinstimmen.

Die Dimension des von den Spalten der Matrix erzeugten Unterraums von F_{2}^{3} ist invariant unter Multiplikation von links mit einem Element aus GL_{3}(F_{2}). Somit haben äquivalente Matrizen in Zeilenstufenform auch dieselbe Anzahl ausgewählter Spalten. Für festes l ∈ [0, 3] bleibt uns also zu zeigen, daß zwei äquivalente Matrizen in Zeilenstufenform mit l ausgewählten Spalten bereits gleich sind.

l = 0 Es gibt nur eine Matrix in Zeilenstufenform, die 0 ausgewählte Spalten hat, nämlich (\begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}).

l = 1 Betrachten wir zwei Matrizen A = (a_{i,j})_{i,j} und Ã = (ã_{i,j})_{i,j} in Zeilenstufenform mit je einer ausgewählten Spalte, in Position k_{1} bzw. k̃_{1}. Wegen A ∼ Ã haben wir {i ∈ [1, 3] | a_{∗,i} = 0} = {i ∈ [1, 3] | ã_{∗,i} = 0}, und mithin k_{1} = k̃_{1}.

Falls k_{1} = 1, so folgt aus G (\begin{matrix}1 & a_{1,2} & a_{1,3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) = (\begin{matrix}1 & ã_{1,2} & ã_{1,3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) mit G ∈ GL_{3}(F_{2}), daß G = (\begin{matrix}1 & ∗ & ∗ \\ 0 & ∗ & ∗ \\ 0 & ∗ & ∗ \end{matrix}), und also a_{1,2} = ã_{1,2} und

a_{1,3} = ã_{1,3}.

Falls k_{1} = 2, so folgt aus G (\begin{matrix}0 & 1 & a_{1,3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) = (\begin{matrix}0 & 1 & ã_{1,3} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) mit G ∈ GL_{3}(F_{2}), daß G = (\begin{matrix}1 & ∗ & ∗ \\ 0 & ∗ & ∗ \\ 0 & ∗ & ∗ \end{matrix}), und also a_{1,3} = ã_{1,3}.

Falls k_{1} = 3, so ist von vorneherein A = Ã.

l = 2 Betrachten wir zwei Matrizen A = (a_{i,j})_{i,j} und Ã = (ã_{i,j})_{i,j} in Zeilenstufenform mit je zwei ausgewählten Spalten, in den Positionen k_{1} < k_{2} bzw. k̃_{1} < k̃_{2}. Wegen A ∼ Ã haben wir

{(i, j) ∈ [1, 3] × [1, 3] | (a_{∗,i}, a_{∗,j}) ist linear unabhängig} = {(i, j) ∈ [1, 3] × [1, 3] | (ã_{∗,i}, ã_{∗,j}) ist linear unabhängig} ,

und mithin k_{1} = k̃_{1} und k_{2} = k̃_{2}.

Falls k_{1} = 1 und k_{2} = 2, so folgt aus G (\begin{matrix}1 & 0 & a_{1,3} \\ 0 & 1 & a_{2,3} \\ 0 & 0 & 0 \end{matrix} ) = (\begin{matrix}1 & 0 & ã_{1,3} \\ 0 & 1 & ã_{2,3} \\ 0 & 0 & 0 \end{matrix} ) mit G ∈ GL_{3}(F_{2}), daß G = (\begin{matrix}1 & 0 & ∗ \\ 0 & 1 & ∗ \\ 0 & 0 & ∗ \end{matrix}), und also a_{1,3} = ã_{1,3}

und a_{2,3} = ã_{2,3}.

Falls k_{1} = 1 und k_{2} = 3, so folgt aus G (\begin{matrix}1 & a_{1,2} & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) = (\begin{matrix}1 & ã_{1,2} & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) mit G ∈ GL_{3}(F_{2}), daß G = (\begin{matrix}1 & 0 & ∗ \\ 0 & 1 & ∗ \\ 0 & 0 & ∗ \end{matrix}), und also a_{1,2} = ã_{1,2}.

Falls k_{1} = 2 und k_{2} = 3, so ist von vorneherein A = Ã.

l = 3 Es gibt nur eine Matrix in Zeilenstufenform, die 3 ausgewählte Spalten hat, nämlich (\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}).

(2) Zunächst läßt sich jede Matrix durch Linksmultiplikation mit Elementen von GL_{4}(F_{2}) in Zeilenstufenform bringen. Sodann läßt sie sich durch Rechtsmultiplikation mit Elementen von GL_{4}(F_{2}) in die Form diag(1, …, 1, 0 …, 0) bringen. In anderen Worten, jede Äquivalenzklasse enthält wenigstens eine Matrix dieser Diagonalform. Da weder Links- noch Rechtsmultiplikation mit Elementen von GL_{4}(F_{2}) an der Dimension des von den Spalten der Matrix erzeugten Untervektorraums von F_{2}^{4} etwas ändern, sind zwei verschiedene Matrizen dieser Form nicht äquivalent, d.h. jede Äquivalenzklasse enthält auch höchstens eine Matrix dieser Diagonalgestalt. Damit gibt es genau 5 Äquivalenzklassen, repräsentiert durch diese Diagonalmatrizen.

(3) Eine direkte Rechnung zeigt, daß es die 6 Äquivalenzklassen \{(\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix})\}, \{(\begin{matrix}0 & 0 \\ 0 & 0 \end{matrix})\}, \{(\begin{matrix}1 & 0 \\ 0 & 0 \end{matrix}) , (\begin{matrix}0 & 0 \\ 0 & 1 \end{matrix}) , (\begin{matrix}0 & 1 \\ 0 & 1 \end{matrix}) , (\begin{matrix}1 & 1 \\ 0 & 0 \end{matrix}) , (\begin{matrix}0 & 0 \\ 1 & 1 \end{matrix}) , (\begin{matrix}1 & 0 \\ 1 & 0 \end{matrix})\},

\{(\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix}) , (\begin{matrix}0 & 0 \\ 1 & 0 \end{matrix}) , (\begin{matrix}1 & 1 \\ 1 & 1 \end{matrix})\}, \{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) , (\begin{matrix}1 & 0 \\ 1 & 1 \end{matrix}) , (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix})\} und \{(\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}) , (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix})\} gibt.

Aufgabe 39.

(1) Es genügt, einen Algorithmus anzugeben, der unter Zuhilfenahme beidseitiger Multiplikation von Matrizen der Form E_{k,l}(η) mit η ∈ Z, der Form π(σ), mit σ ∈ S_{m} resp. σ ∈ S_{n}, oder der Form diag(±1, …, ±1) die Matrix A auf die Blockgestalt (\begin{matrix}d & 0 \\ 0 & A′ \end{matrix} ) bringt, derart, daß A′ ∈ Z^{(m−1)×(n−1)} ist, und derart, daß d jeden Eintrag von A′ teilt. Denn dann kann mit der Matrix A′ ebenso verfahren werden, usf.

Hierzu verfahren wir wie folgt.

0. Falls A = 0, dann fertig. Falls A ≠ 0, dann weiter zu 1.

1. Bringe durch Multiplikation mit geeigneten Permutationsmatrizen von links und von rechts einen betragskleinsten Eintrag ungleich 0 an die Position (1, 1) der Matrix, d.h. nach links oben. Multipliziere die erste Zeile so, daß dieser Eintrag > 0 wird. Dann weiter zu 2.

2. Falls das Element an Position (1, 1) alle übrigen Einträge der ersten Spalte und der ersten Zeile teilt, so säubere durch Zeilen- und Spaltenumformungen, also durch Multiplikation entsprechender Elementarmatrizen von links und von rechts, die erste Spalte und die erste Zeile. Dann weiter zu 3. Falls das Element an Position (1, 1) einen Eintrag in der ersten Spalte nicht teilt, so addiere zu seiner Zeile ein geeignetes Vielfaches der ersten Zeile so, daß an seiner Stelle ein Eintrag ≠ 0 kleineren Betrages entsteht als an Position (1, 1). Dann zurück zu 1. Falls das Element an Position (1, 1) einen Eintrag in der ersten Zeile nicht teilt, so addiere zu seiner Spalte ein geeignetes Vielfaches der ersten Spalte so, daß an seiner Stelle ein Eintrag ≠ 0 kleineren Betrages entsteht als an Position (1, 1). Dann zurück zu 1.

3. Nun hat man die Matrix auf die Form (\begin{matrix}d & 0 \\ 0 & A′ \end{matrix} ) gebracht, mit d ∈ Z und A′ ∈ Z^{(m−1)×(n−1)}.

Falls d jeden Eintrag von A′ teilt, dann fertig. Falls d einen Eintrag von A′ nicht teilt, so addiere seine Zeile auf die erste, und addiere ein geeignetes Vielfaches der ersten Spalte auf seine Spalte derart, daß ein betragskleinerer Eintrag ≠ 0 als d entsteht. Zurück zu 1.

Der Algorithmus terminiert, da bei jedem Durchlaufen von 1. der Betrag des Eintrags an Position (1, 1) echt verkleinert wird.

(2) Es genügt, einen Algorithmus anzugeben, der unter Zuhilfenahme beidseitiger Multiplikation von Matrizen der Form E_{k,l}(η) mit η ∈ K[X], der Form π(σ), mit σ ∈ S_{m} resp. σ ∈ S_{n}, oder der Form diag(λ_{1}, …, λ_{m}) resp. diag(λ_{1}, …, λ_{n}) mit λ_{i} ∈ K ∖ \{0\} die Matrix A auf die Blockgestalt (\begin{matrix}d & 0 \\ 0 & A′ \end{matrix} ) bringt, derart, daß A′ ∈ K[X]^{(m−1)×(n−1)} ist, und derart, daß d jeden Eintrag von A′ teilt. Denn dann kann mit der Matrix A′ ebenso verfahren werden, usf.

Hierzu verfahren wir wie folgt.

0. Falls A = 0, dann fertig. Falls A ≠ 0, dann weiter zu 1.

1. Bringe durch Multiplikation mit geeigneten Permutationsmatrizen von links und von rechts einen Eintrag ungleich 0 kleinsten Grades an die Position (1, 1) der Matrix, d.h. nach links oben. Multipliziere die erste Zeile so, daß dieser Eintrag ein normiertes Polynom wird. Dann weiter zu 2.

2. Falls das Element an Position (1, 1) alle übrigen Einträge der ersten Spalte und der ersten Zeile teilt, so säubere durch Zeilen- und Spaltenumformungen, also durch Multiplikation entsprechender Elementarmatrizen von links und von rechts, die erste Spalte und die erste Zeile. Dann weiter zu 3. Falls das Element an Position (1, 1) einen Eintrag in der ersten Spalte nicht teilt, so addiere zu seiner Zeile ein geeignetes Vielfaches der ersten Zeile so, daß an seiner Stelle ein Eintrag ≠ 0 kleineren Grades entsteht als an Position (1, 1). Dann zurück zu 1. Falls das Element an Position (1, 1) einen Eintrag in der ersten Zeile nicht teilt, so addiere zu seiner Spalte ein geeignetes Vielfaches der ersten Spalte so, daß an seiner Stelle ein Eintrag ≠ 0 kleineren Grades entsteht als an Position (1, 1). Dann zurück zu 1.

3. Nun hat man die Matrix auf die Form (\begin{matrix}d & 0 \\ 0 & A′ \end{matrix} ) gebracht, mit d ∈ K[X] und A′ ∈ K[X]^{(m−1)×(n−1)}.

Falls d jeden Eintrag von A′ teilt, dann fertig. Falls d einen Eintrag von A′ nicht teilt, so addiere seine Zeile auf die erste von links, und addiere ein geeignetes Vielfaches der ersten Spalte auf seine Spalte derart, daß ein Eintrag ≠ 0 kleineren Grades als d entsteht. Zurück zu 1.

Der Algorithmus terminiert, da bei jedem Durchlaufen von 1. der Grad des Eintrags an Position (1, 1) echt verkleinert wird.

(3) Wir formen (\begin{matrix}2 & 2 & 4 \\ 2 & 2 & 4 \end{matrix}) ⇝ (\begin{matrix}2 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) um, also k = 1 und d_{1} = 2. Ferner wird z.B.

(\begin{matrix}−8 & 12 & −8 \\ 6 & 2 & 4 \\ 10 & −10 & 8 \end{matrix}) ⇝ (\begin{matrix}2 & 6 & 4 \\ 12 & −8 & −8 \\ −10 & 10 & 8 \end{matrix}) ⇝ (\begin{matrix}2 & 0 & 0 \\ 0 & −44 & −32 \\ 0 & 40 & 28 \end{matrix}) ⇝ (\begin{matrix}2 & 0 & 0 \\ 0 & 28 & 40 \\ 0 & −32 & −44 \end{matrix}) ⇝ (\begin{matrix}2 & 0 & 0 \\ 0 & 28 & 40 \\ 0 & −4 & −4 \end{matrix}) ⇝ (\begin{matrix}2 & 0 & 0 \\ 0 & 4 & 4 \\ 0 & 28 & 40 \end{matrix}) ⇝ (\begin{matrix}2 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 12 \end{matrix}) ,

also k = 3 sowie d_{1} = 2, d_{2} = 4 und d_{3} = 12. Schließlich wird z.B. (\begin{matrix}X & 1 \\ 0 & X \end{matrix} ) ⇝ (\begin{matrix}1 & X \\ X & 0 \end{matrix} ) ⇝ (\begin{matrix}1 & 0 \\ 0 & −X^{2} \end{matrix} ) ⇝ (\begin{matrix}1 & 0 \\ 0 & X^{2} \end{matrix} ) , also k = 2

sowie d_{1} = 1 und d_{2} = X^{2}.