Newton's identities

From Wikipedia, the free encyclopedia

In mathematics, Newton's identities, also known as the Newton–Girard 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 in about 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.

1 Mathematical statement
2 Derivation of the identities
3 Related identities
4 See also
5 External links
6 References

[edit] Mathematical statement

[edit] Formulation in terms of symmetric polynomials

Let x₁,…. x_n be variables, denote for k ≥ 1 by p_k(x₁,…,x_n) the k-th power sum:

$p_k(x_1,\ldots,x_n)=\sum\nolimits_{i=1}^nx_i^k = x_1^k+\cdots+x_n^k,$

and for k ≥ 0 denote by e_k(x₁,…,x_n) the elementary symmetric polynomial that is the sum of all distinct products of k distinct variables, so in particular

$\begin{align} 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_{i<j}x_ix_j,\\ e_n(x_1,\ldots,x_n) &= x_1x_2\cdots x_n,\\ e_k(x_1,\ldots,x_n) &= 0, \quad{\rm for}\ k>n.\\ \end{align}$

Then the Newton's identities can be stated as

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

valid for all k ≥ 1. Concretely, one gets for the first few values of k:

$\begin{align} 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{align}$

The form and validity of these equations is independent of 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

$\begin{align} e_1 &= p_1,\\ 2e_2 &= e_1p_1-p_2,\\ 3e_3 &= e_2p_1 - e_1p_2 + p_3,\\ 4e_4 &= e_3p_1 - e_2p_2 + e_1p_3 - p_4,\\ \end{align}$

and so on; here the left hand sides never become zero. These equations allow to recursively express the e_i in terms of the p_k; to be able to do the inverse, one may rewrite them as

$\begin{align} p_1 &= e_1,\\ p_2 &= e_1p_1-2e_2,\\ p_3 &= e_1p_2 - e_2p_1 + 3e_3 ,\\ p_4 &= e_1p_3 - e_2p_2 + e_3p_1 - 4e_4, \ldots\\ \end{align}$

[edit] Application to the roots of a polynomial

Now view the x_i as parameters rather than as variables, and consider the monic polynomial in t with roots x₁,…,x_n:

$\prod_{i=1}^n \left( t - x_i \right) = \sum_{k=0}^n (-1)^{k} a_k t^{n-k},$

where the coefficients $a k$ are given by the elementary symmetric polynomials in the roots: a_k = e_k(x₁,…,x_n). Now consider the power sums of the roots

$\psi_k = p_k(x_1,\ldots,x_n)= \sum_{i=1}^n x_i^k.$

Then according to Newton's identities these can be expressed recursively in terms of the coefficients of the polynomial using

$\begin{align} \psi_1 &= a_1,\\ \psi_2 &= a_1 \psi_1 - 2 a_2,\\ \psi_3 &= a_1 \psi_2 - a_2 \psi_1 + 3 a_3,\\ \psi_4 &= a_1 \psi_3 - a_2 \psi_2 + a_3 \psi_1 - 4 a_4, \ldots\\ \end{align}$

[edit] Application to the characteristic polynomial of a matrix

When the polynomial above is the characteristic polynomial of a matrix A, the roots $x i$ are the eigenvalues of the matrix, counted with their algebraic multiplicity. For any positive integer k, the matrix A^k has as eigenvalues the powers x_i^k, and each eigenvalue $x i$ of A contributes its multiplicity to that of the eigenvalue x_i^k of A^k. Then the coefficients of the characteristic polynomial of A^k are given by the elementary symmetric polynomials in those powers x_i^k. In particular, the sum of the x_i^k, which is the k-th power sum ψ_k of the roots of the characteristic polynomial of A, is given by its trace:

$\psi_k = {\rm tr} ( A^k )\,.$

The Newton identities now relate the traces of the powers A^k to the coefficients of the characteristic polynomial of A. 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^k and their traces.

[edit] Relation with Galois theory

For a given n, the elementary symmetric polynomials e_k(x₁,…,x_n) for k = 1,…, n form an algebraic basis for the space of symmetric polynomials in x₁,…. x_n: every polynomial expression in the x_i that is invariant under all permutations of those variables is given by a polynomial expression in those elementary symmetric polynomials, and this expression is unique up to equivalence of polynomial expressions. This is a general fact known as the fundamental theorem of symmetric polynomials, and Newton's identities provide explicit formulae in the case of power sum symmetric polynomials. Applied to the monic polynomial $\textstyle t^n+\sum_{k=1}^n (-1)^{k} a_k t^{n-k}$ with all coefficients a_k considered as free parameters, this means that every symmetric polynomial expression S(x₁,…,x_n) in its roots can be expressed instead as a polynomial expression P(a₁,…,a_n) in terms of its coefficients only, in other words without requiring knowledge of the roots. This fact also follows from general considerations in Galois theory (one views the a_k as elements of a base field, the roots live in an extension field whose Galois group permutes them according to the full symmetric group, and the field fixed under all elements of the Galois group is the base field).

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. In fact the first n power sums also form an algebraic basis for the space of symmetric polynomials.

[edit] 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

[edit] From the special case n = k

One can obtain the k-th Newton identity in k variables by substitution into $\textstyle\prod_{i=1}^k (t - x_i) = \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k)t^i$ as follows. Substituting x_j for t gives

$0= \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k){x_j}^i \quad\mbox{for all }1\leq j\leq k$

Summing over all j gives

$0= (-1)^kke_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),$

where the terms for i = 0 were taken out of the sum because p₀ is (usually) not defined. This equation immediately gives the k-th Newton identity in k variables. 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. Concretely, the identities in n < k variables can be deduced by setting k − n variables to zero. 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. 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.

[edit] Comparing coefficients in series

A derivation can be given by formal manipulations based on the basic relation $\textstyle\prod_{i=1}^n (t - x_i) = \sum_{k=0}^n (-1)^{k} a_k t^{n-k}$ linking roots and coefficients of a monic polynomial. However, to facilitate the manipulations one first "reverses the polynomials" by substituting 1/t for t and then multiplying both sides by tⁿ to remove negative powers of t, giving $\textstyle\prod_{i=1}^n (1- x_it) = \sum_{k=0}^n (-1)^{k} a_k t^k$ . Swapping sides and expressing the a_i as the elementary symmetric polynomials they stand for gives the identity

$\sum_{k=0}^n (-1)^{k} e_k(x_1,\ldots,x_n) t^k=\prod_{i=1}^n (1- x_it).$

One differentiates both sides with respect to t, and then (for convenience) multiplies by t, to obtain

$\begin{align} \sum_{k=0}^n (-1)^{k}k e_k(x_1,\ldots,x_n) t^k &= t \sum_{i=1}^n \left((-x_i) \prod\nolimits_{j\neq i} (1- x_jt)\right)\\ &= -\bigl(\sum_{i=1}^n \frac{x_it}{1-x_it}\bigr) \prod\nolimits_{j=1}^n (1- x_jt)\\ &= -\bigl(\sum_{i=1}^n \sum_{j=1}^\infty(x_it)^j\bigr)\bigl(\sum_{l=0}^n (-1)^{l} e_l(x_1,\ldots,x_n) t^l\bigr)\\ &= \bigl(\sum_{j=1}^\infty p_j(x_1,\ldots,x_n)t^j\bigr)\bigl(\sum_{l=0}^n (-1)^{l-1} e_l(x_1,\ldots,x_n) t^l\bigr),\\ \end{align}$

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 from of the summation, then the fraction in the summand was developed as a series in t, and finally the coefficient of each t ^j was collected, giving a power sum. (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.) Comparing coefficients of t^k on both sides one obtains

$(-1)^{k}k e_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),$

which gives the k-th Newton identity.

[edit] As a telescopic sum of symmetric function identities

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) = p_k; for r(1) the description would amount to that of e_k, but this case was excluded since here monomials no longer have any distinguished variable. All products p_ie_k−i can be expressed in terms of the r(j) with the first and last case being somewhat special. One has

$p_ie_{k-i}=r(i)+r(i+1)\quad\mbox{for }1<i<k$

since each product of terms on the left involving distinct variables contributes to r(i), while those where the variable from p_i already occurs among the variables of the term from e_k−i contributes to r(i + 1), and all terms on the right are so obtained exactly once. For i = k one multiplies by e₀ = 1, giving trivially

$p_ke_0=p_k=r(k)\,$ .

Finally the product p₁e_k−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 e_k, since any on of the variables may come from the factor p₁; thus

$p_1e_{k-1}=ke_k+r(2)\,$ .

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.

[edit] Related identities

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

[edit] A variant using complete homogeneous symmetric polynomials

Denoting by h_k 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

$kh_k=\sum_{i=1}^kh_{k-i}p_i,$

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 nonzero terms. For the first few values of k one has

$\begin{align} h_1 &= p_1,\\ 2h_2 &= h_1p_1+p_2,\\ 3h_3 &= h_2p_1 + h_1p_2 + p_3.\\ \end{align}$

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

$\sum_{k=0}^\infty h_k(X_1,\ldots,X_n)t^k = \prod_{i=1}^n\frac1{1-X_it}.$

The other proofs given above of Newton's identities cannot be easily adapted to prove these variants of those identities.

[edit] Expressing elementary symmetric polynomials in terms of power sums

A 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:

$\begin{alignat}2 e_1 &= p_1,\\ e_2 &= \textstyle\frac12p_1^2 - \frac12p_2 &&= \textstyle\frac12 ( p_1^2 - p_2 ),\\ e_3 &= \textstyle\frac16p_1^3 - \frac12p_1 p_2 + \frac13p_3 &&= \textstyle\frac{1}{6} ( p_1^3 - 3 p_1 p_2 + 2 p_3 ),\\ e_4 &= \textstyle\frac1{24}p_1^4 - \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 - \frac14p_4 &&= \textstyle\frac1{24} ( p_1^4 - 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 - 6 p_4 ),\\ \end{alignat}$

and so forth. Applied to a monic polynomial these formulae express the coefficients in terms of the power sums of the roots: replace each e_i by a_i and each p_k by ψ_k.

[edit] Expressing complete homogeneous symmetric polynomials in terms of power sums

The analogous relations involving complete homogeneous symmetric polynomials can be similarly developed, giving equations

$\begin{alignat}2 h_1 &= p_1,\\ h_2 &= \textstyle\frac12p_1^2 + \frac12p_2 &&= \textstyle\frac12 ( p_1^2 + p_2 ),\\ h_3 &= \textstyle\frac16p_1^3 + \frac12p_1 p_2 + \frac13p_3 &&= \textstyle\frac{1}{6} ( p_1^3 + 3 p_1 p_2 + 2 p_3 ),\\ h_4 &= \textstyle\frac1{24}p_1^4 + \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 + \frac14p_4 &&= \textstyle\frac1{24} ( p_1^4 + 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 + 6 p_4 ),\\ \end{alignat}$

and so forth, in which there are only plus signs. These expressions correspond exactly to the cycle index polynomials of the symmetric groups, if one interprets the power sums p_i as indeterminates: the coefficient in the expression for h_k of any monomial p₁^m₁p₂^m₂…p_l^m_l is equal to the fraction of all permutations of k that have m₁ fixed points, m₂ cycles of length 2, …, and m_l cycles of length l. Explicitly, this coefficient can be written as $1 / N$ where $N=\Pi_{i=1}^l(m_i!\,i^{m_i})$ ; 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)^{m₂+m₄+…}.

[edit] Expressing power sums in terms of elementary symmetric polynomials

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

$\begin{align} p_1 &= e_1,\\ p_2 &= e_1^2 - 2 e_2,\\ p_3 &= e_1^3 - 3 e_2 e_1 + 3 e_3,\\ p_4 &= e_1^4 - 4 e_2 e_1^2 + 4 e_3 e_1 + 2 e_2^2 - 4 e_4,\\ p_5 &= e_1^5 - 5 e_2 e_1^3 + 5 e_2^2 e_1 + 5 e_3 e_1^2 - 5 e_3e_2 - 5 e_4 e_1 + 5 e_5,\\ p_6 &= e_1^6 - 6 e_2 e_1^4 + 9 e_2^2 e_1^2 + 6 e_3 e_1^3 - 2 e_2^3 - 12 e_3 e_2 e_1 - 6 e_4 e_1^2 + 3 e_3^2 + 6 e_4 e_2 + 6 e_1 e_5 - 6e_6,\\ \end{align}$

giving ever longer expressions that do not seem to follow any simple pattern. By consideration of the relations used to obtain these expressions, it can however be seen that the coefficient of some monomial $M=\Pi_{i=1}^l e_i^{m_i}$ in the expression for $p k$ has the same sign as the coefficient of the corresponding product $\Pi_{i=1}^l p_i^{m_i}$ in the expression for $e k$ described above, namely the sign (−1)^{m₂+m₄+…}. Furthermore the absolute value of the coefficient of M is the sum, over all distinct sequences of elementary symmetric functions whose product is M, of the index of the last one in the sequence: for instance the coefficent of $e_1^5e_3e_4^3$ in the expression for p₂₀ will be $(-1)^{0+3}(280\times1+56\times3+168\times4)=-1120$ , since of all distinct orderings of the five factors e₁, one factor e₃ and three factors e₄, there are 280 that end with e₁, 56 that end with e₃, and 168 that end with e₄.

[edit] 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 powr sums in term of them:

$\begin{align} p_1 &= + h_1,\\ p_2 &= - h_1^2 + 2 h_2,\\ p_3 &= + h_1^3 - 3 h_2 h_1 + 3 h_3,\\ p_4 &= - h_1^4 + 4 h_2 h_1^2 - 4 h_3 h_1 - 2 h_2^2 + 4 h_4,\\ p_5 &= + h_1^5 - 5 h_2 h_1^3 + 5 h_2^2 h_1 + 5 h_3 h_1^2 - 5 h_3h_2 - 5 h_4 h_1 + 5 h_5,\\ p_6 &= - h_1^6 + 6 h_2 h_1^4 - 9 h_2^2 h_1^2 - 6 h_3 h_1^3 + 2 h_2^3 + 12 h_3 h_2 h_1 + 6 h_4 h_1^2 - 3 h_3^2 - 6 h_4 h_2 - 6 h_1 h_5 + 6h_6,\\ \end{align}$

and so on. Apart from the replacement of each e_i by the corresponding h_i, 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 $\Pi_{i=1}^l h_i^{m_i}$ is −(−1)^{m₁+m₂+m₃+…}. In partuclar the above description of the absolute value of the coefficients applies here as well.

[edit] See also

Power sum symmetric polynomial
Elementary symmetric polynomial
Symmetric function
Fluid solutions, an article giving an application of Newton's identities to computing the characteristic polynomial of the Einstein tensor in the case of a perfect fluid, and similar articles on other types of exact solutions in general relativity.

[edit] External links

Newton–Girard formulas on MathWorld
A Matrix Proof of Newton's Identities in Mathematics Magazine

[edit] References

Tignol, Jean-Pierre (2001). Galois' theory of algebraic equations. Singapore: World Scientific. ISBN 978-981-02-4541-2.

Bergeron, F.; Labelle, G.; and Leroux, P. (1998). Combinatorial species and tree-like structures. Cambridge: Cambridge University Press. ISBN 978-0-521-57323-8.

Cameron, Peter J. (1999). Permutation Groups. Cambridge: Cambridge University Press. ISBN 978-0-521-65378-7.

Cox, David; Little, John, and O'Shea, Donal (1992). Ideals, Varieties, and Algorithms. New York: Springer-Verlag. ISBN 978-0-387-97847-5.

Eppstein, D.; Goodrich, M. T. (2007). "Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters". Algorithms and Data Structures, 10th International Workshop, WADS 2007: 637–648, Springer-Verlag, Lecture Notes in Computer Science 4619. arXiv:0704.3313

Macdonald, I. G. (1979). Symmetric functions and Hall polynomials, Oxford Mathematical Monographs. Oxford: The Clarendon Press, Oxford University Press, viii+180. ISBN 0-19-853530-9. MR 84g:05003

Macdonald, I. G. (1995). Symmetric functions and Hall polynomials, Second edition, Oxford Mathematical Monographs, New York: Oxford Science Publications. The Clarendon Press, Oxford University Press, x+475. ISBN 0-19-853489-2. MR 96h:05207

Mead, D.G. (1992-10). "Newton's Identities". The American Mathematical Monthly 99 (8): 749–751. doi:10.2307/2324242.

Stanley, Richard P. (1999). Enumerative Combinatorics, Vol. 2. Cambridge University Press. ISBN 0-521-56069-1 (hardback), ISBN 0-521-78987-7 (paperback).

Sturmfels, Bernd (1992). Algorithms in Invariant Theory. New York: Springer-Verlag. ISBN 978-0-387-82445-1.

Tucker, Alan (1980). Applied Combinatorics, 5/e, New York: Wiley. ISBN 978-0-471-73507-6.

See also ebooksgratis.com: no banners, no cookies, totally FREE.