Fachbereich Mathematik Prof. Dr. J.H. Bruinier Martin Fuchssteiner Eric Hofmann Fredrik Strömberg

TECHNISCHE UNIVERSITÄT DARMSTADT

�

SS 2008 06.05.2008

Lineare Algebra II

5. Tutorium mit Lösungshinweisen

(T 21) Irreduzible Polynome

Sei 𝕂 ein Körper und sei P(𝕂) der Vektoraum der Polynome mit Koeffizenten aus 𝕂. Ein Polynom p ∈ P(𝕂) heißt irreduzibel, wenn es keine Polynome q, r ∈ P(K) vom Grad größer 0 gibt, mit der Eigenschaft, dass p = qr.

(a) Wie sehen irreduzible Polynome in P(ℂ) aus? Wie in P(ℝ)?

(b) Geben Sie ein Beispiel für ein irreduzibles Polynom in P(ℚ), dessen Grad größer als 2 ist.

Lösung:

(a) Da jedes Polynom über ℂ in Linearfaktoren zerfällt, sind die irreduziblen Polynome in P(ℂ) genau die linearen Polynome.

Die irreduziblen Polynome in P(ℝ) sind entweder linear oder quadratische Polynome der Form

Q(X) = aX^{2} + bX + c, mit b^{2} − 4ac < 0.

(b) Ein mögliches Beispiel ist etwa

X^{3} − 2.

Natürlich zerfällt dieses, wie jedes solche Beispiel, in P(ℝ),

X^{3} − 2 = (X − \sqrt[3]{2})(X^{2} + \sqrt[3]{2}X + (\sqrt[3]{2})^{2}).

(T 22) Euklidscher Algorithmus

In der Vorlesung wurde ein Verfahren zur Ermittlung des ggT zweier Zahlen behandelt, der sogenannte Euklidsche Algorithmus, den man kurz folgendermaßen beschreiben kann. Bestimmung von ggT(a, b):

• Schritt 0: Setze a_{1} = min{a, b}, a_{0} = max{a, b}.

• Schritt k, k = 1, 2, …: Führe eine Division mit Rest aus,

\begin{matrix}a_{k−1} = q_{k}a_{k} + r_{k}. \\ a_{k+1} := r_{k}. \end{matrix}

• Falls a_{k+1} = 0, so ist a_{k} = ggT(a, b) und man kann aufhören.

(a) Sei n die Zahl an Schritten, die der Algorithmus benötigt, um ggT(a_{0}, b_{0}) zu ermitteln. Betrachten Sie die Matrix M ∈ M_{2}(ℤ),

M = (\begin{matrix}0 & 1 \\ 1 & q_{1} \end{matrix}) (\begin{matrix}0 & 1 \\ 1 & q_{2} \end{matrix}) ⋯ (\begin{matrix}0 & 1 \\ 1 & q_{n} \end{matrix}) .

Zeigen Sie, dass M^{−1} ebenfalls nur ganzzahlige Einträge hat, und berechnen Sie

M^{−1} (\begin{matrix}a_{1} \\ a_{0} \end{matrix}) .

Welche Bedeutung haben die Einträge von M^{−1}?

(b) Finden Sie eine Folge f_{0}, f_{1}, … von ganzen Zahlen mit der Eigenschaft, dass die Berechnung von ggT(f_{m}, f_{m+1}) genau m Schritte benötigt (ohne Schritt 0). Hinweis: Fibonacci-Zahlen, vgl. letztes Semester, Aufgabe (A 37) in der 12.Übung.

(c) Zeigen Sie, dass es kein Paar (a, b) ganzer Zahlen gibt mit a < f_{m+1} und b < f_{m}, für welches m Schritte oder mehr benötigt werden.

Lösung:

(a) Jede der Matrizen ( \begin{matrix}0 & 1 \\ 1 & q_{k} \end{matrix} ), aus denen M zusammengetzt ist, hat Determinante gleich −1. Also ist det M = (−1)^{k}. Folglich ist

M^{−1} = (\begin{matrix}m_{11} & m_{12} \\ m_{21} & m_{22} \end{matrix})^{−1} = (−1)^{k} (\begin{matrix}m_{22} & −m_{12} \\ −m_{21} & m_{11} \end{matrix})

ebenfalls in M_{n}(ℤ). Mit den obigen Bezeichnungen gilt folgende Gleichung:

(\begin{matrix}0 & 1 \\ 1 & q_{k} \end{matrix}) (\begin{matrix}a_{k+1} \\ a_{k} \end{matrix}) = (\begin{matrix}a_{k} \\ a_{k−1} \end{matrix}) .

Also hat man

M^{−1} (\begin{matrix}a_{1} \\ a_{0} \end{matrix}) = (\begin{matrix}0 & 1 \\ 1 & q_{n} \end{matrix})^{−1} (\begin{matrix}0 & 1 \\ 1 & q_{n−1} \end{matrix})^{−1} ⋯ (\begin{matrix}0 & 1 \\ 1 & q_{1} \end{matrix})^{−1} (\begin{matrix}a_{1} \\ a_{0} \end{matrix})

= (\begin{matrix}0 & 1 \\ 1 & q_{n} \end{matrix})^{−1} (\begin{matrix}0 & 1 \\ 1 & q_{n−1} \end{matrix})^{−1} ⋯ (\begin{matrix}0 & 1 \\ 1 & q_{2} \end{matrix})^{−1} (\begin{matrix}a_{2} \\ a_{1} \end{matrix}) = ⋯ = (\begin{matrix}0 \\ ggT(a_{0}, a_{1}) \end{matrix}) .

Sei M^{−1} = ( \begin{matrix}k & l \\ m & n \end{matrix}). Dann sind m, n die Koeffizenten, um ggT(a_{0}, a_{1}) als ganzzahlige Linearkombination von a_{0}, a_{1} darzustellen. Für k und l gilt hingegen ka_{0} = kgV(a_{0}, a_{1}) = −la_{1}.

(b) Idee: Man geht den Euklidschen Algorithmus rückwärts durch und betrachtet ihn als Rekursionsvorschrift. Im letzten, mten Schritt ist immer a_{m+1} = 0. Also setzt man f_{0} = 0. Man überlegt weiter, dass der Algorithmus am längsten läuft, wenn a_{0}, a_{1} teilerfremd sind und alle Reste möglichst groß sind, also a_{k} = ggT(a_{0}, a_{1}) = 1 und q_{k} = 1 für alle k.

Behauptung: Die rekursiv definierte Folge

f_{0} = 0, f_{1} = 1, f_{m+1} = f_{m} + f_{m−1},

hat die gewünschte Eigenschaft. Induktionsbeweis. Verankerung: Die Berechnung von ggT(f_{1}, f_{2}) läuft so ab:

a_{1} = f_{1} = 1, a_{2} = f_{2} = 1, Schritt 1: a_{2} = f_{2} − f_{1} = 0.

Induktionsschritt: Bei der Berechnung des ggT von (a_{0}, a_{1}) = (f_{m+1}, f_{m}) erhält man q_{1} = 1 und a_{2} = f_{m−1}, da

f_{m+1} > f_{m} > f_{m−1} = f_{m+1} − f_{m}.

Dazu benötigt man einen Schritt. Per Induktionsvoraussetzung sind nun noch m−1 Schritte nötig, um den ggT zu berechnen.

(c) Annahme: Es gibt ein solches Paar (a, b). Ohne Beschränkung der Allgemeinheit nehmen wir an, dass a ≥ b und dass a, b teilerfremd sind (sonst bräuchte man weniger Schritte). Es ist also a_{m} = ggT(a, b) = 1 = f_{1} und a_{m+1} = 0 = f_{0}. Induktiv ergibt sich hieraus a_{m+1−k} ≥ f_{k}, für alle k = 0, …, m + 1, denn

a_{m+1−k} = a_{m+1−(k−2)} + q_{m+1−(k−1)}a_{m+1−(k−1)} ≥ f_{k−2} + f_{k−1} = f_{k}.

(Beachte: Die q_{l} ≥ 1, l = 1, …, m.) Insbesondere sind also a = a_{0} ≥ f_{m+1} und b = a_{1} ≥ f_{m}.Widerspruch!

(T 23)

Sei P_{m} der Vektorraum der Polynome vom Grad ≤ m über dem Körper 𝕂 = ℝ, ℂ. Weiterhin sei D ∈ End P definiert durch die Ableitung, also

Df = f′.

Zeigen Sie, dass D nilpotent ist und bestimmen Sie eine zyklische Basis für D. Geben auch eine Basis an, in der D Jordan-Normalform hat.

Lösung:

Dass D nilpotent ist, ergibt sich daraus, dass Dc = 0 für jede Konstante c ∈ 𝕂 und sich der Grad eines nicht-konstanten Polynoms beim Ableiten jeweils um 1 reduziert. D.h. für ein Polynom f vom Grad k ist D^{k}f konstant. Also ist D^{m+1} auf P_{m} die 0-Abbildung.

Bestimmung einer zyklischen Basis: D hat den einzigen Eigenwert 0. Jedes konstante Polynom ist somit Eigenvektor. Wie wählen e_{0} = 1 als ersten Basisvektor.

Ein Vektor e_{1} ∈ P_{4} mit De_{1} = 1 ist offenbar durch e_{1} = X gegeben.

Induktiv erhält man nun weitere Vektoren einer zyklischen Basis e_{k}, k = 0, 1, 2, …, m:

e_{k} = \frac{1}{k!}X^{k}, da De_{k} = \frac{k}{k!}X^{k−1} = \frac{1}{(k − 1)!}X^{k−1} = e_{k−1} und D^{k}e_{k} = e_{0}.

Da D nilpotent ist, ist die angegeben zyklische Basis auch schon eine Jordan-Basis.

(T 24)

Im Folgenden bezeichnet K einen Körper, K = ℝ oder ℂ.

(a) Betrachten Sie einen Jordanblock der Größe 2 × 2, zu einem Eigenwert λ ∈ 𝕂, also

eine Matrix

J(λ) = (\begin{matrix}λ & 1 \\ 0 & λ \end{matrix}) .

Finden Sie eine Formel für J^{m}(λ), m ≥ 0.

(b) Betrachten Sie die Matrix

A = (\begin{matrix}−1 & 0 & 1 \\ 1 & −1 & 2 \\ 0 & 0 & 1 \end{matrix}) .

Bestimmen Sie die Eigenwerte von A und finden Sie Transformationsmatrizen S und S^{−1}, so dass S^{−1}AS Jordan Normalform hat. (Hinweis: Benötigt wird hierzu eine zyklische Basis für jeden (verallgemeinerten) Eigenraum von A. )

(c) Berechnen Sie die Matrix A^{2008}.

Lösung:

(a)Wie man schnell sieht, etwa indem man für einige m J(λ)^{m} berechnet,

J(λ)^{0} = (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) , J(λ)^{1} = (\begin{matrix}λ & 1 \\ 0 & λ \end{matrix}) , J(λ)^{2} = (\begin{matrix}λ^{2} & 2λ \\ 0 & λ^{2} \end{matrix}) , J(λ)^{3} = (\begin{matrix}λ^{3} & 3λ^{2} \\ 0 & λ^{3} \end{matrix})

lautet der gesuchte Ausruck

J(λ)^{m} = (\begin{matrix}λ^{m} & mλ^{m−1} \\ 0 & λ^{m} \end{matrix}) .

Dies beweist man einfach durch Induktion nach m.

Induktionsanfang: siehe oben,

Induktionssschritt:

J(λ)^{m+1} = J(λ)^{m}J(λ) = (\begin{matrix}λ^{m} & mλ^{m−1} \\ 0 & λ^{m} \end{matrix}) (\begin{matrix}λ & 1 \\ 0 & λ \end{matrix}) = (\begin{matrix}λ^{m+1} & mλ^{m} + 1λ^{m} \\ 0 & λ^{m+1} \end{matrix}) .

(b) Bestimmung der Eigenwerte:

det (λE − A) = |\begin{matrix}λ + 1 & 0 & 1 \\ 1 & λ + 1 & 2 \\ 0 & 0 & λ − 1 \end{matrix}| = (λ + 1)^{2}(λ − 1).

Die Eigenwerte von A sind +1 und −1, letzterer mit algebraischer Vielfachheit 2.

Zum Eigenwert −1: Die Matrix

B =: A + E = (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 2 \\ 0 & 0 & 2 \end{matrix})

hat Rang 2. Somit ist die geometrische Vielfachheit des Eigenwerts −1 gleich 1. Wir bestimmen nun eine zyklische (Orthogonal-)Basis des verallgemeinerten Eigenraums V_{−1}^{2}(A).

Bestimmung eines Eigenvektors: Der Kern der linearen Abbildung B wird von dem Eigenvektor (0, 1, 0)^{t} aufgespannt.

Bestimmmung eines Hauptvektors: Gesucht ist ein Lösungsvektor x = (x_{1}, x_{2}, x_{3})^{t} für die Gleichung

Bx = (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 2 \\ 0 & 0 & 2 \end{matrix}) (\begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = (\begin{matrix}0 \\ 1 \\ 0 \end{matrix}) .

Offenbar ist x = (1, 0, 0)^{t} eine solche Lösung, welche außerdem senkrecht auf (0, 1, 0)^{t} steht.

Somit sind (0, 1, 0)^{t} und (1, 0, 0)^{t} eine zyklische Basis von V_{−1}^{2}(A).

Zum Eigenwert +1: Die geometrische Vielfachheit ist 1, einen Eigenvektor v erhält man aus der Gleichung

0 = (A − E)v = (\begin{matrix}−2 & 0 & 1 \\ 1 & −2 & 2 \\ 0 & 0 & 0 \end{matrix}) (\begin{matrix}v_{1} \\ v_{2} \\ v_{3} \end{matrix}) .

Für die Komponenten hat man v_{3} = 2v_{1} und v_{2} = 5/2v_{1}, also ist (1, \frac{5}{2}, 2)^{t} ein Eigenvektor (, welcher den Eigenraum V_{1}(A) aufspannt.

Eine Jordan-Basis für A setzt sich nun aus den Basen von V_{−1}^{2}(A) und V_{1}(A) zusammen, ist also zum Beispiel durch die Vektoren

(\begin{matrix}0 \\ 1 \\ 0 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \end{matrix}) , (1 \frac{5}{2} 2)

gegeben. Damit erhält man die Transformationsmatrizen

S = (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & \frac{5}{2} \\ 0 & 0 & 2 \end{matrix}) und S^{−1} = (\begin{matrix}0 & 1 & −\frac{5}{4} \\ 1 & 0 & −\frac{1}{2} \\ 0 & 0 & \frac{1}{2} \end{matrix} )

und rechnet nach:

\begin{aligned}J =: S^{−1}AS & = (\begin{matrix}0 & 1 & −\frac{5}{4} \\ 1 & 0 & −\frac{1}{2} \\ 0 & 0 & \frac{1}{2} \end{matrix} ) (\begin{matrix}−1 & 0 & 1 \\ 1 & −1 & 2 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & \frac{5}{2} \\ 0 & 0 & 2 \end{matrix}) \\ & = (\begin{matrix}1 & −1 & \frac{3}{4} \\ −1 & 0 & \frac{1}{2} \\ 0 & 0 & \frac{1}{2} \end{matrix} ) (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & \frac{5}{2} \\ 0 & 0 & 2 \end{matrix}) = (\begin{matrix}−1 & 1 & 0 \\ 0 & −1 & 0 \\ 0 & 0 & 1 \end{matrix}) \end{aligned}

(c) Es gilt A^{2008} = S J^{2008}S^{−1}. Da die in der Jordanzerlegung auftretenden Teilräume zueinander orthogonal sind, ist offenbar

J^{2008} = (\begin{matrix}( \begin{matrix}−1 & 1 \\ 0 & −1 \end{matrix} )2008 & ( \begin{matrix}0 \\ 0 \end{matrix} ) \\ (0, 0) & 1^{2008} \end{matrix}) =^{(a)} (\begin{matrix}(−1)^{2008} & 2008 (−1)^{2007} & 0 \\ 0 & (−1)^{2008} & 0 \\ 0 & 0 & 1 \end{matrix}) = (\begin{matrix}1 & −2008 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) .

Man berechnet nun noch

A^{2008} = SJ^{2008}S^{−1} = (\begin{matrix}0 & 1 & 1 \\ 1 & 0 & \frac{5}{2} \\ 0 & 0 & 2 \end{matrix}) (\begin{matrix}1 & −2008 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) (\begin{matrix}0 & 1 & −\frac{3}{4} \\ 1 & 0 & −\frac{1}{2} \\ 0 & 0 & \frac{1}{2} \end{matrix} )

= (\begin{matrix}0 & 1 & 1 \\ 1 & −2008 & \frac{5}{2} \\ 0 & 0 & 2 \end{matrix}) (\begin{matrix}0 & 1 & −\frac{3}{4} \\ 1 & 0 & −\frac{1}{2} \\ 0 & 0 & \frac{1}{2} \end{matrix} ) = (\begin{matrix}1 & 0 & −\frac{3}{4} \\ −2008 & 1 & \frac{1}{2} \\ 0 & 0 & 1 \end{matrix}) .

(T 25) Polynome von Jordan-Blöcken Sei p(X) ein Polynom und J ein Jordan-Block der Größe n × n,

J = (\begin{matrix}λ & 1 & 0 & … & 0 \\ 0 & λ & 1 & … & 0 \\ ⋮ & ... & ⋮ \\ ⋮ & ... & ⋮ \\ . . . . . . . . . & 0 & λ \end{matrix}) .

Zeigen Sie, dass

p(J) = (\begin{matrix}p(λ) & \frac{p′(λ)}{1!} & \frac{p′′(λ)}{2!} & … & \frac{p^{(n−1)}(λ)}{(n−1)!} \\ 0 & p(λ) & \frac{p′(λ)}{1!} & … & \frac{p^{(n−2)}(λ)}{(n−2)!} \\ ⋮ & ... & ⋮ \\ ⋮ & ... & ⋮ \\ . . . . . . . . . . . . . . . . & 0 & p(λ) \end{matrix}) ,

wobei wie üblich p^{(k)} die k-te Ableitung von p bezeichnet.

Lösung:

Am Besten beweist man die Aussage zunächst für das Polynom p(X) = X^{m}, für m ≥ 0. Bekanntlich gilt

p^{(k)}(X) = \begin{cases}m(m − 1) ⋯ (m − k + 1)X^{m−k} & für m ≥ k \\ 0 & sonst \end{cases} .

Also ist

\frac{1}{k!}p^{(k)}(X) = \frac{m!}{k!(m − k)!}X^{m−k} = \binom{m}{k}X^{m−k},

Für p(X) = X^{m} lautet die Behauptung also:

(J^{m})_{i,j} = \begin{cases}\binom{m}{j−i}λ^{m−(j−i)} & für j ≥ i und m ≥ (j − i) \\ 0 & für j < i oder m < (j − i). \end{cases}

Wir führen den Beweis per Induktion. Induktionsverankerung: Auf der rechten Seite der Gleichung sind für m = 0 nur die Einträge auf der Diagonalen ≠ 0, nämlich λ^{0} = 1. Und in der Tat steht links J^{0} = E.

Induktionsschritt m ⟶ m + 1: Der Eintrag in der i-ten Spalte und j-ten Zeile von J^{m+1} ist 0 für j < i (Produkt oberer Dreiecksmatrizen!). Für j > i ist eine Fallunterscheidung nötig: Falls m ≥ j − i gilt

(J^{m+1})_{i,j} = (J^{m}J)_{i,j}

= 0 + ⋯ + 0 + \binom{m}{j − i}λ^{m−(j−i)} · 1 + \binom{m}{j − (i + 1)}λ^{m−(j−(i+1))} · λ + 0 + ⋯

= [\binom{m}{j − i − 1} + \binom{m}{j − i}] λ^{m+1−(j−i)} = \binom{m + 1}{j − i}λ^{m+1−(j−i)}.

Falls hingegen m < j − i, so muss man m = j − i − 1 gesondert betrachten. Hier hat man

(J^{m}J)_{i,j} = 0 · 1 + \underbrace{\binom{m}{0}}_{=1} λ^{0} · λ = λ = \binom{m + 1}{0}λ^{1} = \binom{m + 1}{(m + 1) − (j − i)}λ^{m+1−(j−i)}.

Sonst, also für m < j − i − 1, verschwinden alle Summanden, die zu (J^{m+1})_{i,j} beitragen, also (J^{m+1})_{i,j} = 0. Zusammen ergibt sich die Behauptung für p(X) = X^{m}.

Nun ergibt sich der allgemeine Fall für ein Polynom p(X), vom Grad M

p(X) = ∑_{m=0}^{M} c_{m}X^{m}

einfach aus der Linearität der Ableitung und der Vektorraumsstruktur der n × n Matrizen:

p(J) = ∑_{m=0}^{M} c_{m}J^{m} = (\begin{matrix}∑_{m=0}^{M} c_{m}λ^{m} & ∑_{m=0}^{M} c_{m} \frac{d}{dλ}λ^{m} & ∑_{m=0}^{M} c_{m} \frac{d^{2}}{(dλ)^{2}} \frac{λ^{m}}{2!} & … & … \\ ⋮ & ... & ⋮ \\ ⋮ & ... & ⋮ \\ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . & 0 & ∑_{m=0}^{M} c_{m}λ^{m} \end{matrix}) .