8. Polynomringe

Das Umgehen mit Polynomen, d.h. mit Ausdrücken der Form

a_{0} + a_{1}x + a_{2}x^{2} + … + a_{n}x^{n}

ist aus der Schule vertraut, falls die Koeffizienten a_{0}, …, a_{n} ganze oder rationale oder reelle Zahlen sind. In diesen Fällen kann man das Polynom mit einer Abbildung

p̃: ℝ → ℝ, p̃(x) := ∑_{i=0}^{n} a_{i}x^{i}

identifizieren. Es gilt dann p̃(0) = a_{0}, (p̃)′(0) = a_{1}, (p̃)′′(0) = 2a_{2} und die k’te Ableitung von p̃ ausgewertet an der Stelle x = 0 ist gerade k! a_{k}, d.h. die Funktion p̃ bestimmt die a_{0}, …, a_{n} eindeutig. Wenn man nun Polynome mit Koeffizienten a_{i} aus einem beliebigen Körper K betrachten will, entsteht im Fall von endlichen Körpern folgende Schwierigkeit: es ”existieren“ unendlich viele verschiedene Polynome, z.B. die ”Monome“ 1, x, x^{2}, …, x^{n}, …,

aber nur endlich viele verschiedene Abbildung p̃ : K → K. Ein Polynom ∑_{i=0}^{n} a_{i}x^{i} mit

a_{i} ∈ K kann also nicht durch die zugehörige Abbildung p̃ : K → K, p̃(x) := ∑_{i=0}^{n} a_{i}x^{i}

eindeutig bestimmt sein. Diese Tatsache ruft die Frage hervor, was denn dann ein Polynom mit Koeffizienten a_{i} ∈ K wirklich ”ist“ (oder besser ”sein soll“), eine Frage, die wir eigentlich schon bei der Einführung des charakteristischen Polynoms (nach (5.24)) hätten stellen sollen. Das Ziel dieses Kapitels ist eine befriedigende Antwort auf diese Frage. Dann werden wir noch die Polynomdivision (mit Rest) kennenlernen und uns mit dem Zusammenhang zwischen Nullstellen von Polynomen und dem (multiplikativen) ”Abspalten“ von Linearfaktoren beschäftigen.

Zu einem beliebigen Körper K betrachten wir die Menge

K^{ℕ} := {f | f : ℕ → K},

d.h. ein Element f ∈ K^{ℕ} ist eine Folge f = (f_{0}, f_{1}, …, f_{n}, …) mit f_{n} ∈ K für alle n ∈ ℕ.

(8.1) Def.: Zu f, g ∈ K^{ℕ}, a ∈ K definieren wir

(i) f + g ∈ K^{ℕ} durch f + g := (f_{0} + g_{0}, f_{1} + g_{1}, …, f_{n} + g_{n}, …)

(ii) af ∈ K^{ℕ} durch af := (af_{0}, af_{1}, …, af_{n}, …)

(iii) f · g ∈ K^{ℕ} durch f · g := ((f · g)_{0}, (f · g)_{1}, …, (f · g)_{n}, …), wobei (f · g)_{0} := f_{0} · g_{0}, (f · g)_{1} := f_{0} · g_{1} + f_{1} · g_{0}, (f · g)_{2} := f_{0} · g_{2} + f_{1} · g_{1} + f_{2} · g_{0}

und (f · g)_{n} := ∑_{j=0}^{n} f_{j} · g_{n−j} = ∑_{\begin{matrix}(j,k)∈ℕ×ℕ \\ j+k=n \end{matrix}} f_{j} · g_{k}.

Bem.: 1) Die Ausdrücke in (iii) sind den Ausdrücken nachgebildet, die beim ”schulmäßigen“ Multiplizieren von Polynomen auftreten:

(a_{0}+a_{1}x+…+a_{n}x^{n})·(b_{0}+b_{1}x+…+b_{m}x^{m}) = a_{0}b_{0}+(a_{0}b_{1}+a_{1}b_{0})x+(a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0})x^{2}+… 2) Für a ∈ K, f ∈ K^{ℕ} gilt af = (a, 0, …, 0, …) · f.

(8.2) Fakt.

(i) (K^{ℕ}, +) ist ein ∞-dimensionaler K-Vektorraum mit dem Nullelement 0 = (0, …, 0, …) ∈ K^{ℕ}.

(ii) (K^{ℕ}, +, ·) ist ein kommutativer Ring mit 1 = (1, 0, …, 0, …) ∈ K^{ℕ}.

Bem.: Die Definition des ”kommutativen Rings mit 1“ unterscheidet sich von der des Körpers (vgl. (2.4)) nur dadurch, daß auf die Forderung der Existenz von multiplikativen Inversen verzichtet wird. (Man fordert üblicherweise auch \underline{nicht}, daß 1 ≠ 0 gilt, aber das ist für K^{ℕ} natürlich erfüllt).

Bez.: (K^{ℕ}, +, ·) heißt der Ring der formalen Potenzreihen über K, meist bezeichnet durch K[[x]].

Der Nachweis der in (8.2) behaupteten Eigenschaften ist leicht. Am längsten dauert der Nachweis der Assoziativität der Multiplikation, den man wie folgt durchführen kann: Seien f, g, h ∈ K^{ℕ} und n ∈ ℕ. Dann gilt:

\begin{aligned}((f · g) · h)_{n} & = & ∑_{j+k=n}(f · g)_{j}h_{k} = ∑_{j+k=n} ( ∑_{l+m=j} f_{l} · g_{m}) · h_{k} = ∑_{l+m+k=n} f_{l} · g_{m} · h_{k} \\ (f · (g · h))_{n} & = & ∑_{l+j=n} f_{l} · (g · h)_{j} = ∑_{l+j=n} f_{l} · ( ∑_{m+k=j} g_{m} · h_{k}) = ∑_{l+m+k=n} f_{l} · g_{m} · h_{k} \end{aligned}

(8.3) Fakt. Die Teilmenge

K[x] = {f ∈ K^{ℕ} | f_{n} ≠ 0 nur für endlich viele n ∈ ℕ}

ist abgeschlossen bezüglich + und · und enthält 1 = (1, 0, …, 0, …), und ist ein Unterring (mit 1) von (K^{ℕ}, +, ·).

Die Abgeschlossenheit bzgl. · folgt aus dem Beweis zu (8.5).

(8.4) Def.:

(i) (K[x], +, ·) heißt der Polynomring von K.

(ii) Ist f ∈ K[x] \ {0}, so heißt

grad f := max{i ∈ ℕ | f_{i} ≠ 0} ∈ ℕ

der Grad von f. Ist f = 0 ∈ K[x], so setzen wir grad f = −∞.

(8.5) Fakt. Für alle f, g ∈ K[x] gilt:

grad(f · g) = grad f + grad g.

Speziell folgt: f · g = 0 ⇒ f = 0 oder g = 0.

Zu letzterer Eigenschaft sagt man, (K[x], +, ·) sei ”nullteilerfrei“.

Bew.: Ist f = 0 oder g = 0, so f · g = 0, also

grad(f · g) = −∞ = grad f + grad g.

Ist grad f = m ∈ ℕ, grad g = n ∈ ℕ, so gilt f_{m} ≠ 0, g_{n} ≠ 0 und f_{i} = 0 für i > m, g_{j} = 0 für j > n. Daraus folgt

(f · g)_{m+n} = ∑_{\begin{matrix}(i,j)∈ℕ×ℕ \\ i+j=m+n \end{matrix}} f_{i}g_{j} = f_{m} · g_{n} ≠ 0

und (f · g)_{k} = 0 für k > m + n. Also

grad(f · g) = m + n = grad f + grad g.

Um zur üblichen Darstellung von Polynomen zu kommen, führen wir folgende \underline{Bezeichnung} ein:

x := (0, 1, 0, …, 0, …) ∈ K[x].

Außerdem definieren wir wie üblich x^{0} := (1, 0, …, 0, …) und rekursiv x^{n+1} := x · x^{n} für n ∈ ℕ.

In diesem Zugang zu den Polynomen ist also x keine ”Variable“, sondern ein festes Element des Rings K[x].

(8.6) Fakt. Die Menge {x^{n} | n ∈ ℕ} ist eine Basis des K-Vektorraums K[x]. Es gilt

x^{n} = (\underbrace{0, …, 0}_{n-mal}, 1, 0, …) ∈ K[x].

Bew.: Die erste Behauptung folgt aus der zweiten. Die zweite beweisen wir durch Induktion. Die Gleichung x^{0} = (1, 0, …, 0, …), die nach Definition von x^{0} gilt, ist der Induktionsanfang. Mit der Bezeichnung δ_{ij} := 0 für i ≠ j und δ_{ii} := 1 können wir x = (δ_{01}, δ_{11}, δ_{21}, …) und - nach Induktionsvoraussetzung - x^{n} = (δ_{0n}, δ_{1n}, …, δ_{nn}, …) schreiben. Also gilt für jedes i ∈ ℕ:

(x^{n+1})_{i} = (x · x^{n})_{i} = ∑_{j+k=i} δ_{j1}δ_{kn} = \{ \begin{matrix}1 falls i = n + 1 \\ 0 falls i ≠ n + 1. \end{matrix}

(8.7) Folgerung. Jedes Polynom f ∈ K[x] \ {0} besitzt genau eine Darstellung

f = f_{0} + f_{1}x + f_{2}x^{2} + … + f_{m}x^{m} mit f_{m} ≠ 0.

Es gilt dann grad f = m.

Bem.: Bezüglich dieser Darstellung gehen die in (8.1) definierten Operationen in die für Polynome ”üblichen“ über.

(8.8) Satz (Division mit Rest). Seien f ∈ K[x], g ∈ K[x], und es gelte grad f ≥ grad g ≥ 0. Dann existieren h, r ∈ K[x], so daß

f = gh + r

und

grad r < grad g (möglicherweise r = 0)

gelten.

Bew.: Durch Induktion nach n := grad f.

Induktionsanfang: Gilt grad f = 0, so auch grad g = 0, also f = f_{0}, g = g_{0}, und wir können

als h := \frac{g_{0}}{f_{0}} und r = 0 nehmen. Für den Induktionsschritt betrachten wir f = ∑_{i=0}^{n} f_{i}x^{i},

g = ∑_{j=0}^{m} g_{j}x^{j} mit 0 ≤ m ≤ n, f_{n} ≠ 0, g_{m} ≠ 0. Wir definieren

r_{1} := f − \frac{f_{n}}{g_{m}} x^{n−m} · g.

Dann gilt:

(∗) f = g · (\frac{f_{n}}{g_{m}} x^{n−m}) + r_{1} und grad r_{1} < n.

1. Fall: grad r_{1} < grad g. Dann erhalten wir die Behauptung, indem wir h := \frac{f_{n}}{g_{m}} x^{n−m} und r := r_{1} setzen.

2. Fall: grad r_{1} ≥ grad g. Wegen n > grad r_{1} ≥ grad g ≥ 0 ist auf r_{1} die Induktionsvoraussetzung anwendbar und wir erhalten h_{1}, r ∈ K[x], so daß r_{1} = gh_{1} + r und grad r < grad g gelten.

Dann folgt mit (∗):

f = g · (\frac{f_{n}}{g_{m}} x^{n−m} + h_{1}) + r.

Setzen wir h := \frac{f_{n}}{g_{m}} x^{n−m} + h_{1}, so erhalten wir wegen grad r < grad g die Behauptung.

Bem.: Der Beweis von (8.8) besteht in dem üblichen Rechenverfahren zur Polynomdivision, das in die Form eines Beweises gebracht wurde. Umgekehrt liefert der Beweis auch dieses Rechenverfahren, das man beherrschen muß.

Einem Polynom p = ∑_{i=0}^{n} a_{i}x^{i} ∈ K[x] ordnen wir die Abbildung

p̃: K → K, p̃(b) := ∑_{i=0}^{n} a_{i}b^{i} zu.

Dann gilt für alle p, q ∈ K[x]:

\begin{aligned}(p + q)^{∼} & = & p̃ + q̃ \\ (p · q)^{∼} & = & p̃ · q̃. \end{aligned}

Dabei bedeuten + und · auf der linken Seite die Addition und Multiplikation von Polynomen, auf der rechten Seite die Addition und Multiplikation von Abbildungen von K nach K! Anders ausgedrückt: Die Abbildung p → p̃ ist ein Ringhomomorphismus von K[x] in den Ring der Selbstabbildungen von K. Bez.: Ist p ∈ K[x], b ∈ K, so schreibt man für p̃(b) meist einfach p(b). \underline{Wichtige Bemerkung}: Allgemeiner kann man in p = ∑_{i=0}^{n} a_{i}x^{i} ∈ K[x] auch quadratische Matrizen A ∈ K^{m×m} für beliebiges m ∈ ℕ einsetzen:

p(A) := ∑_{i=0}^{n} a_{i}A^{i} ∈ K^{m×m}.

Es gilt wieder: \begin{aligned}(p + q)(A) & = & p(A) + g(A) \\ (p · q)(A) & = & p(A) · g(A). \end{aligned}

Beweis der zweiten Gleichung: Ist p = ∑_{i=0}^{m} a_{i}x^{i}, q = ∑_{j=0}^{n} b_{j}x^{j}, so gilt nach (8.1)(iii): p · q =

∑_{k=0}^{m+n} ( ∑_{i+j=k} a_{i}b_{j}) x^{k}, also (p · q)(A) = ∑_{k=0}^{m+n} ( ∑_{i+j=k} a_{i}b_{j}) A^{k}. Andererseits berechnen wir in

\begin{aligned}K^{m×m} : p(A) · q(A) & = & (∑_{i=0}^{m} a_{i}A^{i}) (∑_{j=0}^{n} b_{j}A^{j}) = ∑_{i=0}^{m} ∑_{j=0}^{n}(a_{i}A^{i})(b_{j}A^{j}) \\ & = & ∑_{k=0}^{m+n} ( ∑_{i+j=k} a_{i}b_{j}) A^{k}. \end{aligned}

(8.9) Def.: Ein a ∈ K heißt Nullstelle eines Polynoms p ∈ K[x], falls p(a) = 0 gilt. (8.10) Lemma. a ∈ K ist genau dann Nullstelle von p ∈ K[x] \ {0}, wenn ein q ∈ K[x] existiert, so daß p = (x − a)q gilt. Bew.: Offenbar folgt aus p = (x − a)q, daß

p̃(a) =^{!} (a − a)q̃(a) = 0 gilt.

Gilt p(a) = 0, so wenden wir (8.8) auf f := p und g := x − a an und erhalten q ∈ K[x], r ∈ K[x] mit grad r < grad g = 1, so daß

p = (x − a)q + r

gilt. Aus 0 = p(a) = (a − a)q(a) + r(a) folgt r(a) = 0 und daraus wegen grad r < 1: r = 0. Bez.: (x − a)^{0} := 1. (8.11) Def.: Sei p ∈ K[x] \ {0}, a ∈ K. Wir bezeichnen mit k(p, a) ∈ ℕ das Maximum aller k ∈ ℕ, für die ein q ∈ K[x] existiert, so daß p = (x − a)^{k}q gilt. Ist k(p, a) > 0, so gilt p(a) = 0 und k(p, a) heißt die Vielfachheit (oder Ordnung) der Nullstelle a von p.

Bem.: 1) k(p, a) = 0 ⇔ p(a) ≠ 0.

2) ∃q ∈ K[x]: p = (x − a)^{k(p,a)}q und q(a) ≠ 0.

3) k(p, a) ≤ grad p, denn aus 2) folgt: grad p = k(p, a) + grad q ≥ k(p, a).

(8.12) Satz. Seien p, f, g ∈ K[x], a ∈ K und es gelte p = f · g. Dann gilt

k(p, a) = k(f, a) + k(g, a).

Bew.:

(i) Ist f = (x − a)^{k_{1}}q_{1}, g = (x − a)^{k_{2}}q_{2}, so gilt

p = f · g = (x − a)^{k_{1}+k_{2}}q_{1}q_{2}.

Daraus folgt k(p, a) ≥ k(f, a) + k(g, a). (ii) Ist p = (x−a)^{k}q mit k = k(p, a) und f = (x−a)^{k_{1}}q_{1} mit q_{1}(a) ≠ 0 (⇒ k_{1} = k(f, a))

und g = (x − a)^{k_{2}}q_{2} mit q_{2}(a) ≠ 0 (⇒ k_{2} = k(g, a)), so folgt

p = (x − a)^{k}q = f · g = (x − a)^{k_{1}+k_{2}}q_{1}q_{2}.

Wegen (i) gilt k = k(p, a) ≥ k_{1} + k_{2}, also

(x − a)^{k_{1}+k_{2}} ((x − a)^{k−(k_{1}+k_{2})}q − q_{1}q_{2}) = 0.

Da K[x] nulleiterfrei ist, vgl. (8.5), und (x − a)^{k_{1}+k_{2}} ∈ K[x] \ {0} gilt, folgt (x − a)^{k−(k_{1}+k_{2})}q − q_{1}q_{2} = 0. Wenn k > k_{1} + k_{2} gelten würde, so folgte q_{1}(a)q_{2}(a) = 0, im Widerspruch zu q_{1}(a) ≠ 0, q_{2}(a) ≠ 0. Also gilt k = k(p, a) ≤ k_{1} + k_{2} = k(f, a) + k(g, a).

(8.13) Folgerung. Sind a_{1}, …, a_{s} verschiedene Nullstellen von p ∈ K[x] \ {0} mit den Vielfachheiten k_{1} = k(p, a_{1}), …, k_{s} = k(p, a_{s}), so existiert ein q ∈ K[x] mit:

p = (x − a_{1})^{k_{1}} · . . . · (x − a_{s})^{k_{s}}q.

Speziell gilt ∑_{i=1}^{s} k_{i} ≤ grad p.

Bew.: Induktion nach s. Der Induktionsanfang s = 1 ist gerade die Definition (8.11). Nach Induktionsvoraussetzung existiert \overline{q} ∈ K[x] mit

p = (x − a_{1})^{k_{1}} · . . . · (x − a_{s−1})^{k_{s−1}} \overline{q}.

Aus (8.12) folgt k_{s} = k(p, a_{s}) = k(\overline{q}, a_{s}). Also existiert q ∈ K[x] mit \overline{q} = (x − a)^{k_{s}}q. Daraus folgt die Behauptung

(8.14) Def.: Ein p ∈ K[x] \ {0} zerfällt über K (in Linearfaktoren), falls ein a ∈ K und a_{1}, …, a_{s} ∈ K und k_{1}, …, k_{s} ∈ ℕ existieren, so daß gilt

p = a(x − a_{1})^{k_{1}} · . . . · (x − a_{s})^{k_{s}} =: a ∏_{i=1}^{s}(x − a_{i})^{k_{i}}.

(8.15) Folgerung (aus (8.13)): p ∈ K[x]\{0} zerfällt genau dann über K, wenn verschiedene a_{1}, …, a_{s} ∈ K existieren, so daß

grad p = ∑_{i=1}^{s} k(p, a_{i})

gilt.

(8.16) Folgerung. Sind p, f, g ∈ K[x] \ {0}, gilt p = f · g und zerfällt p über K, so zerfallen auch f und g über K.

Bew.: Nach (8.15) existieren verschiedene a_{1}, …, a_{s} ∈ K mit grad p = ∑_{i=1}^{s} k(p, a_{i}).

Nach (8.12) gilt k(p, a_{i}) = k(f, a_{i}) + k(g, a_{i}) für 1 ≤ i ≤ s, also

grad f + grad g = grad p = ∑_{i=1}^{s} k(p, a_{i}) = \underbrace{∑_{i=1}^{s} k(f, a_{i})}_{≤ grad f} + \underbrace{∑_{i=1}^{s} k(g, a_{i})}_{≤ grad g} .

Daraus folgt ∑_{i=1}^{s} k(f, a_{i}) = grad f, ∑_{i=1}^{s} k(g, a_{i}) = grad g, so daß f und g nach (8.15) über K

zerfallen.

Zum Abschluß wollen wir uns überlegen, wie nun eigentlich das charakteristische Polynom eines Endomorphismus oder einer quadratischen Matrix definiert wird. Das ist nicht unproblematisch, da wir in der Formel P_{L}(x) = det(L−x id) das x nicht einfach als Körperelement interpretieren können. Der zu diesem Zeitpunkt beste Weg ist zu erkennen, daß man natürlich auch die Determinante einer Matrix A = (a_{ij})_{1≤i,j≤n} definieren kann, deren Einträge a_{ij} Elemente eines festen kommutativen Rings R mit 1 sind, nämlich durch die Leibnizformel det A = ∑_{σ∈S_{n}} sgn(σ)a_{1σ(1)} · . . . · a_{nσ(n)} ∈ R. Für zwei solche Matrizen A und

B ist das Matrizenprodukt AB definiert und es gilt det(AB) = det A det B. Das kann man mit einer recht unangenehmen Rechnung direkt nachprüfen. Besser wäre es, wie in Kap. 4 und 5 vorzugehen, aber dabei den Körper K durch einen kommutativen Ring R mit 1 zu ersetzen. Den K-Vektorräumen entsprächen dann ”freie R-Moduln“ und den Vektorraumhomomorphismen entsprächen ”R-Modulhomomorphismen“, die (im Fall endlich erzeugter R-Moduln) gerade durch Matrizen mit Einträgen aus R beschrieben werden (für Interessierte sei auf Kapitel 9 des Buchs Kowalsky/Michler: Lineare Algebra, de Gruyter 1995, verwiesen). Wir sehen hier ein schönes Beispiel dafür, wie man manchmal von der Mathematik zu allgemeineren Begriffen gezwungen wird.

Jedenfalls kann man dann für eine Matrix A = (a_{ij})_{1≤i,j≤n} ∈ K^{n×n} die Matrix A − xE_{n} als Matrix mit Einträgen im Ring R = K[x] betrachten, und so ist das charakteristische Polynom

P_{A} = det(A − xE_{n}) = ∑_{σ∈S_{n}} sgn(σ)(a_{1σ(1)} − xδ_{1σ(1)}) · . . . · (a_{nσ(n)} − xδ_{nσ(n)})

von A definiert. Ist B ∈ GL_{n}(K), so gilt

P_{B^{−1}AB} = det(B^{−1}AB − xE_{n}) = det(B^{−1}(A − xE_{n})B)
= det B^{−1}P_{A} det B = P_{A}.

Ist nun L Endomorphismus eines n-dimensionalen K-Vektorraums, so wählen wir eine geordnete Basis G von V, setzen A := Mat_{G}^{G}(L) und definieren das charakteristische Polynom P_{L} ∈ K[x] von L durch P_{L} := P_{A}. Aufgrund der vorangehenden Gleichung ist das unabhängig von der Wahl von G, vgl. (4.19).