31st January 2024, 5 min read

Elementarsymmetrische Polynome

Original post is here eklausmeier.goip.de/blog/2024/01-31-elementarsymmetrische-polynome.

1. Definition: Ein Polynom $f (x_{1}, \dots, x_{n})$ in den Unbestimmten $x_{1}, \dots, x_{n}$ heißt symmetrisch, falls das Polynom invariant bleibt unter jeder beliebigen zyklischen Vertauschung der Unbestimmten.

2. Beispiel: $f (x_{1}, x_{2}) = x_{1}^{2} + x_{2}^{2}$ oder $f (x_{1}, x_{2}) = x_{1}^{3} + x_{2}^{3}$ sind symmetrische Polynome, da Vertauschungen der Rollen von $x_{1}$ gegen $x_{2}$ nichts ändert.

3. Besonders wichtig sind die sogenannten elementarsymmetrischen Polynome

\begin{aligned} s_{1} & = x_{1} + x_{2} + \dots + x_{n}, \\ s_{2} & = x_{1} x_{2} + x_{1} x_{3} + \dots + x_{1} x_{n} + \dots + x_{n - 1} x_{n}, \\ s_{3} & = x_{1} x_{2} x_{3} + x_{1} x_{2} x_{4} + \dots + x_{n - 2} x_{n - 1} x_{n}, \\ ⋮ & ⋮ ⋮ \\ s_{n} & = x_{1} \dots x_{n} . \end{aligned}

Das Polynom $s_{i}$ heißt $i$ -tes elementarsymmetrisches Polynom. Die $s_{i}$ üben gewisse Basisfunktionen im Raum der symmetrischen Polynome aus.

4. Satz: (Hauptsatz über elementarsymmetrische Polynome) Zu jedem symmetrischen $n$ -stelligen Polynom $f (x_{1}, \dots, x_{n})$ existiert genau ein Polynom $F (x_{1}, \dots, x_{n})$ , sodaß $f (x_{1}, \dots, x_{n}) = F (s_{1}, \dots, s_{n})$ , $\forall x_{1}, \dots, x_{n}$ .

Beweis: Siehe László Rédei (1967), Algebra I, László Rédei (15 November 1900 – 21 November 1980). Existenz: $f (x_{1}, \dots, x_{n})$ sei bzgl. der Potenzen lexikographisch geordnet und es sei $q = a x_{1}^{k_{1}} \dots x_{n}^{k_{n}}$ der lexikographisch letzte Term, $k_{1} \geq \dots \geq k_{n}$ . Betrachtet man

a s_{1}^{k_{1} - k_{2}} s_{2}^{k_{2} - k_{3}} \dots s_{n - 1}^{k_{n - 1} - k_{n}} s_{n}^{k_{n}},

so erkennt man, daß dieser Ausdruck als führenden Koeffizienten den Term

\begin{matrix} (*) & a x_{1}^{k_{1} - k_{2}} (x_{1} x_{2})^{k_{2} - k_{3}} \dots (x_{1} \dots x_{n - 1})^{k_{n - 1} - k_{n}} (x_{1} \dots x_{n})^{k_{n}} \end{matrix}

besitzt, welcher offensichtlich gleich $q$ ist. Also enthält

f_{1} (x_{1}, \dots, x_{n}) := f (x_{1}, \dots, x_{n}) - a s_{1}^{k_{1} - k_{2}} \dots s_{n}^{k_{n}}

nur Terme, die lexikographisch vor $q$ kommen, man beachte $(*)$ . $f_{1} (x_{1}, \dots, x_{n})$ ist symmetrisch und man wiederholt das Verfahren, welches irgendwann abbricht, da es nur endlich viele Terme der Form $b x_{1}^{ℓ_{1}} \dots x_{n}^{ℓ_{n}}$ ( $ℓ_{1} \geq \dots \geq ℓ_{n}$ ) gibt.

Eindeutigkeit: Ist $f = F_{1} = F_{2}$ , so ist $F_{1} - F_{2}$ identisch gleich Null, also das Nullpolynom. ☐

5. Bemerkung: $f$ ist symmetrisch, $F$ ist i.d.R. nicht symmetrisch, wie $x_{1}^{2} + x - 2^{2} = s_{1}^{2} - 2 s_{2}$ , oder $x_{1}^{3} + x_{2}^{3} = s_{1}^{3} - 3 s_{1} s_{2}$ zeigen; $s_{1} = x_{1} + x_{2}$ , $s_{2} = x_{1} x_{2}$ . Die Symmetrie von $f$ verlagert sich also in die Symmetrie der Basen der Polynome.

6. Definition: Es seien $f (x) = a_{0} x^{m} + \dots + a_{m}$ und $g (x) = b_{0} x^{n} + \dots + b_{n}$ zwei Polynome. Dann nennt man die Determinante

R = | \begin{matrix} a_{0} & \dots & a_{m} \\ ⋱ & ⋱ & ⋱ \\ a_{0} & \dots & a_{m} \\ b_{0} & \dots & b_{n} \\ ⋱ & ⋱ & ⋱ \\ b_{0} & \dots & b_{n} \end{matrix} | \begin{aligned} } & n Zeilen \\ } & m Zeilen \end{aligned}

die Resultante von $f (x)$ und $g (x)$ , für $m, n \geq 1$ , $a_{0} \neq 0$ , $b_{0} \neq 0$ .

7. Es sei $u$ eine ^{gemeinsame Nullstelle}, also $f (u) = 0$ und $g (u) = 0$ . Dann gilt

\begin{aligned} a_{0} u^{m + n - 1} + \dots + a_{m} u^{n - 1} & = 0 \\ ⋱ ⋱ ⋱ & ⋮ \\ a_{0} u^{m} + \dots + a_{m} & = 0 \\ b_{0} u^{n + m - 1} + \dots + b_{n} u^{m} & = 0 \\ ⋱ ⋱ ⋱ & ⋮ \\ b_{0} u^{n} + \dots + b_{n} & = 0 \end{aligned}

Dieses homogene Gleichungssystem hat den nicht-trivialen Lösungsvektor

{(u^{n + m - 1}, u^{n + m - 2}, \dots, u^{2}, u, 1)}^{⊤} \in C^{n + m}

Daher: falls eine gemeinsame Nullstelle $u$ vorliegt, so ist $R = 0$ . Es gilt sogar: wenn $R = 0$ , dann liegt eine gemeinsame Nullstelle vor.

8. Lemma: Es sei $d (x) = ggT (f (x), g (x))$ , wobei $\deg f (x) = m \geq 1$ , $\deg g (x) = n \geq 1$ . Dann gilt

d (x) = const ⟺ f (x) g_{1} (x) + g (x) f_{1} (x) = 0 {\begin{cases} \deg f_{1} (x) < m, & f_{1} (x) \neq 0, \\ \deg g_{1} (x) < n, & g_{1} (x) \neq 0 . \end{cases}

Beweis: “ $\Rightarrow$ ”: Offensichtlich ist $f (x) = d (x) f_{1} (x)$ und $g (x) = - d (x) g_{1} (x)$ mit zwei Polynomen $f_{1} (x)$ und $g_{1} (x)$ mit allen oben gewünschten Eigenschaften.

“ $\Leftarrow$ ”: siehe Rédei, L., Rédei (1967). ☐

9. Satz: Für die Resultante $R$ gilt: $f (x) F (x) + g (x) G (x) = R$ , wobei $\deg F (x) < n$ , $\deg G (x) < m$ .

Beweis: Addiere für $j = 1, 2, \dots, m + n - 1$ die $j$ -te Spalte multipliziert mit $x^{m + n - j}$ zur letzten ( $m$ -ten) Spalte von $R$ , welche zu

{(x^{n - 1} f (x), \dots, f (x), x^{m - 1} g (x), \dots, g (x))}^{⊤}

wird. Entwickeln nach der letzten Spalte und dann Ausklammern von $f (x)$ bzw. $g (x)$ , liefert die angegebene Darstellung. ☐

Mit Hilfe des Lemmas folgt, daß $R$ genau dann verschwindet, falls $f (x)$ und $g (x)$ einen gemeinsamen Faktor besitzen.

10. Satz: Ist $f (x) = a_{0} (x - y_{1}) \dots (x - y_{m})$ und $g (x) = b_{0} (x - z_{1}) \dots (x - z_{n})$ , $m, n \geq 1$ , so hat man für die Resultante die drei Darstellungen

R = a_{0}^{n} b_{0}^{m} \prod_{1 \leq k, ℓ \leq n} (y_{k} - z_{ℓ}) = a_{0}^{n} \prod_{1 \leq k \leq m} g (y_{k}) = (- 1)^{m n} b_{0}^{m} \prod_{1 \leq ℓ \leq n} f (z_{ℓ}) .

11. Die Newton-Identitäten. Newton, Sir Isaac (1643--1727), Urbain Le Verrier (1811--1877). Zur Matrix $A \in C^{n \times n}$ mit den Eigenwerten $λ_{i}$ , sei $p_{k} = \sum λ_{i}^{k} = tr A^{k}$ und das charakteristische Polynom sei $f (x) = x^{n} + c_{1} x^{n - 1} + \dots + c_{n} = (x - λ_{1}) \dots (x - λ_{n})$ . Nach der Produktregel ist

f^{'} (x) = \frac{f (x)}{x - λ_{1}} + \dots + \frac{f (x)}{x - λ_{n}},

und durch Polynomdivision verifiziert man

f (x) : (x - λ) = x^{n - 1} + (λ + c_{1}) x^{n - 2} + (λ^{2} + c_{1} λ + c_{2}) x^{n - 3} + \dots + (λ^{n - 1} + c_{1} λ^{n - 2} + \dots + c_{n - 1}) .

Summation liefert $f^{'} (x) = n x^{n - 1} + (p_{1} + n c_{1}) x^{n - 2} + (p_{2} + c_{1} p_{1} + n c_{2}) x^{n - 3} + \dots + (p_{n - 1} + c_{1} p_{n - 2} + \dots + n c_{n - 1})$ . Koeffizientenvergleich mit $f^{'} (x) = n x^{n - 1} + (n - 2) x^{n - 2} + \dots + 2 c_{n - 2} + c_{n - 1}$ ergibt

\begin{aligned} p_{1} + c_{1} = 0 \\ p_{2} + c_{1} p_{1} + 2 c_{2} = 0 \\ ⋮ ⋱ \\ p_{n - 1} + c_{1} p_{n - 2} + \dots + c_{n - 2} p_{1} + (n - 1) c_{n - 1} = 0 \end{aligned}

und $λ_{1}^{k} f (λ_{1}) + \dots + λ_{n}^{k} f (λ_{n}) = 0$ ergibt

p_{n + k} + c_{1} p_{n - 1 + k} + \dots + c_{n - 1} p_{1 + k} + n c_{n} = 0, k = 0, 1, 2, \dots