Identidades de Newton
En matemáticas, las identidades de Newton, también conocidas como las fórmulas Newton-Girard, son dos maneras diferentes de describir la raíz de un polinomio. Concretamente, relacionan las sumas de potencias con los polinomios simétricos elementales. Evaluada en las raíces de un polinomio mónico P en una variable, permiten expresar las sumas de la potencia k-n de todas las raíces de P (contadas con su multiplicidad) en términos de los coeficientes de P, sin encontrar en realidad aquellas raíces. Estas identidades fueron encontradas por Isaac Newton alrededor de 1666, aparentemente ignorando el trabajo anterior (1629) de Albert Girard.
Estas identidades tienen aplicaciones en muchas áreas de matemática, incluyendo la teoría de Galois, teoría de invariantes, teoría de grupos, combinatoria, así como más aplicaciones fuera de la matemática, incluyendo la relatividad general.
Enunciado matemático
Formulación en términos de polinomios simétricos
Sean x1, ..., xn variables, denotar k ≥ 1 por pk(x1, . .., xn) la k-ésima suma de potencias:
y para k ≥ 0 denote por ek(x1, ..., xn) el polinomio simétrico elemental (es decir, la suma de todos productos distintos de k variables distintas), por lo que
Entonces las identidades de Newton se pueden establecer como
expresión válida para todos los n ≥ 1 y n ≥ k ≥ 1.
Además,
para todos los k > n ≥ 1.
Concretamente, se obtiene para los primeros valores de k:
La forma y la validez de estas ecuaciones no dependen del número n de variables (aunque sí lo hace el punto donde el lado izquierdo se convierte en 0, es decir, después de la identidad n-ésima), lo que hace es posible enunciarlos como identidades en el anillo de funciones simétricas. En ese anillo se tiene que:
y así; aquí los lados izquierdos nunca se vuelven cero. Estas ecuaciones permiten expresar recursivamente la ei en términos de la pk; para poder hacer lo contrario, se puede reescribirlos como
En general, se tiene que
enunciado válido para todo n ≥ 1 y n ≥k ≥ 1.
Además,
para todo k > n ≥ 1.
Aplicación a las raíces de un polinomio
El polinomio con raíces xi se puede expandir como
donde los coeficientes son los polinomios simétricos definidos anteriormente. Dadas las sumas de potencias de las raíces
los coeficientes del polinomio con raíces pueden expresarse recursivamente en términos de las sumas de potencias como
Formular polinomios de esta manera es útil para usar 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 A (en particular cuando A 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 k, la matriz Ak tiene como valores propios las potencias xik, y cada valor propio de A aporta su multiplicidad a la del valor propio xik de Ak. Entonces, los coeficientes del polinomio característico de Ak están dados por los polinomios simétricos elementales en esas potencias xik. En particular, la suma de xik, que es la k-ésima suma de potencias pk de las raíces del polinomio característico de A, viene dada por su traza:
Las identidades de Newton ahora relacionan las trazas de las potencias Ak con los coeficientes del polinomio característico de A. Usándolas a la inversa para expresar los polinomios simétricos elementales en términos de sumas de potencias, se pueden utilizar para encontrar el polinomio característico calculando solo las potencias Ak y sus trazas.
Este cálculo requiere obtener las trazas de las potencias de la matriz Ak y resolver un sistema triangular de ecuaciones. Ambos se pueden hacer en la clase de complejidad NC (la resolución de un sistema triangular se puede hacer por el procedimiento de divide y vencerás). Por lo tanto, el polinomio característico de una matriz se puede calcular en NC. Por el teorema de Cayley-Hamilton, toda matriz satisface su polinomio característico, y una transformación simple permite encontrar la matriz de adjuntos en NC.
La reorganización de los cálculos en una forma eficiente conduce al "algoritmo de Faddeev-LeVerrier" (1840). Una versión rápida del mismo con cálculos en paralelo se debe a L. Csanky (1976). Su desventaja es que requiere división por enteros, por lo que en general el cuerpo debe tener la característica 0.
Relación con la teoría de Galois
Para un n dado, los polinomios simétricos elementales ek(x1,...,xn) para k = 1 ,..., n forman una base algebraica para el espacio de polinomios simétricos en x1,.... xn: toda expresión polinomial en xi 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 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 ak considerados como parámetros libres, esto significa que toda expresión polinomial simétrica S(x1,...,xn) en sus raíces puede expresarse en cambio como una expresión polinomial P(a1,...,an) en términos de sus coeficientes solamente, en otras palabras, sin requerir conocimiento de las raíces. Este hecho también se deriva de consideraciones generales en la teoría de Galois (donde los ak se consideran como elementos de un cuerpo base con raíces en un cuerpo de extensión cuyo grupo de Galois las permuta de acuerdo con el grupo simétrico completo, y el cuerpo fijo bajo todos los elementos del grupo de Galois es el cuerpo base).
Las identidades de Newton también permiten expresar los polinomios simétricos elementales en términos de los polinomios simétricos de suma de potencias, mostrando que cualquier polinomio simétrico también se puede expresar en sumas de potencias. De hecho, las primeras sumas de potencias n 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.
Variante que utiliza polinomios simétricos homogéneos completos
Denotando como hk el polinomio simétrico homogéneo completo que es 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 sin incluir ningún signo menos. Expresados como identidades en un anillo de funciones simétricas, se leen como
expresión válida para todos los n ≥ k ≥ 1. Al contrario de las identidades de Newton, los lados de la izquierda no se vuelven cero para valores de k grandes, y los lados de la derecha contienen cada vez más términos distintos de cero. Para los primeros valores de k, se tiene que
Estas relaciones pueden justificarse mediante un argumento análogo al de la comparación de coeficientes en series de potencias dado anteriormente, basado en este caso en la función generadora identidad
Las pruebas de las identidades de Newton, como las que se dan a continuación, no se pueden adaptar fácilmente para probar estas variantes de esas identidades.
Expresión de polinomios simétricos elementales en términos de sumas de potencias
Como ya se ha mencionado, las identidades de Newton se pueden usar para expresar polinomios simétricos elementales recursivamente en términos de sumas de potencias. Hacerlo requiere la introducción de denominadores enteros, lo que se puede hacer en el anillo ΛQ de funciones simétricas con coeficientes racionales:
etcétera.[2] La fórmula general se puede expresar convenientemente como
donde Bn es la exponencial completa de los polinomios de Bell. Esta expresión también conduce a la siguiente identidad para generar funciones:
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 ei por ai y cada pk por s k.
Expresión de 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 las ecuaciones
y así sucesivamente, en las que solo hay signos más. En términos del polinomio de Bell completo,
Estas expresiones corresponden exactamente a los polinomios de índice cíclico de los grupos simétricos, si se interpretan las sumas de potencias pi como indeterminadas: el coeficiente en la expresión para hk de cualquier monomio p1m1 p2m2...plml es igual a la fracción de todas las permutaciones de k que tienen m1 puntos fijos, m2 ciclos de longitud 2, ..., y ml ciclos de longitud l. Explícitamente, este coeficiente se puede escribir como donde ; esta 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)m2+m4+....
Se puede probar considerando el siguiente paso inductivo:
Por analogía con la derivación de la función generadora del , también podemos obtener la función generadora del , en términos de las sumas de potencias, como:
Esta función generadora es, por tanto, la exponencial plethystica de .
Expresión de sumas de potencias en términos de polinomios simétricos elementales
También se pueden usar las identidades de Newton para expresar sumas de potencias en términos de polinomios simétricos elementales, lo que no introduce denominadores:
Las primeras cuatro fórmulas fueron obtenidas por Albert Girard en 1629 (por lo tanto, antes que Newton).[3]
La fórmula general (para todos los enteros positivos m) es:
Esto puede expresarse convenientemente en términos de polinomios de Bell ordinarios como
o equivalentemente como función generadora:[4]
que es análoga a la función generadora exponencial de los polinomios de Bell dada en la subsección previa.
La fórmula de suma múltiple anterior se puede probar considerando el siguiente paso inductivo:
Expresión de sumas de potencias en términos de polinomios simétricos homogéneos completos
Finalmente, se pueden usar las identidades variantes que involucran polinomios simétricos homogéneos completos de manera similar para expresar sumas de potencias en términos de ellos:
y así sucesivamente. Aparte de la sustitución de cada ei por la correspondiente hi, el único cambio respecto a la anterior familia de identidades está en los signos de los términos, que en este caso dependen únicamente del número de factores presentes: el signo del monomio es −(−1)m1+m2+m3+.... En particular, la descripción anterior del valor absoluto de los coeficientes también se aplica aquí.
La fórmula general (para todos los enteros no negativos m) es:
Expresiones como determinantes
Se pueden obtener fórmulas explícitas para las expresiones anteriores en forma de determinantes, considerando la primera n de las 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 aplicando la regla de Cramer para encontrar la solución para la incógnita final. Por ejemplo, tomando las identidades de Newton en la forma
se consideran y como incógnitas, y se resuelve la última, dando
Resolver para en lugar de es un problema similar, como los cálculos análogos para los polinomios simétricos homogéneos completos. En cada caso, los detalles son un poco más confusos que los resultados finales, que son (Macdonald 1979, p. 20):
Se debe tener en cuenta que el uso de determinantes hace que la fórmula para tenga signos menos adicionales en comparación con la de , mientras que la situación para la forma desarrollada anterior 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 correspondiente inmanente de esta matriz.
Deducción de las identidades
Cada una de las identidades de Newton puede verificarse fácilmente mediante álgebra elemental; sin embargo, su validez en general necesita una prueba. Aquí hay algunas posibles maneras de demostrar su validez.
Caso especial n = k
Se puede obtener la k-ésima identidad de Newton en k variables por sustitución en
como sigue. Sustituyendo xj por t da
Sumando sobre todas las j se obtiene
donde los términos para i = 0 quedan eliminados de la suma porque p0 (generalmente) 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 deriva de su validez para k variables. Concretamente, las identidades en las n < k variables se pueden deducir poniendo a cero las k − n variables. La identidad k-ésima de Newton en las n > k variables contiene más términos en ambos lados de la ecuación que el de las k variables, pero su la validez estará asegurada si los coeficientes de cualquier monomio coinciden. Dado que ningún monomio individual implica 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 (adecuadamente elegidas) variables.
Comparación de coeficientes en serie
Se puede obtener otra deducción mediante cálculos en el anillo de series formales de potencias R[[t]], donde R es Z[x1,..., x n], el anillo de polinomios en n variables x1,..., xn sobre los enteros.
Partiendo de nuevo de la relación básica
e invirtiendo los polinomios sustituyendo 1/t por t y luego multiplicando ambos lados por tn para eliminar las potencias negativas de t, se obtiene
(el cálculo anterior se debe realizar en el cuerpo de fracciones de R[[t]]; alternativamente, la identidad se puede obtener simplemente evaluando el producto en el lado izquierdo)
Ahora, se intercambian los lados de la ecuación y se expresan los ai como los polinomios simétricos elementales que representan, para obtener la identidad
Calculando las derivadas formales en ambos lados con respecto a t, y luego (por conveniencia) multiplicando por t, se obtiene
donde el polinomio del lado derecho se reescribió primero como función racional para poder factorizar un producto del sumatorio, y luego la fracción en el sumando se desarrolló como una serie en t, usando la fórmula
y finalmente se recogió el coeficiente de cada t j, dando 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 lo suficientemente cerca de 0, para aquellos que se sientan más cómodos con esta interpretación. De hecho, a efectos de las identidades de Newton, solo interesan los coeficientes de la serie. Comparando los coeficientes de tk en ambos lados, se obtiene
lo que da la k-ésima identidad de Newton.
Como una suma telescópica de identidades de funciones simétricas
La siguiente deducción, presentada esencialmente en (Mead, 1992), está formulada en anillo de funciones simétricas para mayor claridad (todas las identidades son independientes del número de variables). Fíjense algunos k > 0, y defínase 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 por k − i distintas otras variables (esta es la función simétrica monomial mγ donde γ es una forma de gancho (i,1,1,...,1)). En particular r(k) = pk; para r(1) la descripción equivaldría a la de ek, pero este caso fue excluido ya que aquí los monomios ya no tienen ninguna variable distinguida. Todos los productos piek−i pueden expresarse en términos de r(j) siendo el primer y último caso algo especial. Entonces, se tiene que
ya que cada producto de términos de la izquierda que involucra distintas variables contribuye a r(i), mientras que aquellos donde la variable de pi ya se encuentra entre las variables del término de ek−i contribuye a r(i + 1), y todos los términos de la derecha se obtienen exactamente una vez. Para i = k se multiplica por e0 = 1, dando trivialmente
Finalmente el producto p1ek−1 por 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 ek, ya que cualquiera de las variables puede provenir del factor p1; de este modo
La identidad k-ésima de Newton ahora se obtiene tomando la suma alterna de estas ecuaciones, en las que todos los términos de la forma r(i) se anulan.
Demostración combinatoria
En (Zeilberger, 1984), se proporciona una breve demostración combinatoria[5] de las identidades de Newton.
Véase también
- Polinomio simétrico suma de potencias
- Polinomio simétrico elemental
- Desigualdades de Newton
- Función simétrica
- Soluciones fluidas, un artículo que da 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
- Delves, L. M. (1967). «A Numerical Method of Locating the Zeros of an Analytic Function». Mathematics of Computation 21 (100): 543-560. JSTOR 2004999. doi:10.2307/2004999.
- Nota: 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 de la DLMF y/o los coeficientes involucrados en las expansiones de la fórmula de Faà di Bruno
- Tignol, Jean-Pierre (2004). Galois' theory of algebraic equations (Reprinted edición). River Edge, NJ: World Scientific. pp. 37–38. ISBN 981-02-4541-6.
- Weisstein, Eric W. «Symmetric Polynomial». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- Zeilberger, Doron (1984). «A Combinatorial Proof of Newton's Identities». Discrete Mathematics 49 (3): 319. doi:10.1016/0012-365X(84)90171-7.
Bibliografía
- Tignol, Jean-Pierre (2001). Galois' theory of algebraic equations. Singapore: World Scientific. ISBN 978-981-02-4541-2.
- Bergeron, F.; Labelle, G.; Leroux, P. (1998). Combinatorial species and tree-like structures. Cambridge: Cambridge University Press. ISBN 978-0-521-57323-8.
- Cameron, Peter J. (1999). Permutation Groups. Cambridge: Cambridge University Press. ISBN 978-0-521-65378-7.
- Cox, David; Little, John; O'Shea, Donal (1992). Ideals, Varieties, and Algorithms. New York: Springer-Verlag. ISBN 978-0-387-97847-5.
- Eppstein, D.; Goodrich, M. T. (2007). «Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters». Algorithms and Data Structures, 10th International Workshop, WADS 2007. Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637-648. Bibcode:2007arXiv0704.3313E. arXiv:0704.3313.
- Littlewood, D. E. (1950). The theory of group characters and matrix representations of groups. Oxford: Oxford University Press. p. viii+310. ISBN 0-8218-4067-3.
- Macdonald, I. G. (1979). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. Oxford: The Clarendon Press, Oxford University Press. p. viii+180. ISBN 0-19-853530-9. MR 553598.
- Macdonald, I. G. (1995). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs (Second edición). New York: Oxford Science Publications. The Clarendon Press, Oxford University Press. p. x+475. ISBN 0-19-853489-2. MR 1354144.
- Mead, D.G. (1992). «Newton's Identities». The American Mathematical Monthly (Mathematical Association of America) 99 (8): 749-751. JSTOR 2324242. doi:10.2307/2324242.
- Stanley, Richard P. (1999). Enumerative Combinatorics, Vol. 2. Cambridge University Press. ISBN 0-521-56069-1. (hardback). (paperback).
- Sturmfels, Bernd (1992). Algorithms in Invariant Theory. New York: Springer-Verlag. ISBN 978-0-387-82445-1.
- Tucker, Alan (1980). Applied Combinatorics (5/e edición). New York: Wiley. ISBN 978-0-471-73507-6.
Enlaces externos
- Newton–Girard formulas on MathWorld
- A Matrix Proof of Newton's Identities in Mathematics Magazine
- Application on the number of real roots
- A Combinatorial Proof of Newton's Identities by Doron Zeilberger