Symmetrisches Polynom

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Mathematik heißt ein Polynom in mehreren Unbestimmten symmetrisch, wenn man die Unbestimmten untereinander vertauschen kann, ohne das Polynom zu verändern.

Betrachtet man beispielsweise die Polynome p=X+Y-1 und q=X+Y^2, so erhält man durch Vertauschen von X und Y die Polynome

\tilde p=Y+X-1 bzw. \tilde q=Y+X^2.

Da die Addition kommutativ ist, erhält man im Fall von p also dasselbe Polynom, d. h., p ist symmetrisch in X und Y, im Fall von q erhält man ein anderes Polynom, q ist nicht symmetrisch.

Formale Definition[Bearbeiten]

Es seien n>1 eine natürliche Zahl, A ein Ring. Dann heißt ein Polynom p\in A[X_1,\ldots, X_n] symmetrisch in X_1,\ldots,X_n, wenn

p(X_{\sigma(1)},\ldots,X_{\sigma(n)})=p(X_1,\ldots,X_n) für alle Permutationen \sigma\in S_n

gilt.

Äquivalente Beschreibungen sind:

  • Für alle k\ne m ist
p(X_1,\ldots,X_{k-1},X_k,X_{k+1}\ldots,X_{m-1},X_m,X_{m+1},\ldots,X_n)=p(X_1,\ldots,X_{k-1},X_m,X_{k+1},\ldots,X_{m-1},X_k,X_{m+1},\ldots,X_n),
das heißt, man kann zwei beliebige Unbestimmte gegeneinander austauschen.
  • Es sei
p=\sum_{e_1\geq0,\ldots,e_n\geq0} a_{e_1,\ldots,e_n}X_1^{e_1}\cdots X_n^{e_n}.
Dann ist p genau dann symmetrisch, wenn
a_{e_1,\ldots,e_n}=a_{e_{\sigma(1)},\ldots,e_{\sigma(n)}} für alle \sigma\in S_n
gilt. Anschaulich bedeutet das, dass der Koeffizient eines Monoms von p nur davon abhängt, welche Exponenten wie oft vorkommen, und nicht, bei welchen Unbestimmten.
(\sigma p)(X_1,\ldots,X_n)=p(X_{\sigma(1)},\ldots,X_{\sigma(n)})
auf dem Polynomring A[X_1,\ldots,X_n]. Ein Polynom ist genau dann symmetrisch, wenn es invariant unter dieser Operation ist, d. h., wenn
\sigma p = p für alle \sigma\in S_n
gilt. Eine mögliche Schreibweise für den Ring der symmetrischen Polynome ist deshalb
A[X_1,\ldots,X_n]^{S_n}.

Körper der symmetrischen Funktionen[Bearbeiten]

Wir ersetzen nun den Grundring A durch einen Grundkörper K. Der Körper der symmetrischen Funktionen L ist analog zu obiger Definition der Fixkörper unter S_n, also: L=K(X_1,\ldots,X_n)^{S_n}.
Die Körpererweiterung K(X_1,\ldots,X_n)/L ist galoissch mit Galoisgruppe S_n und hat damit Grad  n!

Beispiele[Bearbeiten]

  • Das Polynom X+Y ist symmetrisch in X und Y, jedoch nicht symmetrisch in X,Y,Z.
  • Aus jedem beliebigen Polynom P in den Variablen X_1,\ldots,X_n lässt sich ein symmetrisches Polynom bilden indem man die Bilder unter den Permutationen addiert, also:
\sum\limits_{\sigma\in S_n}\sigma(P)

Elementarsymmetrische Polynome[Bearbeiten]

Definition[Bearbeiten]

Es seien T,X_1,\ldots,X_n Unbestimmte. Die Koeffizienten von

(T+X_1)(T+X_2)\dotsm(T+X_n)=T^n+\sigma_1 T^{n-1}+\sigma_2 T^{n-2}+\dotsb+\sigma_n

als Polynom in T sind symmetrisch in X_1,\dotsc,X_n; sie heißen elementarsymmetrische Polynome. Sie sind explizit angebbar als

\sigma_1=X_1+\dotsb+X_n
\sigma_2=X_1X_2+\dotsb+X_1X_n+X_2X_3+\dotsb+X_2X_n+\dotsb+X_{n-1}X_n
\ldots
\sigma_k=\sum_{1\leq i_1<i_2<\dotsb<i_k\leq n}X_{i_1}\dotsm X_{i_k}
\ldots
\sigma_n=X_1\dotsm X_n

Dabei kann man \sigma_k auch schreiben als

\sigma_k = \sum_{ S \subseteq  \{ 1, \dotsc, n \}  \atop \# S=k} \ \prod_{i \in S} X_i \ .

Beispiele[Bearbeiten]

  • Die zwei elementarsymmetrischen Polynome in den Variablen X, Y sind
\sigma_1=X+Y\qquad sowie \sigma_2=X\cdot Y
  • In den drei Variablen X, Y, Z existieren die drei elementarsymmetrischen Polynome
\sigma_1=X+Y+Z\qquad\sigma_2=X\cdot Y+X\cdot Z+Y\cdot Z\qquad\sigma_3=X\cdot Y\cdot Z

Eigenschaften[Bearbeiten]

  • In einem elementarsymmetrischen Polynom haben die Monome einen einheitlichen Grad: es ist ein homogenes Polynom.
  • Nimmt man den Grad n der S_n als ersten Index hinzu, dann ist für n=2
\sigma_{2,1}(X_1,X_2) = X_1 + X_2
\sigma_{2,2}(X_1,X_2) = X_1 \cdot X_2
Für n>2 lassen sich die elementarsymmetrischen Polynome folgendermaßen rekursiv berechnen:
\sigma_{n,1}(X_1,\ldots,X_n) = \sigma_{n-1,1}(X_1,\ldots,X_{n-1}) + X_n
\sigma_{n,k}(X_1,\ldots,X_n) =  \sigma_{n-1,k}(X_1,\ldots,X_{n-1}) +  \sigma_{n-1,k-1}(X_1,\ldots,X_{n-1})\cdot X_n (k\in \{2,\dotsc,n-1\})
\sigma_{n,n}(X_1,\ldots,X_n) =  \sigma_{n-1,n-1}(X_1,\ldots,X_{n-1})\cdot X_n
[1]
  • Das elementarsymmetrische Polynom \sigma_{n,k} vom Symmetriegrad n\in \N und Polynomgrad k\in \{1,\dotsc,n\} enthält \binom{n}{k} Monome.
  • Hauptsatz der elementarsymmetrischen Polynome:
 A[X_1,\dotsc,X_n]^{S_n}=A[\sigma_1,\dotsc,\sigma_n]
In Worten: Jedes symmetrische Polynom lässt sich als Polynom in den elementarsymmetrischen Polynomen schreiben. Der Satz stammt von Joseph-Louis Lagrange, war aber schon Isaac Newton bekannt.
Genauer gilt sogar, dass diese Darstellung eindeutig ist, denn:
das heißt: Es gibt keine zwei verschiedene Polynome P_1,\, P_2 in den Variablen X_1,\dotsc,X_n, für die gilt: P_1(\sigma_1,\dotsc,\sigma_n)=P_2(\sigma_1,\dotsc,\sigma_n)
p(T)=T^n+a_1T^{n-1}+a_2T^{n-2}+\dotsb+a_n
ein Polynom mit Koeffizienten in A und x_1,\dotsc,x_n die (mit Vielfachheit gezählten) Nullstellen von p in einem algebraischen Abschluss des Quotientenkörpers von A. Dann gilt nach dem Wurzelsatz von Vieta:
a_1=-(x_1+\dotsb+x_n)
a_2=x_1x_2+x_1x_3+\dotsb+x_1x_n+x_2x_3+\dotsb+x_{n-1}x_n
\ldots
a_k=(-1)^k\cdot\sigma_k(x_1,\dotsc,x_n)
\ldots
a_n=(-1)^nx_1\dotsm x_n.

Beispiele[Bearbeiten]

  • X_1^2+\dotsb+X_n^2=\sigma_1^2-2\sigma_2
  • X_1^3+\dotsb+X_n^3=\sigma_1^3-3\sigma_1\sigma_2+3\sigma_3, allgemein sind die Potenzsummen mit den elementarsymmetrischen Polynomen durch die Newton-Identitäten verbunden.
  • Das Polynom
\Delta(X_1,\dotsc,X_n)=\prod_{i<j}(X_i-X_j)^2=(-1)^{n(n-1)/2} \prod_{i\ne j}(X_i-X_j)
ist symmetrisch in X_1,\dotsc,X_n, also kann man es als Polynom in den elementarsymmetrischen Polynomen schreiben. Ist nun
p(T)=T^n+a_1T^{n-1}+a_2T^{n-2}+\dotsb+a_n
ein Polynom mit Nullstellen x_1,\dotsc,x_n wie oben und setzt man diese in \Delta ein, so entsprechen die elementarsymmetrischen Ausdrücke bis auf die Vorzeichen den Koeffizienten a_i, d. h., \Delta(x_1,\dotsc,x_n) ist ein nur von n abhängendes Polynom in den Koeffizienten a_1,\dotsc,a_n. Bis auf Definitionsvarianten beim Vorzeichen ist dieses Polynom die Diskriminante von p.

Siehe auch[Bearbeiten]

Anmerkungen[Bearbeiten]

  1. Bei Zahlwerten (anstelle von Unbestimmten) gestaltet sich die Rechnung noch einfacher – statt mit 2^n Monomen bestehend aus Produkten mit bis zu n Faktoren hat man nur \binom{n}2 Multiplikationen.
    Es folgt ein Programm zur Berechnung der Koeffizienten A_k des Polynoms p(T) = T^n + \sum_{k=0}^{n-1} (-1)^{k+1} A_k \, T^{n-k-1} aus den Nullstellen X_k des Polynoms p(T) = \prod_{k=0}^{n-1} (T-X_k) :
     // Umwandlung von Nullstellen in Koeffizienten:
     double X[]; // bei Eingabe: n Zahlen für die Nullstellen X[0, ... ,n-1]
                 // bei Ausgabe: n Zahlen für die Koeffizienten
     for (k=0; k<n; ++k) {
       Y = X[k];
       X[k] = X[k-1]*Y;
       for (j=k-1; j>0; --j) {
         X[j] += X[j-1]*Y;
       }
       X[0] += Y;
     }