Identités de Newton

En mathématiques, et plus particulièrement en algèbre, les identités de Newton (connues également sous le nom de formules de Newton-Girard) sont des relations entre deux types de polynômes symétriques, les polynômes symétriques élémentaires, et les sommes de Newton, c'est-à-dire les sommes de puissances des indéterminées. Évaluées aux racines d'un polynôme P à une variable, ces identités permettent d'exprimer les sommes des k-ièmes puissances de toutes les racines de P (comptées avec leur multiplicité) en fonction des coefficients de P, sans qu'il soit nécessaire de déterminer ces racines. Ces formules furent redécouvertes par Isaac Newton vers 1666, apparemment sans avoir eu connaissance du travail analogue d'Albert Girard en 1629. Elles ont des applications dans de nombreux domaines mathématiques, tels que la théorie de Galois, la théorie des invariants, la théorie des groupes, la combinatoire, et même dans des domaines non mathématiques, comme en relativité générale.

Formulation en fonction des polynômes symétriques

Soient $x 1,..., x n$ des variables ; pour tout entier naturel k non nul, on note $p k (x 1,..., x n)$ la somme des puissances $k$ -ièmes :

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

(appelée somme de Newton)

et pour $k \geq 0$ , on note $e k (x 1,..., x n)$ le polynôme symétrique élémentaire qui est la somme des produits distincts de k variables distinctes parmi les n ; ainsi en particulier

{\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})&=\textstyle \sum \limits _{1\leq i<j\leq n}x_{i}x_{j},\\...\\e_{n}(x_{1},\ldots ,x_{n})&=x_{1}x_{2}\cdots x_{n},\\e_{k}(x_{1},\ldots ,x_{n})&=0,\quad {\text{pour}}\ k>n.\\\end{aligned}}

Les identités de Newton s'écrivent alors :

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

relations vraies pour tout $k\in \mathbb {N} ^{*}$ . On obtient ainsi pour les premières valeurs 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}}

La forme de ces relations ne dépend pas du nombre n de variables (mais le membre de gauche devient nul après la n-ième identité), ce qui permet de les énoncer comme des identités dans l'anneau des polynômes symétriques. Dans cet anneau, on a :

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

et ainsi de suite ; dans ce cas, le membre de gauche ne s'annule jamais.

Ces équations permettent d'exprimer par récurrence les $e i$ en fonction des $p k$ ; inversement, les réécrivant sous la forme :

{\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}p_{1}-2e_{2},\\p_{3}&=e_{1}p_{2}-e_{2}p_{1}+3e_{3},\\p_{4}&=e_{1}p_{3}-e_{2}p_{2}+e_{3}p_{1}-4e_{4},\quad {\text{etc.}}\\\end{aligned}}

on peut exprimer les p_i en fonction des e_k.

Application aux racines d'un polynôme

Les $x i$ étant pris comme paramètres et non comme variables, considérons le polynôme unitaire en $t$ ayant pour racines $x 1,..., x n$ :

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

où les coefficients $a k$ sont donnés par les polynômes symétriques élémentaires des racines : $a k = e k (x 1,\dots, x n)$ . Les sommes des puissances des racines (qu'on appelle encore des sommes de Newton), $s_{k}=p_{k}(x_{1},\ldots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k},$ peuvent alors être exprimées en fonction des coefficients du polynôme en appliquant les identités de Newton de proche en proche :

{\begin{aligned}s_{1}&=a_{1},\\s_{2}&=a_{1}s_{1}-2a_{2},\\s_{3}&=a_{1}s_{2}-a_{2}s_{1}+3a_{3},\\s_{4}&=a_{1}s_{3}-a_{2}s_{2}+a_{3}s_{1}-4a_{4},\quad {\text{etc.}}\\\end{aligned}}

Application au polynôme caractéristique d'une matrice

Lorsque le polynôme du paragraphe précédent est le polynôme caractéristique d'une matrice A, les racines $x i$ sont les valeurs propres de A (comptées avec leur multiplicité algébrique). Pour tout entier k, la matrice A^k a pour valeurs propres les $x k i$ (avec les multiplicités correspondantes). Les coefficients du polynôme caractéristique de A^k sont alors donnés par les polynômes symétriques élémentaires en ces puissances $x k i$ . En particulier, la somme des $x k i$ est donnée par la trace de A^k : $s k = tr(A k)$ .

Les identités de Newton relient donc les traces des A^k aux coefficients du polynôme caractéristique de A. Réciproquement, les utilisant pour calculer les polynômes symétriques élémentaires à partir des sommes de puissances, elles permettent donc de déterminer le polynôme caractéristique de A en calculant uniquement les puissances de A et leurs traces, puis en résolvant un système triangulaire d'équations. Le théorème de Cayley-Hamilton permet ensuite d'en déduire simplement la matrice inverse de A.

L'ensemble de ces calculs (réécrits sous une forme efficace) constitue l'algorithme de Faddeev-Leverrier, datant de 1840 ; une implémentation parallèle rapide de cet algorithme est due à Lazslo Csanky^[1], en 1976. Il demande cependant des divisions (par des entiers), et n'est donc utilisable en général que dans des corps de caractéristique 0. L'implémentation de Csanky montre que ces différents calculs sont (dans ce cas) dans la classe de complexité NC.

Relation à la théorie de Galois

Pour un n donné, les polynômes symétriques élémentaires $e k (x 1, \dots, x n)$ pour k = 1, …, n forment une « base algébrique » de l'algèbre commutative des polynômes symétriques en $x 1,..., x n$ , c'est-à-dire que tout polynôme symétrique s'exprime en fonction polynomiale de ces polynômes symétriques élémentaires, et que cette expression est unique. Ce résultat général, connu sous le nom de théorème fondamental des polynômes symétriques, peut s'expliciter (à l'aide des identités de Newton) dans le cas des sommes de Newton. Ainsi, appliqué au polynôme unitaire $\textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{n-k}$ dont les coefficients $a k$ sont considérés comme des paramètres, cela signifie que toute fonction polynomiale $S (x 1, \dots, x n)$ de ses racines peut s'écrire comme fonction polynomiale $P (a 1, \dots, a n)$ de ses coefficients seuls, c'est-à-dire sans qu'il soit nécessaire de calculer ces racines. Cela peut également se déduire de la théorie de Galois, en voyant les $a k$ comme éléments d'un corps de base ; les racines sont alors dans une extension de ce corps, et le groupe de Galois de cette extension les permute suivant le groupe symétrique entier ; le corps invariant par tous les éléments de ce groupe de Galois est le corps de base.

Réciproquement, les identités de Newton permettent d'exprimer les polynômes symétriques élémentaires en fonction des sommes de Newton, et de démontrer que ces sommes forment également une « base algébrique » de l'algèbre commutative des polynômes symétriques.

Chaque identité peut être vérifiée directement par un simple calcul algébrique, mais le cas général demande une démonstration. Voici quelques pistes possibles :

À partir du cas particulier n = k

La k-ième identité de Newton en k variables s'obtient par substitution dans la formule définissant les $e k$ :

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

Substituant x_j à t, on a :

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

Sommant sur l'ensemble des j, on obtient :

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

(Les termes en i = 0 sont séparés de la somme parce que p₀ n'est en général pas défini.)

Cette équation donne immédiatement l'identité cherchée. Les identités correspondant à n < k variables s'en déduisent en annulant les k − n variables restantes ; le cas où n > k se traite en remarquant que chaque monôme ne contient pas plus de k variables, et que ce monôme ne change pas si on annule les n − k autres variables ; il suffit alors d'utiliser l'identité de Newton correspondant à ces k variables.

Par identification de séries formelles

On peut également obtenir les identités de Newton à l'aide de manipulations formelles basées sur l'identité

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

reliant les racines et les coefficients d'un polynôme unitaire. Pour faciliter les calculs, on commence par substituer 1/t à t, et on multiplie les deux membres par tⁿ, obtenant :

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

Remplaçant les a_i par les polynômes symétriques, on obtient l'identité

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

Après différentiation par rapport à t, et multiplication par t, il vient :

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

où le polynôme de droite a d'abord été réécrit comme une fonction rationnelle, puis celle-ci développée en série formelle en t, et les coefficients de chaque t ^j regroupés pour obtenir une somme de puissances (la convergence de la série est en fait assurée pour t assez proche de zéro, mais comme on ne s'intéresse qu'aux coefficients des t ^j, cette question de convergence n'a pas d'importance réelle). Comparant les coefficients de t^k des deux membres, on obtient

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

,

ce qui est la k-ième identité de Newton.

Comme somme télescopique d'identités

La dérivation suivante^[2] est formulée dans l'anneau des polynômes symétriques, car alors les identités ne dépendent pas du nombre de variables. Pour un k > 0 fixé, on définit (pour 2 ≤ i ≤ k) la fonction symétrique r(i) comme la somme des monômes distincts de degré k obtenus en multipliant une variable élevée à la puissance i par k − i autres variables distinctes. En particulier, r(k) = p_k ; le cas r(1) est exclu car les monômes n'auraient plus de variable jouant un rôle spécial. Tous les produits p_ie_k−i peuvent être exprimés en fonction des r(j) (les cas extrêmes i=1 et i=k mis à part). On obtient $p_{i}e_{k-i}=r(i)+r(i+1)\quad {\text{pour }}1<i<k$ , puisque chaque produit des termes de gauche mettant en jeu des variables distinctes contribue à r(i), alors que ceux où les variables de p_i figurent déjà parmi les variables du terme correspondant de e_k−i contribuent à r(i + 1), et que tous les termes de droite sont ainsi obtenus une fois et une seule. Pour i = k, en multipliant par e₀ = 1, on obtient trivialement $p_{k}e_{0}=p_{k}=r(k)\,$ . Enfin le produit p₁e_k−1 (correspondant à i = 1) apporte des contributions à r(i + 1) = r(2) comme pour les autres valeurs de i < k, mais les contributions restantes sont égales à k fois chaque monôme de e_k, puisque chacune des variables peut provenir du facteur p₁ ; ainsi $p_{1}e_{k-1}=ke_{k}+r(2)$ .

La k-ième identité de Newton est alors obtenue en prenant la somme alternée de ces équations, laquelle est une somme télescopique : tous les termes de la forme r(i) disparaissent.

De nombreuses familles d'identités analogues et étroitement reliées aux identités de Newton existent.

Utilisation des polynômes symétriques complètement homogènes

Notant h_k le polynôme symétrique complètement homogène (en), c'est-à-dire la somme de tous les monômes de degré k, les sommes de puissances satisfont des identités semblables à celles de Newton, mais dont les termes sont tous positifs. Dans l'anneau des polynômes symétriques, elles s'écrivent $kh_{k}=\sum _{i=1}^{k}h_{k-i}p_{i},$ , pour tout k ≥ 1. Contrairement aux identités de Newton, le membre de gauche ne s'annule pas pour k assez grand, et le nombre de termes non nuls des membres de droite grandit indéfiniment. Pour les premières valeurs de k, on a

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

Ces relations peuvent se démontrer par un argument analogue à celui donné plus haut utilisant des séries formelles, mais en utilisant l'identité entre fonctions génératrices :

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

.

En revanche, les autres démonstrations données précédemment ne peuvent s'adapter aisément à ces nouvelles identités.

Expression des polynômes symétriques élémentaires en fonction de sommes de Newton

Comme on l'a dit, les identités de Newton permettent d'exprimer par récurrence les polynômes symétriques élémentaires en fonction de sommes de Newton. Cela demande des divisions par des entiers, et ne peut donc être fait que dans l'anneau Λ_Q des polynômes symétriques à coefficients rationnels :

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

et ainsi de suite. Pour un polynôme unitaire, ces formules expriment les coefficients en fonction des sommes de puissances des racines, en remplaçant chaque e_i par a_i et chaque p_k par s_k.

Expression des polynômes symétriques complètement homogènes en fonction de sommes de Newton

Les relations analogues concernant les polynômes symétriques complètement homogènes se développent de même, amenant aux équations :

{\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}),{\text{ etc.}}\\\end{aligned}}

où tous les termes sont positifs. Ces expressions correspondent exactement aux indicateurs de cycles des polynômes des groupes symétriques, en interprétant les sommes de Newton p_i comme des indéterminées : le coefficient d'un monôme p₁^m₁p₂^m₂…p_l^m_l dans l'expression de h_k est égal à la proportion de toutes les permutations de k ayant m₁ points fixes, m₂ cycles de longueur 2, …, et m_l cycles de longueur l. Plus précisément, ce coefficient peut s'écrire $1/ N$ , avec ${\textstyle N=\Pi _{i=1}^{l}(m_{i}!\,i^{m_{i}})}$ ; N est le nombre de permutations avec une permutation fixée π ayant le type de cycle correspondant. Les expressions correspondant aux fonctions symétriques élémentaires ont des coefficients ayant les mêmes valeurs absolues, mais un signe égal à la signature de π, c'est-à-dire à (−1)^{m₂+m₄+…}.

Expression des sommes de Newton

Inversement, on peut exprimer les sommes de Newton en fonction des polynômes symétriques élémentaires, et ces expressions ont des coefficients entiers :

{\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_{2}^{2}e_{1}+5e_{3}e_{1}^{2}-5e_{3}e_{2}-5e_{4}e_{1}+5e_{5},\\p_{6}&=e_{1}^{6}-6e_{2}e_{1}^{4}+9e_{2}^{2}e_{1}^{2}+6e_{3}e_{1}^{3}-2e_{2}^{3}-12e_{3}e_{2}e_{1}-6e_{4}e_{1}^{2}+3e_{3}^{2}+6e_{4}e_{2}+6e_{1}e_{5}-6e_{6},{\text{ etc.}}\\\end{aligned}}

mais ces expressions ne semblent pas suivre de règle explicite. On voit cependant que le coefficient d'un monôme $M=\Pi _{i=1}^{l}e_{i}^{m_{i}}$ dans l'expression de $p k$ a le même signe que le coefficient du produit correspondant $\Pi _{i=1}^{l}p_{i}^{m_{i}}$ dans l'expression de $e k$ donnée plus haut, c'est-à-dire (−1)^{m₂+m₄+…}. De plus, la valeur absolue du coefficient de M est la somme, prise sur l'ensemble des suites de polynômes symétrique élémentaires dont le produit est M, de l'indice du dernier polynôme de chaque suite : ainsi, le coefficient de $e 15 e 3 e 43$ dans l'expression donnant p₂₀ est $(-1)^{0+3}(280\times 1+56\times 3+168\times 4)=-1120$ , puisque parmi les ordres distincts de cinq facteurs e₁, un facteur e₃ et trois facteurs e₄, il y en a 280 se terminant par e₁, 56 se terminant par e₃, et 168 se terminant par e₄.

Enfin, les identités concernant les polynômes complètement homogènes peuvent de même être inversées, amenant à :

{\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},{\text{ etc.}}\\\end{aligned}}

Ces identités ont exactement la même forme que les précédentes, au signe près : le signe du monôme $\Pi _{i=1}^{l}h_{i}^{m_{i}}$ est à présent −(−1)^{m₁+m₂+m₃+…}.

Expressions sous forme de déterminants

Les expressions précédentes correspondant à la résolution de systèmes d'équations linéaires, elles peuvent se formuler explicitement à l'aide de déterminants, en utilisant la règle de Cramer. Par exemple, écrivant les identités de Newton sous la forme :

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

et en prenant $p_{1}$ , ${-p_{2}}$ , $p_{3}$ , …, $(-1)^{n}p_{n-1}$ et $p_{n}$ comme inconnues, on obtient pour cette dernière :

p_{n}={\frac {\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)^{n-1}\end{vmatrix}}}={\frac {1}{(-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}}={\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}}.

Les calculs sont analogues (mais un peu plus compliqués) pour les $e_{n}$ , ou pour les expressions en fonction des polynômes symétriques complètement homogènes ; on obtient finalement^[3] :

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}},\qquad 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}},\qquad 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}}.

On peut remarquer^[4] que la formule pour $h n$ s'obtient en prenant le permanent de la matrice pour $e n$ au lieu de son déterminant, et plus généralement qu'une expression pour un polynôme de Schur quelconque peut être obtenue en prenant l'immanant correspondant de cette matrice.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Newton's identities » (voir la liste des auteurs).

[1]
(en) L. Csanky, « Fast parallel matrix inversion algorithms », SIAM J. Comput., vol. 5, n^o 4,‎ décembre 1976 (lire en ligne [PDF]).
[2]
(en) D. G. Mead, « Newton's Identities », The American Mathematical Monthly, Mathematical Association of America, vol. 99-8,‎ 1992, p. 749–751 (DOI 10.2307/2324242, JSTOR 2324242).
[3]
(en) Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford, The Clarendon Press, Oxford University Press, coll. « Oxford Mathematical Monographs », 1979, viii+180 (ISBN 0-19-853530-9, MR 84g:05003), p. 20.
[4]
(en) Dudley E. Littlewood, The theory of group characters and matrix representations of groups, Oxford, Oxford University Press, 1950, viii+310 (ISBN 0-8218-4067-3), p. 84.

Articles connexes

Polynôme aux inverses
Indicateur de cycles du groupe symétrique
Solution fluide (en), article donnant une application des identités de Newton au calcul du polynôme caractéristique du tenseur d'Einstein dans le cas d'un fluide parfait

Bibliographie

(en) Jean-Pierre Tignol, Galois' theory of algebraic equations, Singapour, World Scientific, 2001, 333 p. (ISBN 978-981-02-4541-2, lire en ligne)
(en) F. Bergeron, G. Labelle et P. Leroux, Combinatorial species and tree-like structures, Cambridge, Cambridge University Press, 1998, 457 p. (ISBN 978-0-521-57323-8, lire en ligne)
(en) Peter J. Cameron, Permutation Groups, Cambridge, Cambridge University Press, 1999, 220 p. (ISBN 978-0-521-65378-7, lire en ligne)
(en) David A. Cox, John Little et Don O'Shea, Ideals, Varieties, and Algorithms : an introduction to computational algebraic geometry and commutative algebra, New York, Springer-Verlag, 2007, 3^e éd. (ISBN 978-0-387-35651-8, lire en ligne)
(en) David Eppstein et Michael T. Goodrich (en), « Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters », dans Algorithms and Data Structures, 10th International Workshop, WADS 2007, Springer, coll. « Lecture Notes in Computer Science » (n^o 4619), 2007, p. 637-648, « 0704.3313 », texte en accès libre, sur arXiv.
(en) I. G. Macdonald, Symmetric functions and Hall polynomials, New York, Oxford Science Publications. The Clarendon Press, Oxford University Press, coll. « Oxford Mathematical Monographs », 1995, Second éd. (ISBN 0-19-853489-2, MR 96h:05207), x+475
(en) Richard P. Stanley, Enumerative Combinatorics, vol. 2 [détail des éditions] (présentation en ligne)
(en) Bernd Sturmfels, Algorithms in Invariant Theory, New York, Springer-Verlag, 1992 (ISBN 978-0-387-82445-1)
(en) Alan Tucker, Applied Combinatorics, New York, Wiley, 1980, 5/e éd., 476 p. (ISBN 978-0-471-73507-6)

Liens externes

(en) Eric W. Weisstein, « Newton-Girard Formulas », sur MathWorld
(en) A Matrix Proof of Newton's Identities dans Mathematics Magazine
(en) Pablo A Parrilo (MIT), Application on the number of real roots

Portail de l’algèbre

[1] [1]
(en) L. Csanky, « Fast parallel matrix inversion algorithms », SIAM J. Comput., vol. 5, n^o 4,‎ décembre 1976 (lire en ligne [PDF]).

[2] [2]
(en) D. G. Mead, « Newton's Identities », The American Mathematical Monthly, Mathematical Association of America, vol. 99-8,‎ 1992, p. 749–751 (DOI 10.2307/2324242, JSTOR 2324242).

[3] [3]
(en) Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford, The Clarendon Press, Oxford University Press, coll. « Oxford Mathematical Monographs », 1979, viii+180 (ISBN 0-19-853530-9, MR 84g:05003), p. 20.

[4] [4]
(en) Dudley E. Littlewood, The theory of group characters and matrix representations of groups, Oxford, Oxford University Press, 1950, viii+310 (ISBN 0-8218-4067-3), p. 84.

[1]

[2]

[3]

[4]