Las identidades de Newton

Relaciones entre sumas de potencias y funciones simétricas elementales

En matemáticas , las identidades de Newton , también conocidas como fórmulas de Girard-Newton , dan relaciones entre dos tipos de polinomios simétricos , a saber, entre sumas de potencias y polinomios simétricos elementales . Evaluadas en las raíces de un polinomio mónico P en una variable, permiten expresar las sumas de las k -ésimas potencias de todas las raíces de P (contadas con su multiplicidad) en términos de los coeficientes de P , sin encontrar realmente esas raíces. Estas identidades fueron encontradas por Isaac Newton alrededor de 1666, aparentemente ignorando el trabajo anterior (1629) de Albert Girard . Tienen aplicaciones en muchas áreas de las matemáticas, incluida la teoría de Galois , la teoría de invariantes , la teoría de grupos , la combinatoria , así como otras aplicaciones fuera de las matemáticas, incluida la relatividad general .

Enunciado matemático

Formulación en términos de polinomios simétricos

Sean x ₁ , ..., x _n variables, denotemos para k  ≥ 1 por p _k ( x ₁ , ..., x _n ) la suma de potencias k -ésima :

${\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k}=x_{1}^{k}+\cdots +x_{n}^{k},}$

y para k  ≥ 0 denotamos por e _k ( x ₁ , ..., x _n ) el polinomio simétrico elemental (es decir, la suma de todos los productos distintos de k variables distintas), por lo que

${\displaystyle {\begin{aligned}e_{0}(x_{1},\ldots ,x_{n})&=1,\\e_{1}(x_{1},\ldots ,x_{n})&=x_{1}+x_{2}+\cdots +x_{n},\\e_{2}(x_{1},\ldots ,x_{n})&=\sum _{1\leq i<j\leq n}x_{i}x_{j},\\&\;\;\vdots \\e_{n}(x_{1},\ldots ,x_{n})&=x_{1}x_{2}\cdots x_{n},\\e_{k}(x_{1},\ldots ,x_{n})&=0,\quad {\text{for}}\ k>n.\\\end{aligned}}}$

Entonces las identidades de Newton pueden enunciarse como

${\displaystyle ke_{k}(x_{1},\ldots ,x_{n})=\sum _{i=1}^{k}(-1)^{i-1}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}$

válido para todos n ≥ k ≥ 1 .

Además, uno tiene

${\displaystyle 0=\sum _{i=k-n}^{k}(-1)^{i-1}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}$

para todo k > n ≥ 1 .

Concretamente, se obtiene para los primeros valores de k :

${\displaystyle {\begin{aligned}e_{1}(x_{1},\ldots ,x_{n})&=p_{1}(x_{1},\ldots ,x_{n}),\\2e_{2}(x_{1},\ldots ,x_{n})&=e_{1}(x_{1},\ldots ,x_{n})p_{1}(x_{1},\ldots ,x_{n})-p_{2}(x_{1},\ldots ,x_{n}),\\3e_{3}(x_{1},\ldots ,x_{n})&=e_{2}(x_{1},\ldots ,x_{n})p_{1}(x_{1},\ldots ,x_{n})-e_{1}(x_{1},\ldots ,x_{n})p_{2}(x_{1},\ldots ,x_{n})+p_{3}(x_{1},\ldots ,x_{n}).\end{aligned}}}$

La forma y validez de estas ecuaciones no dependen del número n de variables (aunque sí del punto en el que el lado izquierdo se vuelve 0, es decir, después de la identidad n -ésima), lo que permite plantearlas como identidades en el anillo de funciones simétricas . En ese anillo se tiene

${\displaystyle {\begin{aligned}e_{1}&=p_{1},\\2e_{2}&=e_{1}p_{1}-p_{2}=p_{1}^{2}-p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+p_{3}={\tfrac {1}{2}}p_{1}^{3}-{\tfrac {3}{2}}p_{1}p_{2}+p_{3},\\4e_{4}&=e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4}={\tfrac {1}{6}}p_{1}^{4}-p_{1}^{2}p_{2}+{\tfrac {4}{3}}p_{1}p_{3}+{\tfrac {1}{2}}p_{2}^{2}-p_{4},\\\end{aligned}}}$

y así sucesivamente; aquí los lados izquierdos nunca se vuelven cero. Estas ecuaciones permiten expresar recursivamente la e _i en términos de la p _k ; para poder hacer lo inverso, se pueden reescribir como

${\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}p_{1}-2e_{2}=e_{1}^{2}-2e_{2},\\p_{3}&=e_{1}p_{2}-e_{2}p_{1}+3e_{3}=e_{1}^{3}-3e_{1}e_{2}+3e_{3},\\p_{4}&=e_{1}p_{3}-e_{2}p_{2}+e_{3}p_{1}-4e_{4}=e_{1}^{4}-4e_{1}^{2}e_{2}+4e_{1}e_{3}+2e_{2}^{2}-4e_{4},\\&{}\ \ \vdots \end{aligned}}}$

En general, tenemos

${\displaystyle p_{k}(x_{1},\ldots ,x_{n})=(-1)^{k-1}ke_{k}(x_{1},\ldots ,x_{n})+\sum _{i=1}^{k-1}(-1)^{k-1+i}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}$

válido para todo n  ≥ k  ≥ 1.

Además, uno tiene

${\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum _{i=k-n}^{k-1}(-1)^{k-1+i}e_{k-i}(x_{1},\ldots ,x_{n})p_{i}(x_{1},\ldots ,x_{n}),}$

para todo k  >  n  ≥ 1.

Aplicación a las raíces de un polinomio

El polinomio con raíces x _i puede desarrollarse como

${\displaystyle \prod _{i=1}^{n}(x-x_{i})=\sum _{k=0}^{n}(-1)^{k}e_{k}x^{n-k},}$

donde los coeficientes son los polinomios simétricos definidos anteriormente. Dadas las sumas de potencias de las raíces ${\displaystyle e_{k}(x_{1},\ldots ,x_{n})}$

${\displaystyle p_{k}(x_{1},\ldots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k},}$

Los coeficientes del polinomio con raíces pueden expresarse recursivamente en términos de las sumas de potencias como ${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle {\begin{aligned}e_{0}&=1,\\[4pt]-e_{1}&=-p_{1},\\[4pt]e_{2}&={\frac {1}{2}}(e_{1}p_{1}-p_{2}),\\[4pt]-e_{3}&=-{\frac {1}{3}}(e_{2}p_{1}-e_{1}p_{2}+p_{3}),\\[4pt]e_{4}&={\frac {1}{4}}(e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4}),\\&{}\ \ \vdots \end{aligned}}}$

Formular polinomios de esta manera es útil al utilizar el método de Delves y Lyness ^[1] para encontrar los ceros de una función analítica.

Aplicación al polinomio característico de una matriz

Cuando el polinomio anterior es el polinomio característico de una matriz (en particular cuando es la matriz compañera del polinomio), las raíces son los valores propios de la matriz, contados con su multiplicidad algebraica. Para cualquier entero positivo , la matriz tiene como valores propios las potencias , y cada valor propio de contribuye con su multiplicidad a la del valor propio de . Entonces, los coeficientes del polinomio característico de están dados por los polinomios simétricos elementales en esas potencias . En particular, la suma de , que es la suma de la potencia -ésima de las raíces del polinomio característico de , está dada por su traza : ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle x_{i}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {A} ^{k}}$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle x_{i}}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle \mathbf {A} ^{k}}$ ${\displaystyle \mathbf {A} ^{k}}$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle x_{i}^{k}}$ ${\displaystyle k}$ ${\displaystyle p_{k}}$ ${\displaystyle \mathbf {A} }$

$${\displaystyle p_{k}=\operatorname {tr} (\mathbf {A} ^{k})\,.}$$

Las identidades de Newton relacionan ahora las trazas de las potencias con los coeficientes del polinomio característico de . Si se utilizan en sentido inverso para expresar los polinomios simétricos elementales en términos de las sumas de potencias, se pueden utilizar para hallar el polinomio característico calculando únicamente las potencias y sus trazas. ${\displaystyle \mathbf {A} ^{k}}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathbf {A} ^{k}}$

Este cálculo requiere calcular las trazas de las potencias de las matrices y resolver un sistema triangular de ecuaciones. Ambas cosas se pueden hacer en la clase de complejidad NC (la resolución de un sistema triangular se puede hacer mediante la técnica de dividir y vencer). Por lo tanto, el polinomio característico de una matriz se puede calcular en NC. Por el teorema de Cayley-Hamilton , cada matriz satisface su polinomio característico, y una transformación simple permite encontrar la matriz adjunta en NC. ${\displaystyle \mathbf {A} ^{k}}$

La reorganización de los cálculos en una forma eficiente conduce al algoritmo de Faddeev-LeVerrier (1840), cuya rápida implementación paralela se debe a L. Csanky (1976). Su desventaja es que requiere división por números enteros, por lo que en general el campo debería tener característica 0.

Relación con la teoría de Galois

Para un n dado , los polinomios simétricos elementales e _k ( x ₁ ,..., x _n ) para k  = 1,..., n forman una base algebraica para el espacio de polinomios simétricos en x ₁ ,.... x _n : cada expresión polinómica en x _i que es invariante bajo todas las permutaciones de esas variables está dada por una expresión polinómica en esos polinomios simétricos elementales, y esta expresión es única hasta la equivalencia de expresiones polinómicas. Este es un hecho general conocido como el teorema fundamental de los polinomios simétricos , y las identidades de Newton proporcionan fórmulas explícitas en el caso de polinomios simétricos de suma de potencias. Aplicado al polinomio mónico con todos los coeficientes a _k considerados como parámetros libres, esto significa que cada expresión polinómica simétrica S ( x ₁ ,..., x _n ) en sus raíces puede ser expresada en cambio como una expresión polinómica P ( a ₁ ,..., a _n ) en términos de sus coeficientes solamente, en otras palabras sin requerir el conocimiento de las raíces. Este hecho también se desprende de consideraciones generales en la teoría de Galois (uno ve a k _como elementos de un cuerpo base con raíces en un cuerpo de extensión cuyo grupo de Galois los permuta de acuerdo con el grupo simétrico completo, y el cuerpo fijado bajo todos los elementos del grupo de Galois es el cuerpo base). ${\textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{n-k}}$

Las identidades de Newton permiten también expresar los polinomios simétricos elementales en términos de sumas de potencias de polinomios simétricos, demostrando que cualquier polinomio simétrico puede expresarse también en sumas de potencias. De hecho, las primeras n sumas de potencias también forman una base algebraica para el espacio de polinomios simétricos.

Identidades relacionadas

Hay una serie de (familias de) identidades que, si bien deben distinguirse de las identidades de Newton, están muy estrechamente relacionadas con ellas.

Una variante que utiliza polinomios simétricos homogéneos completos

Al denotar por h _k el polinomio simétrico homogéneo completo (es decir, la suma de todos los monomios de grado  k ), los polinomios de suma de potencias también satisfacen identidades similares a las identidades de Newton, pero que no implican ningún signo menos. Expresados ​​como identidades de en el anillo de funciones simétricas , se leen

${\displaystyle kh_{k}=\sum _{i=1}^{k}h_{k-i}p_{i},}$

válido para todos los n ≥  k  ≥ 1. Al contrario de las identidades de Newton, los lados izquierdos no se vuelven cero para valores grandes  de k , y los lados derechos contienen cada vez más términos distintos de cero. Para los primeros valores de k , se tiene

${\displaystyle {\begin{aligned}h_{1}&=p_{1},\\2h_{2}&=h_{1}p_{1}+p_{2},\\3h_{3}&=h_{2}p_{1}+h_{1}p_{2}+p_{3}.\\\end{aligned}}}$

Estas relaciones pueden justificarse mediante un argumento análogo al que se obtiene comparando coeficientes en series de potencias dado anteriormente, basado en este caso en la identidad de la función generadora.

${\displaystyle \sum _{k=0}^{\infty }h_{k}(x_{1},\ldots ,x_{n})t^{k}=\prod _{i=1}^{n}{\frac {1}{1-x_{i}t}}.}$

Las pruebas de las identidades de Newton, como las que se dan a continuación, no pueden adaptarse fácilmente para demostrar estas variantes de esas identidades.

Expresar polinomios simétricos elementales en términos de sumas de potencias

Como se mencionó, las identidades de Newton se pueden utilizar para expresar recursivamente polinomios simétricos elementales en términos de sumas de potencias. Para ello es necesario introducir denominadores enteros, por lo que se puede hacer en el anillo Λ _Q de funciones simétricas con coeficientes racionales:

${\displaystyle {\begin{aligned}e_{1}&=p_{1},\\e_{2}&=\textstyle {\frac {1}{2}}p_{1}^{2}-{\frac {1}{2}}p_{2}&&=\textstyle {\frac {1}{2}}(p_{1}^{2}-p_{2}),\\e_{3}&=\textstyle {\frac {1}{6}}p_{1}^{3}-{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&=\textstyle {\frac {1}{6}}(p_{1}^{3}-3p_{1}p_{2}+2p_{3}),\\e_{4}&=\textstyle {\frac {1}{24}}p_{1}^{4}-{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}-{\frac {1}{4}}p_{4}&&=\textstyle {\frac {1}{24}}(p_{1}^{4}-6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}-6p_{4}),\\&~~\vdots \\e_{n}&=(-1)^{n}\sum _{m_{1}+2m_{2}+\cdots +nm_{n}=n \atop m_{1}\geq 0,\ldots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {(-p_{i})^{m_{i}}}{m_{i}!\,i^{m_{i}}}}\\\end{aligned}}}$

y así sucesivamente. ^[2] La fórmula general se puede expresar convenientemente como

${\displaystyle e_{k}={\frac {(-1)^{k}}{k!}}B_{k}(-p_{1},-1!\,p_{2},-2!\,p_{3},\ldots ,-(k-1)!\,p_{k}),}$

donde B _n es el polinomio de Bell exponencial completo . Esta expresión también conduce a la siguiente identidad para funciones generadoras:

${\displaystyle \sum _{k=0}^{\infty }e_{k}\,t^{k}=\exp \left(\sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{k}}p_{k}\,t^{k}\right).}$

Aplicadas a un polinomio mónico, estas fórmulas expresan los coeficientes en términos de las sumas de potencias de las raíces: reemplaza cada e _i por a _i y cada p _k por s _k .

Expresar polinomios simétricos homogéneos completos en términos de sumas de potencias

Las relaciones análogas que involucran polinomios simétricos homogéneos completos se pueden desarrollar de manera similar, dando ecuaciones

${\displaystyle {\begin{aligned}h_{1}&=p_{1},\\h_{2}&=\textstyle {\frac {1}{2}}p_{1}^{2}+{\frac {1}{2}}p_{2}&&=\textstyle {\frac {1}{2}}(p_{1}^{2}+p_{2}),\\h_{3}&=\textstyle {\frac {1}{6}}p_{1}^{3}+{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&=\textstyle {\frac {1}{6}}(p_{1}^{3}+3p_{1}p_{2}+2p_{3}),\\h_{4}&=\textstyle {\frac {1}{24}}p_{1}^{4}+{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}+{\frac {1}{4}}p_{4}&&=\textstyle {\frac {1}{24}}(p_{1}^{4}+6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}+6p_{4}),\\&~~\vdots \\h_{k}&=\sum _{m_{1}+2m_{2}+\cdots +km_{k}=k \atop m_{1}\geq 0,\ldots ,m_{k}\geq 0}\prod _{i=1}^{k}{\frac {p_{i}^{m_{i}}}{m_{i}!\,i^{m_{i}}}}\end{aligned}}}$

y así sucesivamente, en los que sólo hay signos más. En términos del polinomio de Bell completo,

${\displaystyle h_{k}={\frac {1}{k!}}B_{k}(p_{1},1!\,p_{2},2!\,p_{3},\ldots ,(k-1)!\,p_{k}).}$

Estas expresiones corresponden exactamente a los polinomios de índice de ciclo de los grupos simétricos , si uno interpreta las sumas de potencias p _i como indeterminadas: el coeficiente en la expresión para h _k de cualquier monomio p ₁ ^{m ₁} p ₂ ^{m ₂} ... p _l ^{m _l} es igual a la fracción de todas las permutaciones de k que tienen m ₁ puntos fijos, m ₂ ciclos de longitud 2, ..., y m _l ciclos de longitud l . Explícitamente, este coeficiente puede escribirse como donde ; este N es el número de permutaciones que conmutan con cualquier permutación dada  π del tipo de ciclo dado. Las expresiones para las funciones simétricas elementales tienen coeficientes con el mismo valor absoluto, pero un signo igual al signo de  π , a saber (−1) ^{m ₂ + m ₄ +...} . ${\displaystyle 1/N}$ ${\textstyle N=\prod _{i=1}^{l}(m_{i}!\,i^{m_{i}})}$

Esto se puede demostrar considerando el siguiente paso inductivo:

${\displaystyle {\begin{aligned}mf(m;m_{1},\ldots ,m_{n})&=f(m-1;m_{1}-1,\ldots ,m_{n})+\cdots +f(m-n;m_{1},\ldots ,m_{n}-1)\\m_{1}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}+\cdots +nm_{n}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}&=m\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}\end{aligned}}}$

Por analogía con la derivación de la función generadora de , también podemos obtener la función generadora de , en términos de las sumas de potencias, como: ${\displaystyle e_{n}}$ ${\displaystyle h_{n}}$

${\displaystyle \sum _{k=0}^{\infty }h_{k}\,t^{k}=\exp \left(\sum _{k=1}^{\infty }{\frac {p_{k}}{k}}\,t^{k}\right).}$

Esta función generadora es entonces el exponencial pletístico de . ${\displaystyle p_{1}t=(x_{1}+\cdots +x_{n})t}$

Expresar sumas de potencias en términos de polinomios simétricos elementales

También se pueden utilizar las identidades de Newton para expresar sumas de potencias en términos de polinomios simétricos elementales, lo que no introduce denominadores:

${\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}^{2}-2e_{2},\\p_{3}&=e_{1}^{3}-3e_{2}e_{1}+3e_{3},\\p_{4}&=e_{1}^{4}-4e_{2}e_{1}^{2}+4e_{3}e_{1}+2e_{2}^{2}-4e_{4},\\p_{5}&=e_{1}^{5}-5e_{2}e_{1}^{3}+5e_{3}e_{1}^{2}+5e_{2}^{2}e_{1}-5e_{4}e_{1}-5e_{3}e_{2}+5e_{5},\\p_{6}&=e_{1}^{6}-6e_{2}e_{1}^{4}+6e_{3}e_{1}^{3}+9e_{2}^{2}e_{1}^{2}-6e_{4}e_{1}^{2}-12e_{3}e_{2}e_{1}+6e_{5}e_{1}-2e_{2}^{3}+3e_{3}^{2}+6e_{4}e_{2}-6e_{6}.\end{aligned}}}$

Las primeras cuatro fórmulas fueron obtenidas por Albert Girard en 1629 (es decir, antes de Newton). ^[3]

La fórmula general (para todos los números enteros positivos m ) es:

${\displaystyle p_{m}=(-1)^{m}m\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}{\frac {(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!\,r_{2}!\cdots r_{m}!}}\prod _{i=1}^{m}(-e_{i})^{r_{i}}.}$

Esto se puede expresar convenientemente en términos de polinomios de Bell ordinarios como

${\displaystyle p_{m}=(-1)^{m}m\sum _{k=1}^{m}{\frac {1}{k}}{\hat {B}}_{m,k}(-e_{1},\ldots ,-e_{m-k+1}),}$

o equivalentemente como la función generadora : ^[4]

${\displaystyle {\begin{aligned}\sum _{k=1}^{\infty }(-1)^{k-1}p_{k}{\frac {t^{k}}{k}}&=\ln \left(1+e_{1}t+e_{2}t^{2}+e_{3}t^{3}+\cdots \right)\\&=e_{1}t-{\frac {1}{2}}\left(e_{1}^{2}-2e_{2}\right)t^{2}+{\frac {1}{3}}\left(e_{1}^{3}-3e_{1}e_{2}+3e_{3}\right)t^{3}+\cdots ,\end{aligned}}}$

que es análoga a la función generadora exponencial del polinomio de Bell dada en la subsección anterior.

La fórmula de suma múltiple anterior se puede demostrar considerando el siguiente paso inductivo:

${\displaystyle {\begin{aligned}f(m;\;r_{1},\ldots ,r_{n})={}&f(m-1;\;r_{1}-1,\cdots ,r_{n})+\cdots +f(m-n;\;r_{1},\ldots ,r_{n}-1)\\[8pt]={}&{\frac {1}{(r_{1}-1)!\cdots r_{n}!}}(m-1)(r_{1}+\cdots +r_{n}-2)!+\cdots \\&\cdots +{\frac {1}{r_{1}!\cdots (r_{n}-1)!}}(m-n)(r_{1}+\cdots +r_{n}-2)!\\[8pt]={}&{\frac {1}{r_{1}!\cdots r_{n}!}}\left[r_{1}(m-1)+\cdots +r_{n}(m-n)\right]\left[r_{1}+\cdots +r_{n}-2\right]!\\[8pt]={}&{\frac {1}{r_{1}!\cdots r_{n}!}}\left[m(r_{1}+\cdots +r_{n})-m\right]\left[r_{1}+\cdots +r_{n}-2\right]!\\[8pt]={}&{\frac {m(r_{1}+\cdots +r_{n}-1)!}{r_{1}!\cdots r_{n}!}}\end{aligned}}}$

Expresar sumas de potencias en términos de polinomios simétricos homogéneos completos

Finalmente, se pueden utilizar las identidades variantes que involucran polinomios simétricos homogéneos completos de manera similar para expresar sumas de potencias en términos de ellos:

${\displaystyle {\begin{aligned}p_{1}&=+h_{1},\\p_{2}&=-h_{1}^{2}+2h_{2},\\p_{3}&=+h_{1}^{3}-3h_{2}h_{1}+3h_{3},\\p_{4}&=-h_{1}^{4}+4h_{2}h_{1}^{2}-4h_{3}h_{1}-2h_{2}^{2}+4h_{4},\\p_{5}&=+h_{1}^{5}-5h_{2}h_{1}^{3}+5h_{2}^{2}h_{1}+5h_{3}h_{1}^{2}-5h_{3}h_{2}-5h_{4}h_{1}+5h_{5},\\p_{6}&=-h_{1}^{6}+6h_{2}h_{1}^{4}-9h_{2}^{2}h_{1}^{2}-6h_{3}h_{1}^{3}+2h_{2}^{3}+12h_{3}h_{2}h_{1}+6h_{4}h_{1}^{2}-3h_{3}^{2}-6h_{4}h_{2}-6h_{1}h_{5}+6h_{6},\\\end{aligned}}}$

y así sucesivamente. Aparte de la sustitución de cada e _i por el correspondiente h _i , el único cambio con respecto a la familia de identidades anterior está en los signos de los términos, que en este caso dependen sólo del número de factores presentes: el signo del monomio es −(−1) ^{m ₁ + m ₂ + m ₃ +...} . En particular, la descripción anterior del valor absoluto de los coeficientes se aplica aquí también. ${\textstyle \prod _{i=1}^{l}h_{i}^{m_{i}}}$

La fórmula general (para todos los números enteros no negativos m ) es:

${\displaystyle p_{m}=-\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}{\frac {m(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!\,r_{2}!\cdots r_{m}!}}\prod _{i=1}^{m}(-h_{i})^{r_{i}}}$

Expresiones como determinantes

Se pueden obtener fórmulas explícitas para las expresiones anteriores en forma de determinantes, considerando las primeras n identidades de Newton (o sus contrapartes para los polinomios homogéneos completos) como ecuaciones lineales en las que se conocen las funciones simétricas elementales y las sumas de potencias son incógnitas (o viceversa), y aplicar la regla de Cramer para encontrar la solución para la incógnita final. Por ejemplo, tomando las identidades de Newton en la forma

${\displaystyle {\begin{aligned}e_{1}&=1p_{1},\\2e_{2}&=e_{1}p_{1}-1p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+1p_{3},\\&\,\,\,\vdots \\ne_{n}&=e_{n-1}p_{1}-e_{n-2}p_{2}+\cdots +(-1)^{n}e_{1}p_{n-1}+(-1)^{n-1}p_{n}\end{aligned}}}$

Consideramos y como incógnitas y resolvemos para el último, obteniendo ${\displaystyle p_{1},-p_{2},p_{3},\ldots ,(-1)^{n}p_{n-1}}$ ${\displaystyle p_{n}}$

${\displaystyle {\begin{aligned}p_{n}={}&{\begin{vmatrix}1&0&\cdots &&e_{1}\\e_{1}&1&0&\cdots &2e_{2}\\e_{2}&e_{1}&1&&3e_{3}\\\vdots &&\ddots &\ddots &\vdots \\e_{n-1}&\cdots &e_{2}&e_{1}&ne_{n}\end{vmatrix}}{\begin{vmatrix}1&0&\cdots &\\e_{1}&1&0&\cdots \\e_{2}&e_{1}&1&\\\vdots &&\ddots &\ddots \\e_{n-1}&\cdots &e_{2}&e_{1}&1\end{vmatrix}}^{-1}\\[7pt]={(-1)^{n-1}}&{\begin{vmatrix}1&0&\cdots &&e_{1}\\e_{1}&1&0&\cdots &2e_{2}\\e_{2}&e_{1}&1&&3e_{3}\\\vdots &&\ddots &\ddots &\vdots \\e_{n-1}&\cdots &e_{2}&e_{1}&ne_{n}\end{vmatrix}}\\[7pt]={}&{\begin{vmatrix}e_{1}&1&0&\cdots \\2e_{2}&e_{1}&1&0&\cdots \\3e_{3}&e_{2}&e_{1}&1\\\vdots &&&\ddots &\ddots \\ne_{n}&e_{n-1}&\cdots &&e_{1}\end{vmatrix}}.\end{aligned}}}$

Resolver para en lugar de para es similar a los cálculos análogos para los polinomios simétricos homogéneos completos; en cada caso los detalles son ligeramente más confusos que los resultados finales, que son (Macdonald 1979, p. 20): ${\displaystyle e_{n}}$ ${\displaystyle p_{n}}$

${\displaystyle {\begin{aligned}e_{n}={\frac {1}{n!}}&{\begin{vmatrix}p_{1}&1&0&\cdots \\p_{2}&p_{1}&2&0&\cdots \\\vdots &&\ddots &\ddots \\p_{n-1}&p_{n-2}&\cdots &p_{1}&n-1\\p_{n}&p_{n-1}&\cdots &p_{2}&p_{1}\end{vmatrix}}\\[7pt]p_{n}=(-1)^{n-1}&{\begin{vmatrix}h_{1}&1&0&\cdots \\2h_{2}&h_{1}&1&0&\cdots \\3h_{3}&h_{2}&h_{1}&1\\\vdots &&&\ddots &\ddots \\nh_{n}&h_{n-1}&\cdots &&h_{1}\end{vmatrix}}\\[7pt]h_{n}={\frac {1}{n!}}&{\begin{vmatrix}p_{1}&-1&0&\cdots \\p_{2}&p_{1}&-2&0&\cdots \\\vdots &&\ddots &\ddots \\p_{n-1}&p_{n-2}&\cdots &p_{1}&1-n\\p_{n}&p_{n-1}&\cdots &p_{2}&p_{1}\end{vmatrix}}.\end{aligned}}}$

Obsérvese que el uso de determinantes hace que la fórmula para tenga signos negativos adicionales en comparación con la de , mientras que la situación para la forma expandida dada anteriormente es opuesta. Como se señaló en (Littlewood 1950, p. 84), se puede obtener alternativamente la fórmula para tomando el permanente de la matriz para en lugar del determinante y, de manera más general, se puede obtener una expresión para cualquier polinomio de Schur tomando el inmanente correspondiente de esta matriz. ${\displaystyle h_{n}}$ ${\displaystyle e_{n}}$ ${\displaystyle h_{n}}$ ${\displaystyle e_{n}}$

Derivación de las identidades

Cada una de las identidades de Newton puede comprobarse fácilmente mediante álgebra elemental; sin embargo, su validez en general requiere una demostración. A continuación se presentan algunas posibles deducciones.

Del caso especialnorte = a

Se puede obtener la k -ésima identidad de Newton en k variables mediante sustitución en

${\displaystyle \prod _{i=1}^{k}(t-x_{i})=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})t^{i}}$

como sigue. Sustituyendo x _j por t se obtiene

${\displaystyle 0=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k}){x_{j}}^{i}\quad {\text{for }}1\leq j\leq k}$

Sumando todos los j obtenemos

${\displaystyle 0=(-1)^{k}ke_{k}(x_{1},\ldots ,x_{k})+\sum _{i=1}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})p_{i}(x_{1},\ldots ,x_{k}),}$

donde los términos para i  = 0 se sacaron de la suma porque p ₀ (usualmente) no está definido. Esta ecuación da inmediatamente la k -ésima identidad de Newton en k variables. Dado que esta es una identidad de polinomios simétricos (homogéneos) de grado k , su validez para cualquier número de variables se sigue de su validez para k variables. Concretamente, las identidades en n  <  k variables se pueden deducir fijando k  −  n variables a cero. La k -ésima identidad de Newton en n  >  k variables contiene más términos en ambos lados de la ecuación que la de k variables, pero su validez estará asegurada si los coeficientes de cualquier monomio coinciden. Debido a que ningún monomio individual involucra más de k de las variables, el monomio sobrevivirá a la sustitución de cero por algún conjunto de n  −  k (otras) variables, después de lo cual la igualdad de coeficientes es la que surge en la k -ésima identidad de Newton en k variables (adecuadamente elegidas).

Comparación de coeficientes en serie

Otra derivación puede obtenerse mediante cálculos en el anillo de series de potencias formales R [[ t ]], donde R es Z [ x ₁ ,..., x _n ], el anillo de polinomios en n variables x ₁ ,..., x _n sobre los números enteros.

Partiendo de nuevo de la relación básica

${\displaystyle \prod _{i=1}^{n}(t-x_{i})=\sum _{k=0}^{n}(-1)^{k}a_{k}t^{n-k}}$

y "invirtiendo los polinomios" sustituyendo 1/ t por t y luego multiplicando ambos lados por t ⁿ para eliminar las potencias negativas de t , se obtiene

${\displaystyle \prod _{i=1}^{n}(1-x_{i}t)=\sum _{k=0}^{n}(-1)^{k}a_{k}t^{k}.}$

(el cálculo anterior debe realizarse en el campo de fracciones de R [[ t ]]; alternativamente, la identidad puede obtenerse simplemente evaluando el producto del lado izquierdo)

Al intercambiar los lados y expresar las a _i como los polinomios simétricos elementales que representan, se obtiene la identidad

${\displaystyle \sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\ldots ,x_{n})t^{k}=\prod _{i=1}^{n}(1-x_{i}t).}$

Se diferencian formalmente ambos lados con respecto a t , y luego (por conveniencia) se multiplica por t , para obtener

${\displaystyle {\begin{aligned}\sum _{k=0}^{n}(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})t^{k}&=t\sum _{i=1}^{n}\left[(-x_{i})\prod \nolimits _{j\neq i}(1-x_{j}t)\right]\\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}t}{1-x_{i}t}}\right)\prod \nolimits _{j=1}^{n}(1-x_{j}t)\\&=-\left[\sum _{i=1}^{n}\sum _{j=1}^{\infty }(x_{i}t)^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell }e_{\ell }(x_{1},\ldots ,x_{n})t^{\ell }\right]\\&=\left[\sum _{j=1}^{\infty }p_{j}(x_{1},\ldots ,x_{n})t^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1},\ldots ,x_{n})t^{\ell }\right],\\\end{aligned}}}$

donde el polinomio del lado derecho se reescribió primero como una función racional para poder factorizar un producto de la suma, luego la fracción en el sumando se desarrolló como una serie en t , utilizando la fórmula

${\displaystyle {\frac {X}{1-X}}=X+X^{2}+X^{3}+X^{4}+X^{5}+\cdots ,}$

y finalmente se recopiló el coeficiente de cada t  ^j , lo que dio una suma de potencias. (La serie en t es una serie de potencias formal, pero alternativamente puede considerarse como una expansión de la serie para t suficientemente cerca de 0, para aquellos que se sienten más cómodos con eso; de hecho, uno no está interesado en la función aquí, sino solo en los coeficientes de la serie). Comparando los coeficientes de t ^k en ambos lados se obtiene

${\displaystyle (-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})=\sum _{j=1}^{k}(-1)^{k-j-1}p_{j}(x_{1},\ldots ,x_{n})e_{k-j}(x_{1},\ldots ,x_{n}),}$

lo que da la k -ésima identidad de Newton.

Como suma telescópica de identidades de funciones simétricas

La siguiente derivación, dada esencialmente en (Mead, 1992), se formula en el anillo de funciones simétricas para mayor claridad (todas las identidades son independientes del número de variables). Fije algún k  > 0 y defina la función simétrica r ( i ) para 2 ≤  i  ≤  k como la suma de todos los monomios distintos de grado k obtenidos al multiplicar una variable elevada a la potencia  i con k  −  i otras variables distintas (esta es la función simétrica monomial m _γ donde γ es una forma de gancho ( i ,1,1,...,1)). En particular r ( k ) =  p _k ; para r (1) la descripción equivaldría a la de e _k , pero este caso se excluyó ya que aquí los monomios ya no tienen ninguna variable distinguida. Todos los productos p _i e _{k − i} se pueden expresar en términos de r ( j ) con el primer y último caso siendo algo especiales. Se tiene

${\displaystyle p_{i}e_{k-i}=r(i)+r(i+1)\quad {\text{for }}1<i<k}$

ya que cada producto de términos de la izquierda que involucran variables distintas contribuye a r ( i ), mientras que aquellos donde la variable de p _i ya ocurre entre las variables del término de e _{k − i} contribuyen a r ( i  + 1), y todos los términos de la derecha se obtienen exactamente una vez. Para i  =  k se multiplica por e ₀  = 1, dando trivialmente

${\displaystyle p_{k}e_{0}=p_{k}=r(k).}$

Finalmente el producto p ₁ e _{k −1} para i  = 1 da contribuciones a r ( i  + 1) =  r (2) como para otros valores i  <  k , pero las contribuciones restantes producen k veces cada monomio de e _k , ya que cualquiera de las variables puede provenir del factor p ₁ ; por lo tanto

${\displaystyle p_{1}e_{k-1}=ke_{k}+r(2).}$

La k -ésima identidad de Newton se obtiene ahora tomando la suma alternada de estas ecuaciones, en la que todos los términos de la forma r ( i ) se cancelan.

Prueba combinatoria

En (Zeilberger, 1984) se da una breve prueba combinatoria de las identidades de Newton ^[5].

Véase también

• Polinomio simétrico de suma de potencias
• Polinomio simétrico elemental
• Desigualdades de Newton
• Función simétrica
• Soluciones fluidas , un artículo que ofrece una aplicación de las identidades de Newton para calcular el polinomio característico del tensor de Einstein en el caso de un fluido perfecto y artículos similares sobre otros tipos de soluciones exactas en relatividad general .

Referencias

1. Delves, LM (1967). "Un método numérico para localizar los ceros de una función analítica". Matemáticas de la computación . 21 (100): 543–560. doi : 10.2307/2004999 . JSTOR  2004999.
2. Nb, los coeficientes de los términos del producto ponderado en la suma dada por la identidad anterior están relacionados con los números M2 en la Sección 26.4 del DLMF y/o los coeficientes involucrados en las expansiones de la fórmula de Faa di Bruno.
3. Tignol, Jean-Pierre (2004). Teoría de ecuaciones algebraicas de Galois (edición reimpresa). River Edge, NJ: World Scientific. pp. 37–38. ISBN 981-02-4541-6.
4. Weisstein, Eric W. "Polinomio simétrico". MathWorld .
5. Zeilberger, Doron (1984). "Una prueba combinatoria de las identidades de Newton". Matemáticas discretas . 49 (3): 319. doi :10.1016/0012-365X(84)90171-7.

• Tignol, Jean-Pierre (2001). La teoría de las ecuaciones algebraicas de Galois . Singapur: World Scientific. ISBN 978-981-02-4541-2.
• Bergeron, F.; Labelle, G. y Leroux, P. (1998). Especies combinatorias y estructuras arbóreas . Cambridge: Cambridge University Press. ISBN 978-0-521-57323-8.
• Cameron, Peter J. (1999). Grupos de permutación . Cambridge: Cambridge University Press. ISBN 978-0-521-65378-7.
• Cox, David ; Little, John y O'Shea, Donal (1992). Ideales, variedades y algoritmos . Nueva York: Springer-Verlag. ISBN. 978-0-387-97847-5.
• Eppstein, D. ; Goodrich, MT (2007). "Identificación de rezagados con eficiencia espacial en flujos de datos de ida y vuelta mediante identidades de Newton y filtros Bloom invertibles". Algorithms and Data Structures, 10th International Workshop, WADS 2007 . Springer-Verlag, Lecture Notes in Computer Science 4619. págs. 637–648. arXiv : 0704.3313 . Código Bibliográfico :2007arXiv0704.3313E.
• Littlewood, DE (1950). La teoría de los caracteres de grupo y las representaciones matriciales de grupos . Oxford: Oxford University Press. viii+310. ISBN 0-8218-4067-3.
• Macdonald, IG (1979). Funciones simétricas y polinomios de Hall . Oxford Mathematical Monographs. Oxford: The Clarendon Press, Oxford University Press. viii+180. ISBN 0-19-853530-9.Sr. 0553598  .
• Macdonald, IG (1995). Funciones simétricas y polinomios de Hall . Oxford Mathematical Monographs (segunda edición). Nueva York: Oxford Science Publications. The Clarendon Press, Oxford University Press. pág. x+475. ISBN 0-19-853489-2.Señor 1354144  .
• Mead, DG (1992). "Las identidades de Newton". The American Mathematical Monthly . 99 (8). Asociación Matemática de América: 749–751. doi :10.2307/2324242. JSTOR  2324242.
• Stanley, Richard P. (1999). Combinatoria enumerativa, vol. 2. Cambridge University Press. ISBN 0-521-56069-1. (tapa dura). (libro de bolsillo).
• Sturmfels, Bernd (1992). Algoritmos en teoría invariante . Nueva York: Springer-Verlag. ISBN 978-0-387-82445-1.
• Tucker, Alan (1980). Combinatoria aplicada (quinta edición). Nueva York: Wiley. ISBN 978-0-471-73507-6.

Enlaces externos

• Fórmulas de Newton-Girard en MathWorld
• Una prueba matricial de las identidades de Newton en la revista Mathematics
• Aplicación sobre el número de raíces reales
• Una prueba combinatoria de las identidades de Newton por Doron Zeilberger