HOME

TheInfoList



OR:

In mathematics, Newton's identities, also known as the Girard–Newton formulae, give relations between two types of
symmetric polynomial In mathematics, a symmetric polynomial is a polynomial in variables, such that if any of the variables are interchanged, one obtains the same polynomial. Formally, is a ''symmetric polynomial'' if for any permutation of the subscripts one ha ...
s, namely between power sums and elementary symmetric polynomials. Evaluated at the
root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
s of a monic
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An examp ...
''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 Sir Isaac Newton (25 December 1642 – 20 March 1726/27) was an English mathematician, physicist, astronomer, alchemist, theologian, and author (described in his time as a "natural philosopher"), widely recognised as one of the great ...
around 1666, apparently in ignorance of earlier work (1629) by
Albert Girard Albert Girard () (11 October 1595 in Saint-Mihiel, France − 8 December 1632 in Leiden, The Netherlands) was a French-born mathematician. He studied at the University of Leiden. He "had early thoughts on the fundamental theorem of algebra" and g ...
. They have applications in many areas of mathematics, including
Galois theory In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
,
invariant theory Invariant theory is a branch of abstract algebra dealing with actions of groups on algebraic varieties, such as vector spaces, from the point of view of their effect on functions. Classically, the theory dealt with the question of explicit descri ...
,
group theory In abstract algebra, group theory studies the algebraic structures known as groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces, can all be seen as ...
,
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
, as well as further applications outside mathematics, including
general relativity General relativity, also known as the general theory of relativity and Einstein's theory of gravity, is the geometric theory of gravitation published by Albert Einstein in 1915 and is the current description of gravitation in modern physic ...
.


Mathematical statement


Formulation in terms of symmetric polynomials

Let ''x''1, ..., ''x''''n'' be variables, denote for ''k'' ≥ 1 by ''p''''k''(''x''1, ..., ''x''''n'') the ''k''-th power sum: : p_k(x_1,\ldots,x_n)=\sum_^n x_i^k = x_1^k+\cdots+x_n^k, and for ''k'' ≥ 0 denote by ''e''''k''(''x''1, ..., ''x''''n'') the elementary symmetric polynomial (that is, the sum of all distinct products of ''k'' distinct variables), so : \begin 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) &= \sum_x_ix_j,\\ &\;\;\vdots \\ e_n(x_1, \ldots, x_n) &= x_1 x_2 \cdots x_n,\\ e_k(x_1, \ldots, x_n) &= 0, \quad\text\ k>n.\\ \end Then Newton's identities can be stated as : ke_k(x_1,\ldots,x_n) = \sum_^k(-1)^ e_ (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), valid for all and . Also, one has : 0 = \sum_^k(-1)^ e_ (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), for all . Concretely, one gets for the first few values of ''k'': : \begin 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 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 algebra and in particular in algebraic combinatorics, the ring of symmetric functions is a specific limit of the rings of symmetric polynomials in ''n'' indeterminates, as ''n'' goes to infinity. This ring serves as universal structure in which ...
. In that ring one has :\begin e_1 &= p_1,\\ 2e_2 &= e_1p_1-p_2 = p_1^2-p_2,\\ 3e_3 &= e_2p_1 - e_1p_2 + p_3 = \tfrac12 p_1^3-\tfrac32p_1p_2+p_3,\\ 4e_4 &= e_3p_1 - e_2p_2 + e_1p_3 - p_4 = \tfrac16p_1^4 - p_1^2p_2 + \tfrac43p_1p_3+\tfrac12p_2^2-p_4,\\ \end 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 p_1 &= e_1,\\ p_2 &= e_1p_1-2e_2 = e_1^2 - 2e_2,\\ p_3 &= e_1p_2 - e_2p_1 + 3e_3 = e_1^3-3e_1e_2+3e_3,\\ p_4 &= e_1p_3 - e_2p_2 + e_3p_1 - 4e_4 = e_1^4-4e_1^2e_2+4e_1e_3+2e_2^2-4e_4, \\ & \ \ \vdots \end In general, we have : p_k(x_1,\ldots,x_n) = (-1)^ke_k(x_1,\ldots,x_n)+\sum_^(-1)^ e_ (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), valid for all ''n'' ≥ 1 and ''n'' ≥''k'' ≥ 1. Also, one has : p_k(x_1,\ldots,x_n) = \sum_^(-1)^ e_ (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), for all ''k'' > ''n'' ≥ 1.


Application to the roots of a polynomial

The polynomial with roots ''x''''i'' may be expanded as : \prod_^n (x - x_i) = \sum_^n (-1)^k e_k x^, where the coefficients e_k(x_1,\ldots,x_n) are the symmetric polynomials defined above. Given the ''power sums'' of the roots : p_k(x_1,\ldots,x_n)= \sum_^n x_i^k, the coefficients of the polynomial with roots x_1,\ldots,x_n may be expressed recursively in terms of the power sums as :\begin e_0 &= 1,\\ pt -e_1 &=-p_1,\\ pt e_2 &= \frac(e_1 p_1 - p_2),\\ pt -e_3 &=-\frac(e_2 p_1 - e_1 p_2 + p_3),\\ pt e_4 &= \frac(e_3 p_1 - e_2 p_2 + e_1 p_3 - p_4), \\ & \ \ \vdots \end Formulating polynomials in this way is useful in using the method of Delves and Lyness to find the zeros of an analytic function.


Application to the characteristic polynomial of a matrix

When the polynomial above is the
characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The char ...
of a
matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...
''A'' (in particular when ''A'' is the
companion matrix In linear algebra, the Frobenius companion matrix of the monic polynomial : p(t)=c_0 + c_1 t + \cdots + c_t^ + t^n ~, is the square matrix defined as :C(p)=\begin 0 & 0 & \dots & 0 & -c_0 \\ 1 & 0 & \dots & 0 & -c_1 \\ 0 & 1 & \dots & 0 & -c_2 ...
of the polynomial), the roots x_i are the
eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted ...
s 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 p''k'' of the roots of the characteristic polynomial of ''A'', is given by its
trace Trace may refer to: Arts and entertainment Music * ''Trace'' (Son Volt album), 1995 * ''Trace'' (Died Pretty album), 1993 * Trace (band), a Dutch progressive rock band * ''The Trace'' (album) Other uses in arts and entertainment * ''Trace'' ...
: :p_k = \operatorname ( 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. This computation requires computing the traces of matrix powers ''A''''k'' and solving a triangular system of equations. Both can be done in complexity class NC (solving a triangular system can be done by divide-and-conquer). Therefore, characteristic polynomial of a matrix can be computed in NC. By the
Cayley–Hamilton theorem In linear algebra, the Cayley–Hamilton theorem (named after the mathematicians Arthur Cayley and William Rowan Hamilton) states that every square matrix over a commutative ring (such as the real or complex numbers or the integers) satisfies ...
, every matrix satisfies its characteristic polynomial, and a simple transformation allows to find the
adjugate matrix In linear algebra, the adjugate or classical adjoint of a square matrix is the transpose of its cofactor matrix and is denoted by . It is also occasionally known as adjunct matrix, or "adjoint", though the latter today normally refers to a differe ...
in NC. Rearranging the computations into an efficient form leads to the ''
Faddeev–LeVerrier algorithm In mathematics ( linear algebra), the Faddeev–LeVerrier algorithm is a recursive method to calculate the coefficients of the characteristic polynomial p_A(\lambda)=\det (\lambda I_n - A) of a square matrix, , named after Dmitry Konstantinovich ...
'' (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.


Relation with Galois theory

For a given ''n'', the elementary symmetric polynomials ''e''''k''(''x''1,...,''x''''n'') for ''k'' = 1,..., ''n'' form an algebraic basis for the space of symmetric polynomials in ''x''1,.... ''x''''n'': every polynomial expression in the ''x''''i'' that is invariant under all permutations of those variables is given by a
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An examp ...
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 In mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial can be expressed as a polynomial in elementary sym ...
, and Newton's identities provide explicit formulae in the case of power sum symmetric polynomials. Applied to the monic polynomial t^n+\sum_^n (-1)^k a_k t^ with all coefficients ''a''''k'' considered as free parameters, this means that every symmetric polynomial expression ''S''(''x''1,...,''x''''n'') in its roots can be expressed instead as a polynomial expression ''P''(''a''1,...,''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 In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
(one views the ''a''''k'' as elements of a base field with roots 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.


Related identities

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

Denoting by ''h''''k'' the
complete homogeneous symmetric polynomial In mathematics, specifically in algebraic combinatorics and commutative algebra, the complete homogeneous symmetric polynomials are a specific kind of symmetric polynomials. Every symmetric polynomial can be expressed as a polynomial expression in ...
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 In algebra and in particular in algebraic combinatorics, the ring of symmetric functions is a specific limit of the rings of symmetric polynomials in ''n'' indeterminates, as ''n'' goes to infinity. This ring serves as universal structure in which ...
, they read :kh_k = \sum_^kh_p_i, valid for all n ≥ ''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 :\begin h_1 &= p_1,\\ 2h_2 &= h_1p_1 + p_2,\\ 3h_3 &= h_2p_1 + h_1p_2 + p_3.\\ \end 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 :\sum_^\infty h_k(x_1, \ldots, x_n)t^k = \prod_^n\frac1. Proofs of Newton's identities, like these given below, cannot be easily adapted to prove these variants of those identities.


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: :\begin 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 ( p_1^3 - 3 p_1 p_2 + 2 p_3 ),\\ e_4 &= \textstyle\frac1p_1^4 - \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 - \frac14p_4 &&= \textstyle\frac1 ( p_1^4 - 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 - 6 p_4 ),\\ &~~\vdots\\ e_n &= (-1)^n \sum_ \prod_^n \frac \\ \end and so forth. The general formula can be conveniently expressed as :e_k = \frac B_(- p_1, -1! \, p_2, - 2! \, p_3, \ldots, - (k-1)! \, p_k ), where the ''Bn'' is the complete exponential
Bell polynomial In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are used in the study of set partitions. They are related to Stirling and Bell numbers. They also occur in many applications, such as in the Faà di Bruno's fo ...
. This expression also leads to the following identity for generating functions: : \sum_^\infty e_k \,t^k = \exp\left(\sum_^\infty \frac p_k \,t^k \right). 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 ''s''''k''.


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 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 ( p_1^3 + 3 p_1 p_2 + 2 p_3 ),\\ h_4 &= \textstyle\frac1p_1^4 + \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 + \frac14p_4 &&= \textstyle\frac1 ( p_1^4 + 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 + 6 p_4 ),\\ &~~\vdots\\ h_k &= \sum_ \prod_^k \frac \end and so forth, in which there are only plus signs. In terms of the complete Bell polynomial, :h_k = \frac B_(p_1, 1! \, p_2, 2! \, p_3, \ldots, (k-1)! \, p_k ). These expressions correspond exactly to the
cycle index Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in ...
polynomials of the
symmetric group In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
s, if one interprets the power sums ''p''''i'' as indeterminates: the coefficient in the expression for ''h''''k'' of any monomial ''p''1''m''1''p''2''m''2...''p''''l''''m''''l'' is equal to the fraction of all permutations of ''k'' that have ''m''1 fixed points, ''m''2 cycles of length 2, ..., and ''m''''l'' cycles of length ''l''. Explicitly, this coefficient can be written as 1/N where N = \prod_^l (m_i!\,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''2+''m''4+.... It can be proved by considering the following inductive step: :\begin mf(m; m_1, \ldots, m_n) &= f(m-1; m_1 - 1, \ldots, m_n) + \cdots + f(m - n; m_1, \ldots, m_n - 1) \\ m_1\prod_^n \frac + \cdots + nm_n \prod_^n \frac &= m\prod_^n \frac \end By analogy with the derivation of the generating function of the e_n, we can also obtain the generating function of the h_n, in terms of the power sums, as: : \sum_^\infty h_k \,t^k = \exp\left(\sum_^\infty \frac \,t^k \right). This generating function is thus the plethystic exponential of p_1 t = (x_1 + \cdots + x_n)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: :\begin 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_3 e_1^2 + 5 e_2^2 e_1 - 5 e_4 e_1 - 5 e_3e_2 + 5 e_5,\\ p_6 &= e_1^6 - 6 e_2 e_1^4 + 6 e_3 e_1^3 + 9 e_2^2 e_1^2 - 6 e_4 e_1^2 - 12 e_3 e_2 e_1 + 6 e_5 e_1 - 2 e_2^3 + 3 e_3^2 + 6 e_4 e_2 - 6e_6. \end The first four formulas were obtained by
Albert Girard Albert Girard () (11 October 1595 in Saint-Mihiel, France − 8 December 1632 in Leiden, The Netherlands) was a French-born mathematician. He studied at the University of Leiden. He "had early thoughts on the fundamental theorem of algebra" and g ...
in 1629 (thus before Newton). The general formula (for all positive integers ''m'') is: :p_m = (-1)^m m \sum_ \frac \prod_^m (-e_i)^. This can be conveniently stated in terms of ordinary Bell polynomials as :p_m = (-1)^m m \sum_^m \frac \hat_(-e_1,\ldots,-e_), or equivalently as the
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
: : \begin \sum_^ (-1)^ p_k \frac & = \ln\left(1+e_1t+e_2t^2+e_3t^3+\cdots\right) \\ & = e_1 t - \frac\left(e_1^2-2e_2\right) t^2 + \frac\left(e_1^3-3e_1e_2+3e_3\right) t^3 + \cdots, \end which is analogous to the
Bell polynomial In combinatorial mathematics, the Bell polynomials, named in honor of Eric Temple Bell, are used in the study of set partitions. They are related to Stirling and Bell numbers. They also occur in many applications, such as in the Faà di Bruno's fo ...
''exponential'' generating function given in the previous subsection. The multiple summation formula above can be proved by considering the following inductive step: :\begin f(m;\; r_1,\ldots,r_n) = & f(m - 1;\; r_1 - 1, \cdots, r_n) + \cdots + f(m - n;\; r_1, \ldots, r_n - 1)\\ pt = & \frac(m - 1)(r_1 + \cdots + r_n - 2)! + \cdots \\ & \cdots + \frac(m - n)(r_1 + \cdots + r_n - 2)!\\ pt = & \frac\left _1(m - 1) + \cdots + r_n(m-n)\rightleft _1 + \cdots + r_n - 2\right\\ pt = & \frac\left (r_1 + \cdots + r_n) - m\rightleft _1 + \cdots + r_n - 2\right\\ pt = & \frac \end


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: :\begin 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 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 \prod_^l h_i^ is −(−1)''m''1+''m''2+''m''3+.... 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: :p_m = -\sum_ \frac \prod_^m (-h_i)^


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 In linear algebra, Cramer's rule is an explicit formula for the solution of a system of linear equations with as many equations as unknowns, valid whenever the system has a unique solution. It expresses the solution in terms of the determinants of ...
to find the solution for the final unknown. For instance taking Newton's identities in the form :\begin e_1 &= 1p_1,\\ 2e_2 &= e_1p_1 - 1p_2,\\ 3e_3 &= e_2p_1 - e_1p_2 + 1p_3,\\ & \,\,\,\vdots \\ ne_n &= e_p_1 - e_ p_2 + \cdots + (-1)^ne_1p_ + (-1)^p_n \end we consider p_1, -p_2, p_3, \ldots, (-1)^np_ and p_n as unknowns, and solve for the final one, giving :\begin p_n = &\begin 1 & 0 & \cdots & & e_1 \\ e_1 & 1 & 0 & \cdots & 2e_2 \\ e_2 & e_1 & 1 & & 3e_3 \\ \vdots & & \ddots & \ddots & \vdots\\ e_ & \cdots & e_2 & e_1 & ne_n \end\begin 1 & 0 & \cdots & \\ e_1 & 1 & 0 & \cdots \\ e_2 & e_1 & 1 & \\ \vdots & & \ddots & \ddots \\ e_ & \cdots & e_2 & e_1 & 1 \end^ \\ pt = &\begin 1 & 0 & \cdots & & e_1 \\ e_1 & 1 & 0 & \cdots & 2e_2 \\ e_2 & e_1 & 1 & & 3e_3 \\ \vdots & & \ddots &\ddots & \vdots \\ e_ & \cdots & e_2 & e_1 & ne_n \end \\ pt = &\begin e_1 & 1 & 0 & \cdots \\ 2e_2 & e_1 & 1 & 0 & \cdots \\ 3e_3 & e_2 & e_1 & 1 \\ \vdots & & & \ddots & \ddots \\ ne_n & e_ & \cdots & & e_1 \end. \end Solving for e_n instead of for p_n 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): :\begin e_n = \frac1&\begin p_1 & 1 & 0 & \cdots \\ p_2 & p_1 & 2 & 0 & \cdots \\ \vdots & & \ddots & \ddots \\ p_ & p_ & \cdots & p_1 & n-1 \\ p_n & p_ & \cdots & p_2 & p_1 \end \\ pt p_n = (-1)^&\begin h_1 & 1 & 0 & \cdots \\ 2h_2 & h_1 & 1 & 0 & \cdots \\ 3h_3 & h_2 & h_1 & 1 \\ \vdots & & & \ddots & \ddots \\ nh_n & h_ & \cdots & & h_1 \end \\ pt h_n = \frac1&\begin p_1 & -1 & 0 & \cdots \\ p_2 & p_1 & -2 & 0 & \cdots \\ \vdots & & \ddots & \ddots \\ p_ & p_ & \cdots & p_1 & 1 - n \\ p_n & p_ & \cdots & p_2 & p_1 \end. \end Note that the use of determinants makes that the formula for h_n has additional minus signs compared to the one for e_n, 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 h_n by taking the permanent of the matrix for e_n instead of the determinant, and more generally an expression for any
Schur polynomial In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in ''n'' variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In ...
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.


From the special case ''n'' = ''k''

One can obtain the ''k''-th Newton identity in ''k'' variables by substitution into : \prod_^k (t - x_i) = \sum_^k (-1)^ e_(x_1,\ldots,x_k)t^i as follows. Substituting ''x''''j'' for ''t'' gives :0= \sum_^k (-1)^ e_(x_1,\ldots,x_k)^i \quad\text1\leq j\leq k Summing over all ''j'' gives :0= (-1)^kke_k(x_1,\ldots,x_k)+\sum_^k(-1)^ e_(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''0 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.


Comparing coefficients in series

Another derivation can be obtained by computations in the ring of
formal power series In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sum ...
''R'', where ''R'' is Z 'x''1,..., ''x''''n'' the ring of polynomials in ''n'' variables ''x''1,..., ''x''''n'' over the integers. Starting again from the basic relation : \prod_^n (t - x_i) = \sum_^n (-1)^ a_k t^ and "reversing the polynomials" by substituting 1/''t'' for ''t'' and then multiplying both sides by ''t''''n'' to remove negative powers of ''t'', gives : \prod_^n (1- x_it) = \sum_^n (-1)^ a_k t^k. (the above computation should be performed in the field of fractions of ''R''; alternatively, the identity can be obtained simply by evaluating the product on the left side) Swapping sides and expressing the ''a''''i'' as the elementary symmetric polynomials they stand for gives the identity :\sum_^n (-1)^ e_k(x_1,\ldots,x_n) t^k=\prod_^n (1- x_it). One formally differentiates both sides with respect to ''t'', and then (for convenience) multiplies by ''t'', to obtain :\begin \sum_^n (-1)^k e_k(x_1,\ldots,x_n) t^k &= t \sum_^n \left -x_i) \prod\nolimits_(1 - x_jt)\right\ &= -\left(\sum_^n \frac\right) \prod\nolimits_^n (1 - x_jt)\\ &= -\left sum_^n \sum_^\infty(x_it)^j\rightleft sum_^n (-1)^\ell e_\ell(x_1,\ldots,x_n) t^\ell\right\ &= \left sum_^\infty p_j(x_1, \ldots, x_n)t^j\right\left sum_^n (-1)^ e_\ell(x_1, \ldots, x_n) t^\ell\right\\ \end where the polynomial on the right hand side was first rewritten as a
rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...
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 :\frac = X + X^2 + X^3 + X^4 + X^5 + \cdots, 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 e_k(x_1,\ldots,x_n) = \sum_^k (-1)^ p_j(x_1,\ldots,x_n)e_(x_1,\ldots,x_n), which gives the ''k''-th Newton identity.


As a telescopic sum of symmetric function identities

The following derivation, given essentially in (Mead, 1992), is formulated in the
ring of symmetric functions In algebra and in particular in algebraic combinatorics, the ring of symmetric functions is a specific limit of the rings of symmetric polynomials in ''n'' indeterminates, as ''n'' goes to infinity. This ring serves as universal structure in which ...
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''''i''''e''''k''−''i'' can be expressed in terms of the ''r''(''j'') with the first and last case being somewhat special. One has :p_ie_=r(i)+r(i+1)\quad\text1 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''0 = 1, giving trivially :p_ke_0=p_k=r(k). Finally the product ''p''1''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 one of the variables may come from the factor ''p''1; thus :p_1e_=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.


Combinatorial Proof

A short
combinatorial proof In mathematics, the term ''combinatorial proof'' is often used to mean either of two types of mathematical proof: * A proof by double counting. A combinatorial identity is proven by counting the number of elements of some carefully chosen set in ...
of Newton's Identities is given in (Zeilberger, 1984)


See also

*
Power sum symmetric polynomial In mathematics, specifically in commutative algebra, the power sum symmetric polynomials are a type of basic building block for symmetric polynomials, in the sense that every symmetric polynomial with rational coefficients can be expressed as a sum ...
* Elementary symmetric polynomial * Newton's inequalities *
Symmetric function In mathematics, a function of n variables is symmetric if its value is the same no matter the order of its arguments. For example, a function f\left(x_1,x_2\right) of two arguments is a symmetric function if and only if f\left(x_1,x_2\right) = f ...
* Fluid solutions, an article giving an application of Newton's identities to computing the characteristic polynomial of the
Einstein tensor In differential geometry, the Einstein tensor (named after Albert Einstein; also known as the trace-reversed Ricci tensor) is used to express the curvature of a pseudo-Riemannian manifold. In general relativity, it occurs in the Einstein field eq ...
in the case of a perfect fluid, and similar articles on other types of
exact solutions in general relativity In general relativity, an exact solution is a solution of the Einstein field equations whose derivation does not invoke simplifying assumptions, though the starting point for that derivation may be an idealized case like a perfectly spherical sh ...
.


References

* * * * * * * * * * * *


External links


Newton–Girard formulas
on MathWorld
A Matrix Proof of Newton's Identities
in Mathematics Magazine
Application on the number of real rootsA Combinatorial Proof of Newton's Identities
by Doron Zeilberger {{Isaac Newton Isaac Newton Group theory Invariant theory Linear algebra Mathematical identities Symmetric functions Algebraic combinatorics Galois theory