Newton's identities

From Wikipedia for FEVERv2
Jump to navigation Jump to search

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. Newton's identities_sentence_0

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. Newton's identities_sentence_1

These identities were found by Isaac Newton around 1666, apparently in ignorance of earlier work (1629) by Albert Girard. Newton's identities_sentence_2

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. Newton's identities_sentence_3

Mathematical statement Newton's identities_section_0

Formulation in terms of symmetric polynomials Newton's identities_section_1

Let x1, ..., xn be variables, denote for k ≥ 1 by pk(x1, ..., xn) the k-th power sum: Newton's identities_sentence_4

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 Newton's identities_sentence_5

Then Newton's identities can be stated as Newton's identities_sentence_6

valid for all n ≥ 1 and n ≥k ≥ 1. Newton's identities_sentence_7

Also, one has Newton's identities_sentence_8

for all k > n ≥ 1. Newton's identities_sentence_9

Concretely, one gets for the first few values of k: Newton's identities_sentence_10

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. Newton's identities_sentence_11

In that ring one has Newton's identities_sentence_12

and so on; here the left-hand sides never become zero. Newton's identities_sentence_13

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 Newton's identities_sentence_14

In general, we have Newton's identities_sentence_15

valid for all n ≥ 1 and n ≥k ≥ 1. Newton's identities_sentence_16

Also, one has Newton's identities_sentence_17

for all k > n ≥ 1. Newton's identities_sentence_18

Application to the roots of a polynomial Newton's identities_section_2

The polynomial with roots xi may be expanded as Newton's identities_sentence_19

Formulating polynomials in this way is useful in using the method of Delves and Lyness to find the zeros of an analytic function. Newton's identities_sentence_20

Application to the characteristic polynomial of a matrix Newton's identities_section_3

The Newton identities now relate the traces of the powers A to the coefficients of the characteristic polynomial of A. Newton's identities_sentence_21

Using them in reverse to express the elementary symmetric polynomials in terms of the power sums, they can be used to find the characteristic polynomial by computing only the powers A and their traces. Newton's identities_sentence_22

This computation requires computing the traces of matrix powers A and solving a triangular system of equations. Newton's identities_sentence_23

Both can be done in complexity class NC (solving a triangular system can be done by divide-and-conquer). Newton's identities_sentence_24

Therefore, characteristic polynomial of a matrix can be computed in NC. Newton's identities_sentence_25

By the Cayley–Hamilton theorem, every matrix satisfies its characteristic polynomial, and a simple transformation allows to find the adjugate matrix in NC. Newton's identities_sentence_26

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). Newton's identities_sentence_27

Its disadvantage is that it requires division by integers, so in general the field should have characteristic, 0. Newton's identities_sentence_28

Relation with Galois theory Newton's identities_section_4

The Newton identities also permit expressing the elementary symmetric polynomials in terms of the power sum symmetric polynomials, showing that any symmetric polynomial can also be expressed in the power sums. Newton's identities_sentence_29

In fact the first n power sums also form an algebraic basis for the space of symmetric polynomials. Newton's identities_sentence_30

Related identities Newton's identities_section_5

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

A variant using complete homogeneous symmetric polynomials Newton's identities_section_6

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. Newton's identities_sentence_32

Expressed as identities of in the ring of symmetric functions, they read Newton's identities_sentence_33

valid for all n ≥ k ≥ 1. Newton's identities_sentence_34

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. Newton's identities_sentence_35

For the first few values of k, one has Newton's identities_sentence_36

These relations can be justified by an argument analogous to the one by comparing coefficients in power series given above, based in this case on the generating function identity Newton's identities_sentence_37

Proofs of Newton's identities, like these given below, cannot be easily adapted to prove these variants of those identities. Newton's identities_sentence_38

Expressing elementary symmetric polynomials in terms of power sums Newton's identities_section_7

As mentioned, Newton's identities can be used to recursively express elementary symmetric polynomials in terms of power sums. Newton's identities_sentence_39

Doing so requires the introduction of integer denominators, so it can be done in the ring ΛQ of symmetric functions with rational coefficients: Newton's identities_sentence_40

and so forth. Newton's identities_sentence_41

The general formula can be conveniently expressed as Newton's identities_sentence_42

where the Bn is the complete exponential Bell polynomial. Newton's identities_sentence_43

This expression also leads to the following identity for generating functions: Newton's identities_sentence_44

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. Newton's identities_sentence_45

Expressing complete homogeneous symmetric polynomials in terms of power sums Newton's identities_section_8

The analogous relations involving complete homogeneous symmetric polynomials can be similarly developed, giving equations Newton's identities_sentence_46

and so forth, in which there are only plus signs. Newton's identities_sentence_47

In terms of the complete Bell polynomial, Newton's identities_sentence_48

It can be proved by considering the following inductive step: Newton's identities_sentence_49

Expressing power sums in terms of elementary symmetric polynomials Newton's identities_section_9

One may also use Newton's identities to express power sums in terms of symmetric polynomials, which does not introduce denominators: Newton's identities_sentence_50

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

The general formula (for all non-negative integers m) is: Newton's identities_sentence_52

This can be conveniently stated in terms of ordinary Bell polynomials as Newton's identities_sentence_53

or equivalently as the generating function: Newton's identities_sentence_54

which is analogous to the Bell polynomial exponential generating function given in the previous subsection. Newton's identities_sentence_55

The multiple summation formula above can be proved by considering the following inductive step: Newton's identities_sentence_56

Expressing power sums in terms of complete homogeneous symmetric polynomials Newton's identities_section_10

Finally one may use the variant identities involving complete homogeneous symmetric polynomials similarly to express power sums in term of them: Newton's identities_sentence_57

The general formula (for all non-negative integers m) is: Newton's identities_sentence_58

Expressions as determinants Newton's identities_section_11

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. Newton's identities_sentence_59

For instance taking Newton's identities in the form Newton's identities_sentence_60

Derivation of the identities Newton's identities_section_12

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

Here are some possible derivations. Newton's identities_sentence_62

From the special case n = k Newton's identities_section_13

One can obtain the k-th Newton identity in k variables by substitution into Newton's identities_sentence_63

as follows. Newton's identities_sentence_64

Substituting xj for t gives Newton's identities_sentence_65

Summing over all j gives Newton's identities_sentence_66

where the terms for i = 0 were taken out of the sum because p0 is (usually) not defined. Newton's identities_sentence_67

This equation immediately gives the k-th Newton identity in k variables. Newton's identities_sentence_68

Since this is an identity of symmetric polynomials (homogeneous) of degree k, its validity for any number of variables follows from its validity for k variables. Newton's identities_sentence_69

Concretely, the identities in n < k variables can be deduced by setting k − n variables to zero. Newton's identities_sentence_70

The k-th Newton identity in n > k variables contains more terms on both sides of the equation than the one in k variables, but its validity will be assured if the coefficients of any monomial match. Newton's identities_sentence_71

Because no individual monomial involves more than k of the variables, the monomial will survive the substitution of zero for some set of n − k (other) variables, after which the equality of coefficients is one that arises in the k-th Newton identity in k (suitably chosen) variables. Newton's identities_sentence_72

Comparing coefficients in series Newton's identities_section_14

Another derivation can be obtained by computations in the ring of formal power series Rt, where R is Z[x1,..., xn], the ring of polynomials in n variables x1,..., xn over the integers. Newton's identities_sentence_73

Starting again from the basic relation Newton's identities_sentence_74

and "reversing the polynomials" by substituting 1/t for t and then multiplying both sides by t to remove negative powers of t, gives Newton's identities_sentence_75

(the above computation should be performed in the field of fractions of Rt; alternatively, the identity can be obtained simply by evaluating the product on the left side) Newton's identities_sentence_76

Swapping sides and expressing the ai as the elementary symmetric polynomials they stand for gives the identity Newton's identities_sentence_77

One formally differentiates both sides with respect to t, and then (for convenience) multiplies by t, to obtain Newton's identities_sentence_78

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 Newton's identities_sentence_79

and finally the coefficient of each t  was collected, giving a power sum. Newton's identities_sentence_80

(The series in t is a formal power series, but may alternatively be thought of as a series expansion for t sufficiently close to 0, for those more comfortable with that; in fact one is not interested in the function here, but only in the coefficients of the series.) Newton's identities_sentence_81

Comparing coefficients of t on both sides one obtains Newton's identities_sentence_82

which gives the k-th Newton identity. Newton's identities_sentence_83

As a telescopic sum of symmetric function identities Newton's identities_section_15

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). Newton's identities_sentence_84

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)). Newton's identities_sentence_85

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. Newton's identities_sentence_86

All products piek−i can be expressed in terms of the r(j) with the first and last case being somewhat special. Newton's identities_sentence_87

One has Newton's identities_sentence_88

since each product of terms on the left involving distinct variables contributes to r(i), while those where the variable from pi already occurs among the variables of the term from ek−i contributes to r(i + 1), and all terms on the right are so obtained exactly once. Newton's identities_sentence_89

For i = k one multiplies by e0 = 1, giving trivially Newton's identities_sentence_90

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 Newton's identities_sentence_91

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. Newton's identities_sentence_92

Combinatorial Proof Newton's identities_section_16

A short combinatorial proof of Newton's Identities is given in (Zeilberger, 1984) Newton's identities_sentence_93

See also Newton's identities_section_17

Newton's identities_unordered_list_0


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Newton's identities.