Identidades de Newton

En matemáticas, as identidades de Newton, tamén coñecidas como fórmulas de Girard-Newton, dan relacións entre dous tipos de polinomio simétricos, a saber, entre sumas de potencias e polinomios simétrico elemental.

Avaliados nas raíces dun polinomio mónico P nunha variábel, permiten expresar as sumas da k-ésima potencia de todas as raíces de P (contadas coa súa multiplicidade) en termos dos coeficientes de P, sen ter que atopar os coeficientes concretos.

Estas identidades foron atopadas por Isaac Newton ao redor de 1666, aparentemente descoñecendo os traballos anteriores (1629) de Albert Girard. Teñen aplicacións en moitas áreas das matemáticas, incluíndo a teoría de Galois, a teoría invariante, a teoría de grupos, a combinatoria, así como outras aplicacións fóra das matemáticas, incluíndo a relatividade xeral.

Enunciado matemático

Formulación en termos de polinomios simétricos

Sexan x₁, ..., x_n variábeis, denotamos para k≥1 como p_k(x₁, ..., x_n) a suma das potencias k-ésimas:

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

e para k≥0 denótase como e_k(x₁, ..., x_n) o polinomio simétrico elemental (é dicir, a suma dos produtos distintos de k distintas variábeis)

{\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}}

Entón as identidades de Newton pódense enunciar como

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 os $n \geq k \geq 1$ .

A maiores, temos

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 todos os $k > n \geq 1$ .

Concretamente, obtense para os primeiros valores de k:

{\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}}

A forma e a validez destas ecuacións non dependen do número n de variábeis, o que permite declaralas como identidades no anel de funcións simétricas. Nese anel temos

{\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}}

e así para os seguintes; aquí os lados esquerdos nunca se converten en cero. Estas ecuacións permiten expresar recursivamente os e_i en termos dos p_k.

Podemos reescribir a relación inversa como

{\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 xeral, temos

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 todos os n ≥k ≥ 1.

Alén diso, temos

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 todos os k > n ≥ 1.

Aplicación ás raíces dun polinomio

O polinomio con raíces x_i pódese expandir como

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

onde os coeficientes $e_{k}(x_{1},\ldots ,x_{n})$ son os polinomios simétricos definidos anteriormente. Dadas as sumas de potencias das raíces

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

os coeficientes do polinomio con raíces $x_{1},\ldots ,x_{n}$ pódense expresar recursivamente en termos de sumas de potencias como

{\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 deste xeito é útil para usar o método de Delves e Lyness^[1] para atopar os ceros dunha función analítica.

Aplicación ao polinomio característico dunha matriz

Cando o polinomio anterior é o polinomio característico dunha matriz $\mathbf {A}$ (en particular cando $\mathbf {A}$ é a matriz compañeira do polinomio), as raíces son os eigenvalores da matriz, contados coa súa multiplicidade alxébrica.

Para calquera número enteiro positivo $k$ , a matriz $\mathbf {A} ^{k}$ ten como eigenvalores as potencias $x_{i}^{k}$ , e cada eigenvalor $x_{i}$ de $\mathbf {A}$ contribúe coa súa multiplicidade para os autovalores $x_{i}^{k}$ de $\mathbf {A} ^{k}$ . Entón, os coeficientes do polinomio característico de $\mathbf {A} ^{k}$ veñen dados polos polinomios simétricos elementais nesas potencias $x_{i}^{k}$ .

En particular, a suma dos $x_{i}^{k}$ , que son a suma das $k$ -ésimas potencias $p_{k}$ das raíces do polinomio característico de $\mathbf {A}$ , vén dada pola súa traza:

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

As identidades de Newton agora relacionan as trazas das potencias $\mathbf {A} ^{k}$ cos coeficientes do polinomio característico de $\mathbf {A}$ . Usándoos á inversa para expresar os polinomios simétricos elementais en termos de sumas de potencias, pódense usar para atopar o polinomio característico calculando só as potencias $\mathbf {A} ^{k}$ e as súas trazas.

A reorganización dos cálculos nunha forma eficiente leva ao Algoritmo de Faddeev-LeVerrier (1840), unha rápida implementación paralela do mesmo débese a L. Csanky (1976). A súa desvantaxe é que require división por números enteiros, polo que en xeral o corpo debería ter a característica 0.

Relación coa teoría de Galois

Para un n dado, os polinomios simétricos elementais e_k(x₁,...,x_n) para k=1,..., n forman unha base alxébrica para o espazo de polinomios simétricos en x₁,.... x_n: toda expresión polinómica nas x_i que é invariante en todas as permutacións desas variábeis vén dada por unha expresión polinomial neses polinomios elementais simétricos, e esta expresión é única ata equivalencia de expresións polinómicas.

Este é un feito xeral coñecido como teorema fundamental dos polinomios simétricos, e as identidades de Newton proporcionan fórmulas explícitas no caso dos polinomios simétricos de suma de potencias.

Aplicado ao polinomio mónico ${\textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{n-k}}$ con todos os coeficientes a_k considerados como parámetros libres, isto significa que toda expresión polinómica simétrica S(x₁,...,x_k) pode expresarse en lugar da súa raíz polinómica como a súa expresión polinómica P(a₁,...,a_n) só en termos dos seus coeficientes, é dicir, sen esixir o coñecemento das raíces.

Este feito tamén se desprende das consideracións xerais da teoría de Galois (vemos os a_k como elementos dun corpo base con raíces nunha extensión de corpo cuxo grupo de Galois as permuta segundo o grupo simétrico completo, e o corpo fixado baixo todos os elementos do grupo de Galois é o corpo base).

As identidades de Newton tamén permiten expresar os polinomios simétricos elementais en termos de polinomios simétricos de suma de potencias, mostrando que calquera polinomio simétrico tamén se pode expresar nas sumas de potencias. De feito, as primeiras n sumas de potencias tamén forman unha base alxébrica para o espazo de polinomios simétricos.

Identidades relacionadas

Hai unha serie de (familias de) identidades que, aínda que deberían distinguirse das identidades de Newton, están moi relacionadas con elas.

Unha variante que utiliza polinomios simétricos homoxéneos completos

Denotando por h_k o polinomio simétrico homoxéneo completo (é dicir, a suma de todos os monomios de grao k), os polinomios de suma de potencias tamén satisfán identidades semellantes ás identidades de Newton, mais non implican ningún signo menos. Expresados como identidades no anel de funcións simétricas, pódense escribir como

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

válido para todos os n ≥ k ≥ 1. Ao contrario das identidades de Newton, os lados esquerdos non se converten en cero para grandes k, e os lados da dereita conteñen cada vez máis termos distintos de cero. Para os primeiros valores de k, temos

{\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 relacións poden xustificarse mediante un argumento análogo ao de comparanr os coeficientes en series de potencias dados anteriormente, baseados neste caso na identidade da función xeradora.

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

As probas das identidades de Newton, como as que se dan a continuación, non se poden adaptar facilmente para probar estas variantes desas identidades.

Expresar polinomios simétricos elementais en termos de sumas de potencias

Como xa se mencionou, temos:

{\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}}

.^[2] A fórmula xeral pódese expresar convenientemente como

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

onde o B_n é o polinomio de Bell exponencial completo. Esta expresión tamén leva á seguinte identidade e funcións xeradoras:

\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 os coeficientes en termos das sumas de potencias das raíces: substitúa cada e_i por a_i e cada p_k por s_k.

Expresar polinomios simétricos homoxéneos completos en termos de sumas de potencias

As relacións análogas que implican polinomios simétricos homoxéneos completos poden desenvolverse de forma similar, dando as ecuacións

{\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}},

nos que só hai signos máis. En termos do polinomio completo de Bell,

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

Estas expresións corresponden exactamente aos polinomios de índice de ciclo dos grupo simétricos, se se interpretan as sumas de potencias p_i como indeterminadas: o coeficiente na expresión para h_k de calquera monomio p₁^m₁p₂^m₂...p_l^m_l é igual á fracción de todas as permutacións de k que teñen m₁ puntos fixos, m₂ ciclos de lonxitude 2, ... e m_l ciclos de lonxitude l.

Explicitamente, estes coeficientes pódense escribir como $1/N$ onde ${\textstyle N=\prod _{i=1}^{l}(m_{i}!\,i^{m_{i}})}$ ; esta N é o número de permutacións que conmutan con calquera permutación $π$ do tipo de ciclo dado. As expresións das funcións simétricas elementais teñen coeficientes co mesmo valor absoluto, pero un signo igual ao signo da permutación $π$ , é dicir, (−1)^{m₂+m₄+...}.

Pódese probar considerando o seguinte paso indutivo:

{\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 analoxía coa derivación da función xeradora dos $e_{n}$ , tamén podemos obter a función xeradora dos $h_{n}$ , en termos das sumas de potencias, como:

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

Esta función xeradora é polo tanto a exponencial pletistica (operación definida por Littlewood^[3]) de $p_{1}t=(x_{1}+\cdots +x_{n})t$ .

Expresar sumas de potencia en termos de polinomios simétricos elementais

Tamén se pode usar as identidades de Newton para expresar sumas de potencias en termos de polinomios simétricos elementais, que non introducen denominadores:

{\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}}

As catro primeiras fórmulas foron obtidas por Albert Girard en 1629 (polo tanto, antes de Newton).^[4]

A fórmula xeral (para todos os enteiros positivos m) é:

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}}.

Isto pódese enunciar convenientemente en termos dos polinomios de Bell ordinarios como

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

ou de xeito equivalente como a función xeradora:^[5]

{\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 é análogo á función xeradora exponencial do polinomio de Bell dada na subsección anterior subsección anterior.

Expresar sumas de potencia en termos de polinomios simétricos homoxéneos completos

Finalmente pódese usar as identidades variantes que implican polinomios simétricos homoxéneos completos de xeito similar para expresar as sumas de potencia en termos deles:

{\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}}

e así por diante. Ademais da substitución de cada e_i pola correspondente h_i, o único cambio con respecto á anterior familia de identidades está nos signos dos termos, que neste caso dependen só do número de factores presentes: o signo do monomio ${\textstyle \prod _{i=1}^{l}h_{i}^{m_{i}}}$ é −(−1)^{m₁+m₂+m₃+...}. En particular, a descrición anterior do valor absoluto dos coeficientes tamén se aplica aquí.

A fórmula xeral (para todos os enteiros non negativos m) é:

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}}

Expresións como determinantes

Pódense obter fórmulas explicitas para as expresións anteriores en forma de determinantes, considerando as primeiras n das identidades de Newton (ou as súas contrapartes para os polinomios homoxéneos completos) como ecuacións lineares nas que se coñecen as funcións simétricas elementais e as sumas de potencias son descoñecidas (ou viceversa) e aplicando a regra de Cramer. Por exemplo, tomando as identidades de Newton na forma

{\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 $p_{1},-p_{2},p_{3},\ldots ,(-1)^{n}p_{n-1}$ e $p_{n}$ como incógnitas, e resolvemos a última, dando

{\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 $e_{n}$ en lugar de para $p_{n}$ é semellante (Macdonald 1979, p. 20):

{\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}}

Dedución das identidades

Cada unha das identidades de Newton pódese comprobar facilmente mediante álxebra elemental; porén, a súa validez en xeral precisa dunha proba. Aquí temos algunhas posíbeis deducións.

Do caso especial n =k

Pódese obter a k-ésima identidade de Newton en k variábeis por substitución en

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

do seguinte xeito. Substituíndo x_j por t dáse

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

Suma sobre todas as j das

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}),

onde os termos para i = 0 foron eliminados da suma porque p₀ non está (normalmente) definido. Esta ecuación dá inmediatamente a k-ésima identidade de Newton en k variábeis.

Comparando coeficientes das series

Pódese obter outra demostración mediante cálculos no anel de series formais de potencias R[[t]], onde R é Z[x₁,..., x_n], o anel de polinomios en 'n variábeis x₁,..., xn sobre os enteiros.

Partindo de novo da relación básica

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

e "invertindo os polinomios" substituíndo 1/t por t e despois multiplicando ambos os dous lados por tⁿ para eliminar as potencias negativas de t, dá

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

(o cálculo anterior debería realizarse no corpo de fraccións de R[[t]]; alternativamente, a identidade pódese obter simplemente avaliando o produto no lado esquerdo).

Trocando os lados e expresando os a_i como os polinomios simétricos elementais que representan dá a identidade

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

Derivando formalmente ambos os dous lados en relación a t, e despois (por conveniencia) multiplica por t, para obter

{\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}}

onde o polinomio do lado dereito foi reescrito primeiro como unha función racional para poder factorizar un produto da suma, entón a fracción do sumando desenvolveuse como unha serie en t, usando a fórmula

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

e finalmente recolleuse o coeficiente de cada t ^j, dando unha suma de potencias. (A serie en t é unha serie de potencias formal, masi pode considerarse alternativamente como unha expansión en serie para t o suficientemente próxima a 0, tendo en conta que só nos interesan os coeficientes da serie).

(-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}),

que dá a k-ésima identidade de Newton.

Demostración combinatoria

Doron Zeilberger deu unha breve proba combinatoria das identidades de Newton en 1984.^[6]

Notas

↑ 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.
↑ coeficientes relacionados con DLMF e Fórmula de Faa di Bruno
↑ Littlewood (1936, p. 52, 1944, p. 329)
↑ Tignol, Jean-Pierre (2004). Galois' theory of algebraic equations (Reprinted ed.). River Edge, NJ: World Scientific. pp. 37–38. ISBN 981-02-4541-6.
↑ Weisstein, Eric W. "Symmetric Polynomial". MathWorld.
↑ 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". Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637–648. arXiv:0704.3313.
Littlewood, D. E. (1950). The theory of group characters and matrix representations of groups. Oxford: Oxford University Press. 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. viii+180. ISBN 0-19-853530-9. MR 553598.
Macdonald, I. G. (1995). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs (Second ed.). 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 ed.). New York: Wiley. ISBN 978-0-471-73507-6.

Outros artigos

Ligazóns externas

Fórmulas de Newton–Girard en MathWorld
A Matrix Proof of Newton's Identities na revista Mathematics
Aplicación sobre o número de raíces reais
Unha proba combinatoria das identidades de Newton de Doron Zeilberger

[Delves_Lyness_1967-1] 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.

[2] tes relacionados con DLMF e Fórmula de Faa di Bruno

[3] Littlewood (1936, p. 52, 1944, p. 329)

[4] Tignol, Jean-Pierre (2004). Galois' theory of algebraic equations (Reprinted ed.). River Edge, NJ: World Scientific. pp. 37–38. ISBN 981-02-4541-6.

[5] Weisstein, Eric W. "Symmetric Polynomial". MathWorld.

[Zeilberger_1984-6] Zeilberger, Doron (1984). "A Combinatorial Proof of Newton's Identities". Discrete Mathematics 49 (3): 319. doi:10.1016/0012-365X(84)90171-7.

[1]

[2]

[3]

[4]

[5]

[6]