, 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,\ldots,x_n)$ in den Unbestimmten $x_1,\ldots,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

$$ \def\tr{\mathop{\rm tr}} \eqalignno{ s_1 &= x_1 + x_2 + \cdots + x_n,\cr s_2 &= x_1x_2 + x_1x_3 + \cdots + x_1x_n + \cdots + x_{n-1}x_n,\cr s_3 &= x_1x_2x_3 + x_1x_2x_4 + \cdots + x_{n-2}x_{n-1}x_n,\cr \vdots\: & \qquad\vdots\qquad\vdots\cr s_n &= x_1\ldots x_n.\cr } $$

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,\ldots,x_n)$ existiert genau ein Polynom $F(x_1,\ldots,x_n)$, sodaß $f(x_1,\ldots,x_n)=F(s_1,\ldots,s_n)$, $\forall x_1,\ldots,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,\ldots,x_n)$ sei bzgl. der Potenzen lexikographisch geordnet und es sei $q=ax_1^{k_1}\ldots x_n^{k_n}$ der lexikographisch letzte Term, $k_1\ge\cdots\ge k_n$. Betrachtet man

$$ a s_1^{k_1-k_2} s_2^{k_2-k_3} \ldots{\mskip 3mu} s_{n-1}^{k_{n-1}-k_n} s_n^{k_n}, $$

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

$$ a x_1^{k_1-k_2} (x_1x_2)^{k_2-k_3} \ldots (x_1\ldots x_{n-1})^{k_{n-1}-k_n} (x_1\ldots x_n)^{k_n} \tag{*} $$

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

$$ f_1(x_1,\ldots,x_n) := f(x_1,\ldots,x_n) - a s_1^{k_1-k_2} \ldots s_n^{k_n} $$

nur Terme, die lexikographisch vor $q$ kommen, man beachte $(*)$. $f_1(x_1,\ldots,x_n)$ ist symmetrisch und man wiederholt das Verfahren, welches irgendwann abbricht, da es nur endlich viele Terme der Form $b x_1^{\ell_1} \ldots x_n^{\ell_n}$ ($\ell_1\ge\cdots\ge\ell_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-2s_2$, oder $x_1^3+x_2^3=s_1^3-3s_1s_2$ zeigen; $s_1=x_1+x_2$, $s_2=x_1x_2$. Die Symmetrie von $f$ verlagert sich also in die Symmetrie der Basen der Polynome.

6. Definition: Es seien $f(x)=a_0x^m+\cdots+a_m$ und $g(x)=b_0x^n+\cdots+b_n$ zwei Polynome. Dann nennt man die Determinante

$$ \def\abc{\phantom{\matrix{\imath_1\cr \imath_1\cr \imath_1\cr}}} R = \left|\matrix{ a_0 & \ldots & a_m\cr & \ddots & \ddots & \ddots\cr && a_0 & \ldots & a_m\cr b_0 & \ldots & b_n\cr & \ddots & \ddots & \ddots\cr && b_0 & \ldots & b_n\cr }\right| \eqalign{ \left.\abc\right\} & \hbox{$n$ Zeilen}\cr \left.\abc\right\} & \hbox{$m$ Zeilen}\cr } $$

die Resultante von $f(x)$ und $g(x)$, für $m,n\ge1$, $a_0\ne0$, $b_0\ne0$.

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

$$ \eqalign{ a_0u^{m+n-1} + \cdots + a_mu^{n-1}\qquad &= 0\cr \qquad\ddots\qquad\ddots\qquad\ddots\quad & \phantom{=0}\kern-1pt\vdots\cr \qquad\qquad a_0u^m + \cdots + a_m &= 0\cr b_0u^{n+m-1} + \cdots + b_nu^m\qquad &= 0\cr \qquad\ddots\qquad\ddots\qquad\ddots\quad & \phantom{=0}\kern-1pt\vdots\cr \qquad\qquad b_0u^n + \cdots + b_n &= 0\cr } $$

Dieses homogene Gleichungssystem hat den nicht-trivialen Lösungsvektor

$$ \left(u^{n+m-1}, u^{n+m-2}, \ldots, u^2, u, 1\right)^\top \in \mathbb{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)=\mathop{\rm ggT}(f(x),g(x))$, wobei $\deg f(x)=m\ge1$, $\deg g(x)=n\ge1$. Dann gilt

$$ d(x)=\hbox{const}\iff f(x)g_1(x)+g(x)f_1(x)=0\quad\cases{ \deg f_1(x)\lt m,&$f_1(x)\ne0$,\cr \deg g_1(x)\lt n,&$g_1(x)\ne0$.\cr} $$

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,\ldots,m+n-1$ die $j$-te Spalte multipliziert mit $x^{m+n-j}$ zur letzten ($m$-ten) Spalte von $R$, welche zu

$$ \left(x^{n-1}f(x), \ldots, f(x), {\mskip 5mu} x^{m-1}g(x), \ldots, g(x)\right)^\top $$

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)\ldots(x-y_m)$ und $g(x)=b_0(x-z_1)\ldots(x-z_n)$, $m,n\ge1$, so hat man für die Resultante die drei Darstellungen

$$ R = a_0^n b_0^m \prod_{1\le k,\ell\le n} %\prod_{\scriptstyle{1\le k\le n}\atop\scriptstyle{1\le\ell\le n}} (y_k-z_\ell) = a_0^n \prod_{1\le k\le m} g(y_k) = (-1)^{mn} b_0^m \prod_{1\le\ell\le n} f(z_\ell). $$

11. Die Newton-Identitäten. Newton, Sir Isaac (1643--1727), Urbain Le Verrier (1811--1877). Zur Matrix $A\in\mathbb{C}^{n\times n}$ mit den Eigenwerten $\lambda_i$, sei $p_k=\sum\lambda_i^k=\tr A^k$ und das charakteristische Polynom sei $f(x)=x^n+c_1x^{n-1}+\cdots+c_n=(x-\lambda_1)\ldots(x-\lambda_n)$. Nach der Produktregel ist

$$ f'(x) = {f(x)\over x-\lambda_1} + \cdots + {f(x)\over x-\lambda_n}, $$

und durch Polynomdivision verifiziert man

$$ f(x):(x-\lambda) = x^{n-1} + (\lambda+c_1)x^{n-2} + (\lambda^2+c_1\lambda+c_2)x^{n-3} + \cdots + (\lambda^{n-1}+c_1\lambda^{n-2}+\cdots+c_{n-1}). $$

Summation liefert $f'(x)=nx^{n-1}+(p_1+nc_1)x^{n-2}+(p_2+c_1p_1+nc_2)x^{n-3} +\cdots+(p_{n-1}+c_1p_{n-2}+\cdots+nc_{n-1})$. Koeffizientenvergleich mit $f'(x)=nx^{n-1}+(n-2)x^{n-2}+\cdots+2c_{n-2}+c_{n-1}$ ergibt

$$ \eqalignno{ &p_1 + c_1 = 0\cr &p_2 + c_1p_1 + 2c_2 = 0\cr &\qquad\vdots\qquad\qquad\ddots\cr &p_{n-1} + c_1p_{n-2} + \cdots + c_{n-2}p_1 + (n-1)c_{n-1} = 0\cr } $$

und $\lambda_1^k f(\lambda_1) + \cdots + \lambda_n^k f(\lambda_n) = 0$ ergibt

$$ p_{n+k} + c_1p_{n-1+k} + \cdots + c_{n-1}p_{1+k} + nc_n = 0, \qquad k=0,1,2,\ldots $$