These identities were found by Isaac Newton around 1666, apparently in ignorance of earlier work (1629) by Albert Girard.
Concretely, one gets for the first few values of k: The form and validity of these equations do not depend on the number n of variables (although the point where the left-hand side becomes 0 does, namely after the n-th identity), which makes it possible to state them as identities in the ring of symmetric functions.
These equations allow to recursively express the ei in terms of the pk; to be able to do the inverse, one may rewrite them as In general, we have valid for all n ≥k ≥ 1.
may be expressed recursively in terms of the power sums as Formulating polynomials in this way is useful in using the method of Delves and Lyness[1] to find the zeros of an analytic function.
Both can be done in complexity class NC (solving a triangular system can be done by divide-and-conquer).
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.
In fact the first n power sums also form an algebraic basis for the space of symmetric polynomials.
Denoting by hk the complete homogeneous symmetric polynomial (that is, the sum of all monomials of degree k), 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 valid for all n ≥ k ≥ 1.
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: and so forth.
[2] The general formula can be conveniently expressed as where the Bn is the complete exponential Bell polynomial.
This expression also leads to the following identity for generating functions: 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.
The analogous relations involving complete homogeneous symmetric polynomials can be similarly developed, giving equations and so forth, in which there are only plus signs.
In terms of the complete Bell polynomial, 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
It can be proved by considering the following inductive step: By analogy with the derivation of the generating function of the
, in terms of the power sums, as: This generating function is thus the plethystic exponential of
[3] The general formula (for all positive integers m) is: This can be conveniently stated in terms of ordinary Bell polynomials as or equivalently as the generating function:[4] 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: Finally one may use the variant identities involving complete homogeneous symmetric polynomials similarly to express power sums in term of them: and so on.
The general formula (for all non-negative integers m) is: 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.
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): Note that the use of determinants makes that the formula for
instead of the determinant, and more generally an expression for any Schur polynomial can be obtained by taking the corresponding immanant of this matrix.
Each of Newton's identities can easily be checked by elementary algebra; however, their validity in general needs a proof.
Starting again from the basic relation and "reversing the polynomials" by substituting 1/t for t and then multiplying both sides by tn to remove negative powers of t, gives (the above computation should be performed in the field of fractions of R[[t]]; alternatively, the identity can be obtained simply by evaluating the product on the left side) Swapping sides and expressing the ai as the elementary symmetric polynomials they stand for gives the identity One formally differentiates both sides with respect to t, and then (for convenience) multiplies by t, to obtain where the polynomial on the right hand side was first rewritten as a rational function in order to be able to factor out a product out of the summation, then the fraction in the summand was developed as a series in t, using the formula and finally the coefficient of each t j was collected, giving a power sum.
Comparing coefficients of tk on both sides one obtains which gives the k-th Newton identity.
The following derivation, given essentially in (Mead, 1992), is formulated in the ring of symmetric functions for clarity (all identities are independent of the number of variables).
Fix some k > 0, and define the symmetric function r(i) for 2 ≤ i ≤ k as the sum of all distinct monomials of degree k obtained by multiplying one variable raised to the power i with k − i distinct other variables (this is the monomial symmetric function mγ where γ is a hook shape (i,1,1,...,1)).
In particular r(k) = pk; for r(1) the description would amount to that of ek, but this case was excluded since here monomials no longer have any distinguished variable.
For i = k one multiplies by e0 = 1, giving trivially Finally the product p1ek−1 for i = 1 gives contributions to r(i + 1) = r(2) like for other values i < k, but the remaining contributions produce k times each monomial of ek, since any one of the variables may come from the factor p1; thus The k-th Newton identity is now obtained by taking the alternating sum of these equations, in which all terms of the form r(i) cancel out.