Newton's identities

In mathematics, Newton's identities, also known as the Girard–Newton formulae, give relations between two types of symmetric polynomials, namely between power sums and elementary symmetric polynomials. Evaluated at the roots of a monic polynomial P in one variable, they allow expressing the sums of the k-th powers of all roots of P (counted with their multiplicity) in terms of the coefficients of P, without actually finding those roots. These identities were found by Isaac Newton around 1666, apparently in ignorance of earlier work (1629) by Albert Girard. They have applications in many areas of mathematics, including Galois theory, invariant theory, group theory, combinatorics, as well as further applications outside mathematics, including general relativity.

Statement

Newton's identities relate power sums of n variables x1, ..., xn and elementary symmetric polynomials of the same variables.

For integer k, the k-th power sum is pk=x1k+⋯+xnk. This definition is problematic for k ≤ 0 if any of the xi values is zero. Some authors restrict the xi values to be non-zero; the formulas below that have pk for k ≤ 0 assume this convention. Other authors choose to not define pk for any k ≤ 0.

The k-th elementary symmetric polynomial ek is the sum of all ⁠(nk)⁠ possible products of k different variables among x1, ..., xn: ek=∑1≤i1<…<ik≤nxi1xi2⋯xik=∑1≤i1<…<ik≤n∏j=1kxij In particular, e0=1,e1=x1+⋯+xn,e2=x1x2+x1x3+⋯+xn−1xn,en=x1…xn,ek=0,for k>n or k<0.

Newton's identities express the relationship between the ek and pk values and can be written as 0=∑j=0n(−1)jejpk−jorpk=∑j=1n(−1)j−1ejpk−j. When the convention that pj is not defined for j ≤ 0 is used these summations are instead truncated at the j = k − 1 term and the remaining terms are replaced with (−1)kkek: 0=(−1)kkek+∑j=0min⁡(n,k−1)(−1)jejpk−jorpk=(−1)k−1kek+∑j=1min⁡(n,k−1)(−1)j−1ejpk−j. Because ek = 0 for k > n this truncated-summation formula captures that the original summations remain unchanged when there is no truncation.

Small indexes

Newton's identities can be viewed as recurrence relations for expressing the pk as polynomials in the ei only or, conversely, the ei as polynomials in the pk of lower indexes. However, there is no simple general formula for expressing these formulas. For indexes at most four, one has the following formulas.

The first four Newton's identities are e1=e0p1,2e2=e1p1−e0p2,3e3=e2p1−e1p2+e0p3,4e4=e3p1−e2p2+e1p3−e0p4.

Substituting each ei or each pk with the values obtained in the preceding rows, one gets formulae for computing e1, e2, ..., en from p1, p2, ..., pn: e1=p1,2e2=p12−p2,3e3=12p13−32p1p2+p3,4e4=16p14−p12p2+43p1p3+12p22−p4, and so on.

Solving for pk, one gets p1=e1,p2=e12−2e2,p3=e13−3e1e2+3e3,p4=e14−4e12e2+4e1e3+2e22−4e4.

There is no simple closed-form formula for generalizing these formulas to arbitrary indexes. However, closed formulas exist that involve Bell polynomials; see below.

Proof when k ≥ n

Vieta's formulas express as elementary symmetric functions of x1, ..., xn the coefficients of the polynomial that has x1, ..., xn as polynomial roots. That is, ∏i=1n(x−xi)=∑i=0n(−1)ieixn−i, and, for h = 1, ..., n one has ∑i=0n(−1)ieixhn−i=0. Multiplying this equation by ⁠xhk−n⁠ and summing over h gives ∑i=0n(−1)ieipk−i=0, which are Newton's identities whenever ⁠n≤k⁠.

This proof does not work if ⁠k<n⁠ when pj is not defined for j ≤ 0. Indeed, in this case, the term of index ⁠k+1⁠ of the sum is (−1)k+1ek+1∑i=1n1xi, which cannot be evaluated in terms of the ⁠pi⁠.

Proof by a telescopic sum

The following proof, is essentially that of Newton.[citation needed] The proof does not depend on the number of variables, which is thus left implicit. The proof may also be formulated in the ring of symmetric functions that formalizes the fact the identities do not depend on the number of variables.

For ⁠1<i≤k⁠, let ⁠rk(i)⁠ be the sum of all monomials of the form xσ(1)ixσ(2)⋯xσ(k−i), where ⁠σ⁠ is a permutation of the indices of the variables. In particular, ⁠rk(k)=pk⁠.

One has piek−i=rk(i+1)+rk(i), for ⁠1<i<k⁠. In fact, the left-hand side is the sum of all products of ⁠k−i⁠ different variables and the ⁠i⁠th power of another variable; the sum of the products such that the last variable differs from others is ⁠rk(i)⁠, and the sum of all other products is ⁠rk(i)⁠.

It results that most ⁠rk(i)⁠ are cancelled in the alternate sun of the ⁠piek−i⁠, giving ∑i=1k−1(−1)ipiek−i=−p1ek−1+r2(i)+(−1)p−1rk(k)=−p1ek−1+r2(i)+(−1)p−1pke0.

One gets p1ek−1=kek+rk(2) by expanding the product of the left-hand side. By reordering the terms, his gives kek=∑i=1k(−1)i+1piek−i, which is the ⁠k⁠th Newton's identity.

Application to the characteristic polynomial of a matrix

Newton identities are useful for fast algorithms for computing the characteristic polynomial of a square matrix.

This is based on the following facts:

It follows that the kth power sum of the roots of the characteristic polynomial of a marix A is given by pk=tr⁡(Ak).

So, for taking advantage of a fast agorithm for computing matrix povers, one can compute ⁠pk=tr⁡(Ak)⁠ for ⁠k=1,…,n⁠, where n is the size of the matrix and the degree of its characteristic polynomial; then, Newton's identities allow computing the elementary symmetric functions of the eigenvalues, which are, up to their sign, the coefficiens of he characteristic polynomial Vieta's formulas).

This computation requires computing the traces of matrix powers Ak and solving a triangular system of equations. Both can be done in omplexity class NC. Therefore, the characteristic polynomial of a matrix can be computed in NC.

Rearranging the computations into an efficient form leads to the Faddeev–LeVerrier algorithm (1840), a fast parallel implementation of it is due to L. Csanky (1976). Its disadvantage is that it requires division by integers, so in general the field should have characteristic 0.

There are a number of (families of) identities that, while they should be distinguished from Newton's identities, are very closely related to them.

A variant using complete homogeneous symmetric polynomials

Denote by hk the complete homogeneous symmetric polynomial; it is the sum of all ⁠(n+k−1k)⁠ monomials of degree k: hk=∑1≤i1≤…≤ik≤nxi1xi2⋯xik=∑1≤i1≤…≤ik≤n∏j=1kxij. In particular, h0=1,h1=x1+⋯+xn,h2=x1x1+x1x2+x1x3+⋯+xn−1xn+xnxn.

The power sum polynomials also satisfy identities similar to Newton's identities, but not involving any minus signs. Expressed as identities of in the ring of symmetric functions, they read khk=∑i=1khk−ipi, valid for all k ≥ 1. Contrary to Newton's identities, the left-hand sides do not become zero for large k, and the right-hand sides contain ever more non-zero terms. For the first few values of k, one has h1=h0p1,2h2=h1p1+h0p2,3h3=h2p1+h1p2+h0p3.

Expressing elementary symmetric polynomials in terms of power sums

As mentioned, Newton's identities can be used to recursively express elementary symmetric polynomials in terms of power sums. Doing so requires the introduction of integer denominators, so it can be done in the ring ΛQ of symmetric functions with rational coefficients: e1=p1,e2=12p12−12p2=12(p12−p2),e3=16p13−12p1p2+13p3=16(p13−3p1p2+2p3),e4=124p14−14p12p2+18p22+13p1p3−14p4=124(p14−6p12p2+3p22+8p1p3−6p4),  ⋮en=(−1)n∑m1+2m2+⋯+nmn=nm1≥0,…,mn≥0∏i=1n(−pi)mimi!imi and so forth. The general formula can be conveniently expressed as ek=(−1)kk!Bk(−p1,−1!p2,−2!p3,…,−(k−1)!pk), where the Bn is the complete exponential Bell polynomial. This expression also leads to the following identity for generating functions: ∑k=0∞ektk=exp⁡(∑k=1∞(−1)k+1kpktk). Applied to a monic polynomial, these formulae express the coefficients in terms of the power sums of the roots: replace each ei by ai and each pk by sk.

Expressing complete homogeneous symmetric polynomials in terms of power sums

The analogous relations involving complete homogeneous symmetric polynomials can be similarly developed, giving equations h1=p1,h2=12p12+12p2=12(p12+p2),h3=16p13+12p1p2+13p3=16(p13+3p1p2+2p3),h4=124p14+14p12p2+18p22+13p1p3+14p4=124(p14+6p12p2+3p22+8p1p3+6p4),  ⋮hk=∑m1+2m2+⋯+kmk=km1≥0,…,mk≥0∏i=1kpimimi!imi and so forth, in which there are only plus signs. In terms of the complete Bell polynomial, hk=1k!Bk(p1,0!p2,1!p3,…,(k−1)!pk).

These expressions correspond exactly to the cycle index polynomials of the symmetric groups, if one interprets the power sums pi as indeterminates: the coefficient in the expression for hk of any monomial p1m1p2m2...plml is equal to the fraction of all permutations of k that have m1 fixed points, m2 cycles of length 2, ..., and ml cycles of length l. Explicitly, this coefficient can be written as 1/N where N=∏i=1l(mi!imi); this N is the number permutations commuting with any given permutation π of the given cycle type. The expressions for the elementary symmetric functions have coefficients with the same absolute value, but a sign equal to the sign of π, namely (−1)m2+m4+....

It can be proved by considering the following inductive step: mf(m;m1,…,mn)=f(m−1;m1−1,…,mn)+⋯+f(m−n;m1,…,mn−1)m1∏i=1n1imimi!+⋯+nmn∏i=1n1imimi!=m∏i=1n1imimi!

By analogy with the derivation of the generating function of the en, we can also obtain the generating function of the hn, in terms of the power sums, as: ∑k=0∞hktk=exp⁡(∑k=1∞pkktk).

This generating function is thus the plethystic exponential of p1t=(x1+⋯+xn)t.

Expressing power sums in terms of elementary symmetric polynomials

One may also use Newton's identities to express power sums in terms of elementary symmetric polynomials, which does not introduce denominators: p1=e1,p2=e12−2e2,p3=e13−3e2e1+3e3,p4=e14−4e2e12+4e3e1+2e22−4e4,p5=e15−5e2e13+5e3e12+5e22e1−5e4e1−5e3e2+5e5,p6=e16−6e2e14+6e3e13+9e22e12−6e4e12−12e3e2e1+6e5e1−2e23+3e32+6e4e2−6e6.

The first four formulas were obtained by Albert Girard in 1629 (thus before Newton).

The general formula (for all positive integers m) is: pm=(−1)mm∑r1+2r2+⋯+mrm=mr1≥0,…,rm≥01n(nr1r2⋯rm)∏i=1m(−ei)ri.where n = r1 + ... + rm and we are using a multinomial coefficient.

This can be conveniently stated in terms of ordinary Bell polynomials as pm=(−1)mm∑k=1m1kB̂m,k(−e1,…,−em−k+1), or equivalently as the generating function: ∑k=1∞(−1)k−1pktkk=ln⁡(1+e1t+e2t2+e3t3+⋯)=e1t−12(e12−2e2)t2+13(e13−3e1e2+3e3)t3+⋯, which is analogous to the Bell polynomial exponential generating function given in the previous subsection.

The multiple summation formula above can be proved by considering the following inductive step: f(m;r1,…,rn)=f(m−1;r1−1,⋯,rn)+⋯+f(m−n;r1,…,rn−1)=1(r1−1)!⋯rn!(m−1)(r1+⋯+rn−2)!+⋯⋯+1r1!⋯(rn−1)!(m−n)(r1+⋯+rn−2)!=1r1!⋯rn![r1(m−1)+⋯+rn(m−n)][r1+⋯+rn−2]!=1r1!⋯rn![m(r1+⋯+rn)−m][r1+⋯+rn−2]!=m(r1+⋯+rn−1)!r1!⋯rn!

Expressing power sums in terms of complete homogeneous symmetric polynomials

Finally one may use the variant identities involving complete homogeneous symmetric polynomials similarly to express power sums in term of them: p1=+h1,p2=−h12+2h2,p3=+h13−3h2h1+3h3,p4=−h14+4h2h12−4h3h1−2h22+4h4,p5=+h15−5h2h13+5h22h1+5h3h12−5h3h2−5h4h1+5h5,p6=−h16+6h2h14−9h22h12−6h3h13+2h23+12h3h2h1+6h4h12−3h32−6h4h2−6h1h5+6h6, and so on. Apart from the replacement of each ei by the corresponding hi, the only change with respect to the previous family of identities is in the signs of the terms, which in this case depend just on the number of factors present: the sign of the monomial ∏i=1lhimi is −(−1)m1+m2+m3+.... In particular the above description of the absolute value of the coefficients applies here as well.

The general formula (for all non-negative integers m) is: pm=−∑r1+2r2+⋯+mrm=mr1≥0,…,rm≥0m(r1+r2+⋯+rm−1)!r1!r2!⋯rm!∏i=1m(−hi)ri

Expressions as determinants

One can obtain explicit formulas for the above expressions in the form of determinants, by considering the first n of Newton's identities (or it counterparts for the complete homogeneous polynomials) as linear equations in which the elementary symmetric functions are known and the power sums are unknowns (or vice versa), and apply Cramer's rule to find the solution for the final unknown. For instance taking Newton's identities in the form e1=e0p1,2e2=e1p1−e0p2,3e3=e2p1−e1p2+e0p3,⋮nen=en−1p1−en−2p2+⋯+(−1)ne1pn−1+(−1)n−1pn we consider p1,−p2,p3,…,(−1)npn−1 and pn as unknowns, and solve for the final one, giving (−1)n−1pn=|10⋯e1e110⋯2e2e2e113e3⋮⋱⋱⋮en−1⋯e2e1nen||10⋯e110⋯e2e11⋮⋱⋱en−1⋯e2e11|−1pn=(−1)n−1|10⋯e1e110⋯2e2e2e113e3⋮⋱⋱⋮en−1⋯e2e1nen|=|e110⋯2e2e110⋯3e3e2e11⋮⋱⋱nenen−1⋯e1|.

Solving for en instead of for pn is similar, as the analogous computations for the complete homogeneous symmetric polynomials; in each case the details are slightly messier than the final results, which are (Macdonald 1979, p. 20): en=1n!|p110⋯p2p120⋯⋮⋱⋱pn−1pn−2⋯p1n−1pnpn−1⋯p2p1|pn=(−1)n−1|h110⋯2h2h110⋯3h3h2h11⋮⋱⋱nhnhn−1⋯h1|hn=1n!|p1−10⋯p2p1−20⋯⋮⋱⋱pn−1pn−2⋯p11−npnpn−1⋯p2p1|.

Note that the use of determinants makes that the formula for hn has additional minus signs compared to the one for en, while the situation for the expanded form given earlier is opposite. As remarked in (Littlewood 1950, p. 84) one can alternatively obtain the formula for hn by taking the permanent of the matrix for en instead of the determinant, and more generally an expression for any Schur polynomial can be obtained by taking the corresponding immanant of this matrix.

Derivation of the identities

Each of Newton's identities can easily be checked by elementary algebra; however, their validity in general needs a proof. Here are some possible derivations.

Proofs via generating functions

We can show the relationships between ek, pk, and hk via the generating functions E(t)=∑k=0n(−1)kek(x1,…,xn)tk=∏j=1n(1−xjt)P(t)=∑k=1∞pk(x1,…,xn)tk=∑j=1n(xjt+(xjt)2+…)=∑j=1nxjt1−xjtH(t)=∑k=0∞hk(x1,…,xn)tk=∏j=1n(1+xjt+(xjt)2+…)=∏j=1n11−xjt. Note that we are using the convention that pk is not defined when k ≤ 0.

E and H

Equality of the coefficient of tk on each side of the equation E(t)H(t) = 1 gives us that ∑j=0min⁡(n,k)(−1)jejhk−j=δk0, for any k ≥ 0, where we take advantage of the fact that ej = 0 for j > n, and where δk0 is the Kronecker delta function, which is 1 when k = 0 and is 0 otherwise. That is, the sum on the left hand side equals zero except in the trivial case that k = 0.

E and P

The equation 1E(t)dE(t)dt=ddtln⁡E(t)=∑j=1nddtln⁡(1−xjt)=∑j=1n−xj1−xjt=−P(t)t gives us −tdE(t)dt=P(t)E(t), and equality of the coefficient of tk on each side of that equation gives (−1)k+1kek=∑j=0min⁡(n,k−1)(−1)jejpk−j for any k ≥ 0.

Another relationship can be found by repeatedly differentiating the right-hand side of the equation P(t)=−t1E(t)dE(t)dt to get its Taylor series around t = 0; its k-th term equals pk.

H and P

Plugging 1H(t)dH(t)dt=−1E(t)dE(t)dt into the relationship between E(t) and P(t) gives tdH(t)dt=P(t)H(t), and equality of the coefficient of tk on each side of that equation gives khk=∑j=0k−1hjpk−j for any k ≥ 0.

Combinatorial proof

A short combinatorial proof of Newton's identities was given by Doron Zeilberger in 1984.

See also