Sean x 1 , ..., x n variables, denote para k ≥ 1 por p k ( x 1 , ..., x n ) la k -ésima suma de potencias :
y para k ≥ 0 denotar por e k ( x 1 , ..., x n ) el polinomio simétrico elemental (es decir, la suma de todos los productos distintos de k variables distintas), entonces
Entonces las identidades de Newton se pueden establecer como
válido para todo n ≥ 1 yn ≥ k ≥ 1.
Además, uno tiene
para todo k > n ≥ 1.
Concretamente, para los primeros valores de k se obtiene :
La forma y 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 n -ésima identidad), lo que permite enunciarlas como identidades en el anillo de funciones simétricas . En ese anillo uno tiene
y así; aquí los lados izquierdos nunca se vuelven cero. Estas ecuaciones permiten expresar de forma recursiva la e i en términos de la p k ; para poder hacer lo inverso, uno puede reescribirlos como
En general, tenemos
válido para todo n ≥ 1 yn ≥ k ≥ 1.
Además, uno tiene
para todo k > n ≥ 1.
Aplicación a las raíces de un polinomio
El polinomio con raíces x i puede expandirse como
donde los coeficientesson los polinomios simétricos definidos anteriormente. Dadas las sumas de poder de las raíces
los coeficientes del polinomio con raíces puede expresarse recursivamente en términos de las sumas de potencia como
Formular polinomios de esta manera es útil al 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ícesson los valores propios de la matriz, contados con su multiplicidad algebraica. Para cualquier entero positivo k , la matriz A k tiene como autovalores las potencias x i k , y cada autovalorde A contribuye su multiplicidad a la del valor propio x i k de A k . Entonces los coeficientes del polinomio característico de A k vienen dados por los polinomios simétricos elementales en esas potencias x i k . En particular, la suma de x i k , que es la k -ésima suma de potencias p k de las raíces del polinomio característico de A , viene dada por su traza :
Las identidades de Newton ahora se relacionan las huellas de las potencias Un k a los coeficientes del polinomio característico de A . Utilizándolos a la inversa para expresar los polinomios simétricos elementales en términos de sumas de potencia, se pueden usar para encontrar el polinomio característico calculando solo las potencias A k y sus trazas.
Este cálculo requiere calcular las trazas de las potencias matriciales A k y resolver un sistema triangular de ecuaciones. Ambos se pueden hacer en la clase de complejidad NC (resolver un sistema triangular se puede hacer dividiendo y conquistando). Por lo tanto, el polinomio característico de una matriz se puede calcular en NC. Según el teorema de Cayley-Hamilton , toda matriz satisface su polinomio característico y una transformación simple permite encontrar la matriz adjunta en NC.
Reorganizar los cálculos en una forma eficiente conduce al algoritmo de Faddeev-LeVerrier (1840), una implementación paralela rápida del mismo 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 la característica 0.
Relación con la teoría de Galois
Para un n dado , los polinomios simétricos elementales e k ( x 1 , ..., x n ) para k = 1, ..., n forman una base algebraica para el espacio de polinomios simétricos en x 1 , .... x n : cada expresión polinomial en x i que es invariante bajo todas las permutaciones de esas variables viene dada por una expresión polinomial en esos polinomios simétricos elementales, y esta expresión es única hasta la equivalencia de expresiones polinomiales. 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ónicocon todos los coeficientes a k considerados como parámetros libres, esto significa que cada expresión polinomial simétrica S ( x 1 , ..., x n ) en sus raíces puede expresarse en cambio como una expresión polinomial P ( a 1 , ..., a n ) sólo en términos de sus coeficientes, es decir, sin necesidad de conocer las raíces. Este hecho también se sigue de consideraciones generales en la teoría de Galois (uno ve a k como elementos de un campo base con raíces en un campo de extensión cuyo grupo de Galois los permuta de acuerdo con el grupo simétrico completo, y el campo fijo bajo todos los elementos de la grupo es el campo base).
Las identidades de Newton también permiten expresar los polinomios simétricos elementales en términos de polinomios simétricos de suma de potencias, mostrando que cualquier polinomio simétrico también se puede expresar en las sumas de potencia. De hecho, las primeras n sumas de potencia 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 deberían distinguirse de las identidades de Newton, están muy relacionadas con ellas.
Una variante que utiliza polinomios simétricos homogéneos completos
Denotando por h k el polinomio simétrico homogéneo completo que es la suma de todos los monomios de grado k , los polinomios de suma de potencia también satisfacen identidades similares a las identidades de Newton, pero sin incluir ningún signo menos. Expresados como identidades de en el anillo de funciones simétricas , leen
válido para todo n ≥ k ≥ 1. Contrariamente a las identidades de Newton, los lados izquierdos no se vuelven cero para k grandes , y los lados derechos contienen cada vez más términos distintos de cero. Para los primeros valores de k , uno tiene
Estas relaciones pueden justificarse mediante un argumento análogo al de la comparación de coeficientes en series de potencia dadas anteriormente, basado en este caso en la identidad de la función generadora.
Las pruebas de las identidades de Newton, como las que se dan a continuación, no pueden adaptarse fácilmente para probar estas variantes de esas identidades.
Expresar polinomios simétricos elementales en términos de sumas de potencia
Como se mencionó, las identidades de Newton se pueden usar para expresar de manera recursiva polinomios simétricos elementales en términos de sumas de potencia. Hacerlo requiere la introducción de denominadores enteros, por 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 B n es el polinomio de Bell exponencial completo . Esta expresión también conduce a la siguiente identidad para generar funciones:
Aplicadas a un polinomio monico, estas fórmulas expresan los coeficientes en términos de las sumas de potencia de las raíces: reemplace 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 potencia
Las relaciones análogas que involucran polinomios simétricos homogéneos completos se pueden desarrollar de manera similar, dando ecuaciones
y así sucesivamente, en los que solo hay signos más. En términos del polinomio de Bell completo,
Estas expresiones corresponden exactamente a los polinomios de índice de ciclo de los grupos simétricos , si se interpretan las sumas de potencia p i como indeterminadas: el coeficiente en la expresión para h k de cualquier monomio p 1 m 1 p 2 m 2 ... p l m l es igual a la fracción de todas las permutaciones de k que tienen m 1 puntos fijos, m 2 ciclos de longitud 2, ..., y m l ciclos de longitud l . Explícitamente, este coeficiente se puede escribir como dónde ; este N es el número de permutaciones que conmuta 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, sino un signo igual a la señal de π , es decir, (-1) m 2 + m 4 + ... .
Se puede demostrar considerando el siguiente paso inductivo:
Expresar sumas de potencia en términos de polinomios simétricos elementales
También se pueden usar las identidades de Newton para expresar sumas de potencia en términos de polinomios simétricos, lo que no introduce denominadores:
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 enteros no negativos m ) es:
La fórmula de suma múltiple anterior se puede probar considerando el siguiente paso inductivo:
Expresar sumas de potencia 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 potencia en términos de ellas:
y así. Aparte de la sustitución de cada e i por su 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 únicamente del número de factores presentes: el signo del monomioes - (- 1) m 1 + m 2 + m 3 + ... . En particular, la descripción anterior del valor absoluto de los coeficientes se aplica aquí también.
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 las funciones simétricas elementales son conocidas y las sumas de potencias desconocidas (o viceversa) y aplique la regla de Cramer para encontrar la solución para la incógnita final. Por ejemplo, tomando las identidades de Newton en la forma
consideramos y como incógnitas, y resolver la última, dando
Resolviendo para en lugar de para es 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 desordenados que los resultados finales, que son (Macdonald 1979, p. 20):
Tenga en cuenta que el uso de determinantes hace que la fórmula para tiene signos negativos adicionales en comparación con el de , mientras que la situación para la forma expandida dada anteriormente es opuesta. Como se observa en (Littlewood 1950, p. 84) se puede obtener alternativamente la fórmula paratomando el permanente de la matriz paraen lugar del determinante, y más generalmente se puede obtener una expresión para cualquier polinomio de Schur tomando el correspondiente inmanante de esta matriz.
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 necesita una prueba. A continuación, se muestran algunas posibles derivaciones.
Del caso especial n = k
Se puede obtener la k -ésima identidad de Newton en k variables mediante sustitución en
como sigue. Sustituyendo x j por t da
Sumando todo j da
donde los términos para i = 0 se tomaron de la suma porque p 0 (generalmente) no está definido. Esta ecuación da inmediatamente la k -ésima identidad de Newton en k variables. Dado que se trata de 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 n < k variables se pueden deducir estableciendo k - n variables en 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 aquella que surge en la k -ésima identidad de Newton en k variables (adecuadamente elegidas).
Comparación de coeficientes en serie
Otra derivación se puede obtener mediante cálculos en el anillo de la serie de potencias formales R [[ t ]], donde R es Z [ x 1 , ..., x n ], el anillo de polinomios en n variables x 1 , ... , x n sobre los enteros.
Comenzando de nuevo desde la relación básica
y "invertir los polinomios" sustituyendo 1 / t por t y luego multiplicando ambos lados por t n para eliminar las potencias negativas de t , da
(el cálculo anterior debe realizarse en el campo de las fracciones de R [[ t ]]; alternativamente, la identidad se puede obtener simplemente evaluando el producto en el lado izquierdo)
Intercambiar lados y expresar el a i como los polinomios simétricos elementales que representan da la identidad
Uno diferencia formalmente ambos lados con respecto a t , y luego (por conveniencia) se multiplica por t , para obtener
donde el polinomio en el 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 , 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 formales, pero alternativamente puede pensarse como una expansión en serie para t lo suficientemente cerca de 0, para aquellos que se sientan más cómodos con eso; de hecho, uno no está interesado en la función aquí, sino solo en la coeficientes de la serie.) Al comparar los coeficientes de t k en ambos lados se obtiene
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 algunos 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 (esto 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 fue excluido ya que aquí los monomios ya no tienen ninguna variable distinguida. Todos los productos p i e k - i pueden expresarse en términos de r ( j ), siendo el primer y último caso algo especial. Uno tiene
dado que cada producto de los términos de la izquierda que involucran variables distintas contribuye a r ( i ), mientras que aquellos en los que la variable de p i ya ocurre entre las variables del término de e k - i contribuye a r ( i + 1), y todos los términos de la derecha se obtienen así exactamente una vez. Para i = k uno se multiplica por e 0 = 1, dando trivialmente
Finalmente, el producto p 1 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 cualquier una de las variables puede provenir del factor p 1 ; por lo tanto
La k -ésima identidad de Newton se obtiene ahora tomando la suma alterna de estas ecuaciones, en la que todos los términos de la forma r ( i ) se cancelan.
Prueba combinatoria
Se da una breve prueba combinatoria de las identidades de Newton en (Zeilberger, 1984) [5]
Ver también
Polinomio simétrico de suma de potencias
Polinomio simétrico elemental
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, LM (1967). "Un método numérico de 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 .
^ Nb, los coeficientes de los términos del producto ponderado en la suma dada por la identidad anterior están relacionados con losnú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
^Tignol, Jean-Pierre (2004). Teoría de ecuaciones algebraicas de Galois (ed. Reimpresa). River Edge, Nueva Jersey: World Scientific. págs. 37 –38. ISBN 981-02-4541-6.
^Weisstein, Eric W. "Polinomio simétrico" . MathWorld .
^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). Teoría de 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 de espacio eficiente en flujos de datos de ida y vuelta a través de identidades de Newton y filtros Bloom invertibles". Algoritmos y estructuras de datos, décimo taller internacional, 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 personajes grupales y representaciones matriciales de grupos . Oxford: Prensa de la Universidad de Oxford. viii + 310. ISBN 0-8218-4067-3.
Macdonald, IG (1979). Funciones simétricas y polinomios de Hall . Monografías matemáticas de Oxford. Oxford: The Clarendon Press, Oxford University Press. viii + 180. ISBN 0-19-853530-9. Señor 0553598 .
Macdonald, IG (1995). Funciones simétricas y polinomios de Hall . Monografías de matemáticas de Oxford (segunda ed.). Nueva York: Publicaciones científicas de Oxford. The Clarendon Press, Oxford University Press. pag. x + 475. ISBN 0-19-853489-2. Señor 1354144 .
Mead, DG (1992). "Identidades de Newton". The American Mathematical Monthly . Asociación Matemática de América. 99 (8): 749–751. doi : 10.2307 / 2324242 . JSTOR 2324242 .
Stanley, Richard P. (1999). Combinatoria enumerativa, vol. 2 . Prensa de la Universidad de Cambridge. 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 (5 / e ed.). 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