Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Newton's identities
Summary
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.
Let x1, ..., xn be variables, denote for k ≥ 1 by pk(x1, ..., xn) the k-th power sum:
and for k ≥ 0 denote by ek(x1, ..., xn) the elementary symmetric polynomial (that is, the sum of all distinct products of k distinct variables), so
Then Newton's identities can be stated as
valid for all n ≥ k ≥ 1.
Also, one has
for all k > n ≥ 1.
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. In that ring one has
and so on; here the left-hand sides never become zero.
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.
Also, one has
for all k > n ≥ 1.
The polynomial with roots xi may be expanded as
where the coefficients are the symmetric polynomials defined above.
Given the power sums of the roots
the coefficients of the polynomial with roots 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 to find the zeros of an analytic function.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related units (2)