Newton's identities

Template:Short description 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 Template:Mvar in one variable, they allow expressing the sums of the Template:Mvar-th powers of all roots of Template:Mvar (counted with their multiplicity) in terms of the coefficients of Template:Mvar, 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.

Mathematical statement

Formulation in terms of symmetric polynomials

Let Template:Math be variables, denote for Template:Math by Template:Math the Template:Mvar-th power sum:

$p_k(x_1,\dots ,x_n)=\sum _{i=1}^n{x}_i^k=x_1^k+\cdots +x_n^k,$

and for Template:Math denote by Template:Math the elementary symmetric polynomial (that is, the sum of all distinct products of Template:Mvar distinct variables), so

$\begin{array}{cc}{e}_0(x_1,\dots ,x_n)& =1,\\ e_1(x_1,\dots ,x_n)& =x_1+x_2+\cdots +x_n,\\ e_2(x_1,\dots ,x_n)& =\sum _{1\le i<j\le n}{x}_i{x}_j,\\ & ⋮\\ e_n(x_1,\dots ,x_n)& =x_1{x}_2\cdots x_n,\\ e_k(x_1,\dots ,x_n)& =0,\text{for}k>n.\end{array}$

Then Newton's identities can be stated as

$k{e}_k(x_1,\dots ,x_n)=\sum _{i=1}^k(-1{)}^{i-1}{e}_{k-i}(x_1,\dots ,x_n)p_i(x_1,\dots ,x_n),$

valid for all Template:Math, where the left-hand size is zero for Template:Math.

Concretely, one gets for the first few values of Template:Mvar:

$\begin{array}{cc}{e}_1(x_1,\dots ,x_n)& =p_1(x_1,\dots ,x_n),\\ 2e_2(x_1,\dots ,x_n)& =e_1(x_1,\dots ,x_n)p_1(x_1,\dots ,x_n)-p_2(x_1,\dots ,x_n),\\ 3e_3(x_1,\dots ,x_n)& =e_2(x_1,\dots ,x_n)p_1(x_1,\dots ,x_n)-e_1(x_1,\dots ,x_n)p_2(x_1,\dots ,x_n)+p_3(x_1,\dots ,x_n).\end{array}$

The form and validity of these equations do not depend on the number Template:Mvar of variables (although the point where the left-hand side becomes 0 does, namely after the Template:Mvar-th identity), which makes it possible to state them as identities in the ring of symmetric functions. In that ring one has

$\begin{array}{cc}{e}_1& =p_1,\\ 2e_2& =e_1{p}_1-p_2=p_1^2-p_2,\\ 3e_3& =e_2{p}_1-e_1{p}_2+p_3=\frac{1}{2}{p}_1^3-\frac{3}{2}{p}_1{p}_2+p_3,\\ 4e_4& =e_3{p}_1-e_2{p}_2+e_1{p}_3-p_4=\frac{1}{6}{p}_1^4-p_1^2{p}_2+\frac{4}{3}{p}_1{p}_3+\frac{1}{2}{p}_2^2-p_4,\end{array}$

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

$\begin{array}{cc}{p}_1& =e_1,\\ p_2& =e_1{p}_1-2e_2=e_1^2-2e_2,\\ p_3& =e_1{p}_2-e_2{p}_1+3e_3=e_1^3-3e_1{e}_2+3e_3,\\ p_4& =e_1{p}_3-e_2{p}_2+e_3{p}_1-4e_4=e_1^4-4e_1^2{e}_2+4e_1{e}_3+2e_2^2-4e_4,\\ & ⋮\end{array}$

In general, we have

$p_k(x_1,\dots ,x_n)=(-1{)}^{k-1}k{e}_k(x_1,\dots ,x_n)+\sum _{i=1}^{k-1}(-1{)}^{k-1+i}{e}_{k-i}(x_1,\dots ,x_n)p_i(x_1,\dots ,x_n),$

valid for all Template:Math.

Also, one has

$p_k(x_1,\dots ,x_n)=\sum _{i=k-n}^{k-1}(-1{)}^{k-1+i}{e}_{k-i}(x_1,\dots ,x_n)p_i(x_1,\dots ,x_n),$

for all Template:Math.

Application to the roots of a polynomial

The polynomial with roots Template:Math may be expanded as

$\prod _{i=1}^n(x-x_i)=\sum _{k=0}^n(-1{)}^k{e}_k{x}^{n-k},$

where the coefficients $e_k(x_1,\dots ,x_n)$ are the symmetric polynomials defined above. Given the power sums of the roots

$p_k(x_1,\dots ,x_n)=\sum _{i=1}^n{x}_i^k,$

the coefficients of the polynomial with roots $x_1,\dots ,x_n$ may be expressed recursively in terms of the power sums as

$\begin{array}{cc}{e}_0& =1,\\ -e_1& =-p_1,\\ e_2& =\frac{1}{2}(e_1{p}_1-p_2),\\ -e_3& =-\frac{1}{3}(e_2{p}_1-e_1{p}_2+p_3),\\ e_4& =\frac{1}{4}(e_3{p}_1-e_2{p}_2+e_1{p}_3-p_4),\\ & ⋮\end{array}$

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 of a matrix $𝐀$ (in particular when $𝐀$ is the companion matrix of the polynomial), the roots $x_i$ are the eigenvalues of the matrix, counted with their algebraic multiplicity. For any positive integer $k$, the matrix ${𝐀}^k$ has as eigenvalues the powers $x_i^k$, and each eigenvalue $x_i$ of $𝐀$ contributes its multiplicity to that of the eigenvalue $x_i^k$ of ${𝐀}^k$. Then the coefficients of the characteristic polynomial of ${𝐀}^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 $𝐀$, is given by its trace:

$$p_k=\mathrm{tr}({𝐀}^k).$$

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

This computation requires computing the traces of matrix powers ${𝐀}^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, every matrix satisfies its characteristic polynomial, and a simple transformation allows to find the adjugate matrix in NC.

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.

Relation with Galois theory

For a given Template:Mvar, the elementary symmetric polynomials Template:Math for Template:Math form an algebraic basis for the space of symmetric polynomials in Template:Math: every polynomial expression in the Template:Math 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 $t^n+{\sum }_{k=1}^n(-1{)}^k{a}_k{t}^{n-k}$ with all coefficients Template:Math considered as free parameters, this means that every symmetric polynomial expression Template:Math in its roots can be expressed instead as a polynomial expression Template:Math 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 Template:Math 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 Template:Mvar 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 Template:Math the complete homogeneous symmetric polynomial (that is, the sum of all monomials of degree Template:Mvar), 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

$k{h}_k=\sum _{i=1}^k{h}_{k-i}{p}_i,$

valid for all Template:Math. Contrary to Newton's identities, the left-hand sides do not become zero for large Template:Mvar, and the right-hand sides contain ever more non-zero terms. For the first few values of Template:Mvar, one has

$\begin{array}{cc}{h}_1& =p_1,\\ 2h_2& =h_1{p}_1+p_2,\\ 3h_3& =h_2{p}_1+h_1{p}_2+p_3.\end{array}$

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 Template:Math of symmetric functions with rational coefficients:

$\begin{array}{cc}{e}_1& =p_1,\\ e_2& =\frac{1}{2}{p}_1^2-\frac{1}{2}{p}_2& & =\frac{1}{2}(p_1^2-p_2),\\ e_3& =\frac{1}{6}{p}_1^3-\frac{1}{2}{p}_1{p}_2+\frac{1}{3}{p}_3& & =\frac{1}{6}(p_1^3-3p_1{p}_2+2p_3),\\ e_4& =\frac{1}{24}{p}_1^4-\frac{1}{4}{p}_1^2{p}_2+\frac{1}{8}{p}_2^2+\frac{1}{3}{p}_1{p}_3-\frac{1}{4}{p}_4& & =\frac{1}{24}(p_1^4-6p_1^2{p}_2+3p_2^2+8p_1{p}_3-6p_4),\\ & ⋮\\ e_n& =(-1{)}^n\sum _{\genfrac{}{}{0ex}{}{m_1+2m_2+\cdots +n{m}_n=n}{m_1\ge 0,\dots ,m_n\ge 0}}\prod _{i=1}^n\frac{(-p_i{)}^{m_i}}{m_i!i^{m_i}}\end{array}$

and so forth. The general formula can be conveniently expressed as

$e_k=\frac{(-1{)}^k}{k!}{B}_k(-p_1,-1!p_2,-2!p_3,\dots ,-(k-1)!p_k),$

where the Template:Math is the complete exponential Bell polynomial. This expression also leads to the following identity for generating functions:

$\sum _{k=0}^{\mathrm{\infty }}{e}_k{t}^k=\exp \left(\sum _{k=1}^{\mathrm{\infty }}\frac{(-1{)}^{k+1}}{k}{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 Template:Math by Template:Math and each Template:Math by Template:Math.

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{array}{cc}{h}_1& =p_1,\\ h_2& =\frac{1}{2}{p}_1^2+\frac{1}{2}{p}_2& & =\frac{1}{2}(p_1^2+p_2),\\ h_3& =\frac{1}{6}{p}_1^3+\frac{1}{2}{p}_1{p}_2+\frac{1}{3}{p}_3& & =\frac{1}{6}(p_1^3+3p_1{p}_2+2p_3),\\ h_4& =\frac{1}{24}{p}_1^4+\frac{1}{4}{p}_1^2{p}_2+\frac{1}{8}{p}_2^2+\frac{1}{3}{p}_1{p}_3+\frac{1}{4}{p}_4& & =\frac{1}{24}(p_1^4+6p_1^2{p}_2+3p_2^2+8p_1{p}_3+6p_4),\\ & ⋮\\ h_k& =\sum _{\genfrac{}{}{0ex}{}{m_1+2m_2+\cdots +k{m}_k=k}{m_1\ge 0,\dots ,m_k\ge 0}}\prod _{i=1}^k\frac{p_i^{m_i}}{m_i!i^{m_i}}\end{array}$

and so forth, in which there are only plus signs. In terms of the complete Bell polynomial,

$h_k=\frac{1}{k!}{B}_k(p_1,0!p_2,1!p_3,\dots ,(k-1)!p_k).$

These expressions correspond exactly to the cycle index polynomials of the symmetric groups, if one interprets the power sums Template:Math as indeterminates: the coefficient in the expression for Template:Math of any monomial Template:Math is equal to the fraction of all permutations of Template:Mvar that have Template:Math fixed points, Template:Math cycles of length 2, ..., and Template:Math cycles of length Template:Mvar. Explicitly, this coefficient can be written as $1/N$ where $N={\prod }_{i=1}^l(m_i!i^{m_i})$; this Template:Mvar is the number permutations commuting with any given permutation Template:Pi 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 Template:Pi, namely Template:Math.

It can be proved by considering the following inductive step:

$\begin{array}{cc}mf(m;m_1,\dots ,m_n)& =f(m-1;m_1-1,\dots ,m_n)+\cdots +f(m-n;m_1,\dots ,m_n-1)\\ m_1\prod _{i=1}^n\frac{1}{i^{m_i}{m}_i!}+\cdots +n{m}_n\prod _{i=1}^n\frac{1}{i^{m_i}{m}_i!}& =m\prod _{i=1}^n\frac{1}{i^{m_i}{m}_i!}\end{array}$

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 _{k=0}^{\mathrm{\infty }}{h}_k{t}^k=\exp \left(\sum _{k=1}^{\mathrm{\infty }}\frac{p_k}{k}{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{array}{cc}{p}_1& =e_1,\\ p_2& =e_1^2-2e_2,\\ p_3& =e_1^3-3e_2{e}_1+3e_3,\\ p_4& =e_1^4-4e_2{e}_1^2+4e_3{e}_1+2e_2^2-4e_4,\\ p_5& =e_1^5-5e_2{e}_1^3+5e_3{e}_1^2+5e_2^2{e}_1-5e_4{e}_1-5e_3{e}_2+5e_5,\\ p_6& =e_1^6-6e_2{e}_1^4+6e_3{e}_1^3+9e_2^2{e}_1^2-6e_4{e}_1^2-12e_3{e}_2{e}_1+6e_5{e}_1-2e_2^3+3e_3^2+6e_4{e}_2-6e_6.\end{array}$

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

The general formula (for all positive integers Template:Mvar) is:

$p_m=(-1{)}^{m}m\sum _{\genfrac{}{}{0ex}{}{r_1+2r_2+\cdots +m{r}_m=m}{r_1\ge 0,\dots ,r_m\ge 0}}\frac{(r_1+r_2+\cdots +r_m-1)!}{r_1!r_2!\cdots r_m!}\prod _{i=1}^m(-e_i{)}^{r_i}.$

This can be conveniently stated in terms of ordinary Bell polynomials as

$p_m=(-1{)}^{m}m\sum _{k=1}^m\frac{1}{k}{\hat{B}}_{m,k}(-e_1,\dots ,-e_{m-k+1}),$

or equivalently as the generating function:

$\begin{array}{cc}\sum _{k=1}^{\mathrm{\infty }}(-1{)}^{k-1}{p}_k\frac{t^k}{k}& =\ln (1+e_{1}t+e_2{t}^2+e_3{t}^3+\cdots )\\ & =e_{1}t-\frac{1}{2}(e_1^2-2e_2)t^2+\frac{1}{3}(e_1^3-3e_1{e}_2+3e_3)t^3+\cdots ,\end{array}$

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:

$\begin{array}{cc}f(m;r_1,\dots ,r_n)=& f(m-1;r_1-1,\cdots ,r_n)+\cdots +f(m-n;r_1,\dots ,r_n-1)\\ =& \frac{1}{(r_1-1)!\cdots r_n!}(m-1)(r_1+\cdots +r_n-2)!+\cdots \\ & \cdots +\frac{1}{r_1!\cdots (r_n-1)!}(m-n)(r_1+\cdots +r_n-2)!\\ =& \frac{1}{r_1!\cdots r_n!}[r_1(m-1)+\cdots +r_n(m-n)][r_1+\cdots +r_n-2]!\\ =& \frac{1}{r_1!\cdots r_n!}[m(r_1+\cdots +r_n)-m][r_1+\cdots +r_n-2]!\\ =& \frac{m(r_1+\cdots +r_n-1)!}{r_1!\cdots r_n!}\end{array}$

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{array}{cc}{p}_1& =+h_1,\\ p_2& =-h_1^2+2h_2,\\ p_3& =+h_1^3-3h_2{h}_1+3h_3,\\ p_4& =-h_1^4+4h_2{h}_1^2-4h_3{h}_1-2h_2^2+4h_4,\\ p_5& =+h_1^5-5h_2{h}_1^3+5h_2^2{h}_1+5h_3{h}_1^2-5h_3{h}_2-5h_4{h}_1+5h_5,\\ p_6& =-h_1^6+6h_2{h}_1^4-9h_2^2{h}_1^2-6h_3{h}_1^3+2h_2^3+12h_3{h}_2{h}_1+6h_4{h}_1^2-3h_3^2-6h_4{h}_2-6h_1{h}_5+6h_6,\end{array}$

and so on. Apart from the replacement of each Template:Math by the corresponding Template:Math, 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 }_{i=1}^l{h}_i^{m_i}$ is Template:Math. In particular the above description of the absolute value of the coefficients applies here as well.

The general formula (for all non-negative integers Template:Mvar) is:

$p_m=-\sum _{\genfrac{}{}{0ex}{}{r_1+2r_2+\cdots +m{r}_m=m}{r_1\ge 0,\dots ,r_m\ge 0}}\frac{m(r_1+r_2+\cdots +r_m-1)!}{r_1!r_2!\cdots r_m!}\prod _{i=1}^m(-h_i{)}^{r_i}$

Expressions as determinants

One can obtain explicit formulas for the above expressions in the form of determinants, by considering the first Template:Mvar 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. For instance taking Newton's identities in the form

$\begin{array}{cc}{e}_1& =1p_1,\\ 2e_2& =e_1{p}_1-1p_2,\\ 3e_3& =e_2{p}_1-e_1{p}_2+1p_3,\\ & ⋮\\ n{e}_n& =e_{n-1}{p}_1-e_{n-2}{p}_2+\cdots +(-1{)}^n{e}_1{p}_{n-1}+(-1{)}^{n-1}{p}_n\end{array}$

we consider $p_1,-p_2,p_3,\dots ,(-1{)}^n{p}_{n-1}$ and $p_n$ as unknowns, and solve for the final one, giving

$\begin{array}{cc}(-1{)}^{n-1}{p}_n=& \left|\begin{array}{ccccc}1& 0& \cdots & & e_1\\ e_1& 1& 0& \cdots & 2e_2\\ e_2& e_1& 1& & 3e_3\\ ⋮& & \ddots & \ddots & ⋮\\ e_{n-1}& \cdots & e_2& e_1& n{e}_n\end{array}\right|{\left|\begin{array}{cccc}1& 0& \cdots & \\ e_1& 1& 0& \cdots \\ e_2& e_1& 1& \\ ⋮& & \ddots & \ddots \\ e_{n-1}& \cdots & e_2& e_1& 1\end{array}\right|}^{-1}\\ p_n=(-1{)}^{n-1}& \left|\begin{array}{ccccc}1& 0& \cdots & & e_1\\ e_1& 1& 0& \cdots & 2e_2\\ e_2& e_1& 1& & 3e_3\\ ⋮& & \ddots & \ddots & ⋮\\ e_{n-1}& \cdots & e_2& e_1& n{e}_n\end{array}\right|\\ =& \left|\begin{array}{cccc}{e}_1& 1& 0& \cdots \\ 2e_2& e_1& 1& 0& \cdots \\ 3e_3& e_2& e_1& 1\\ ⋮& & & \ddots & \ddots \\ n{e}_n& e_{n-1}& \cdots & & e_1\end{array}\right|.\end{array}$

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{array}{cc}{e}_n=\frac{1}{n!}& \left|\begin{array}{cccc}{p}_1& 1& 0& \cdots \\ p_2& p_1& 2& 0& \cdots \\ ⋮& & \ddots & \ddots \\ p_{n-1}& p_{n-2}& \cdots & p_1& n-1\\ p_n& p_{n-1}& \cdots & p_2& p_1\end{array}\right|\\ p_n=(-1{)}^{n-1}& \left|\begin{array}{cccc}{h}_1& 1& 0& \cdots \\ 2h_2& h_1& 1& 0& \cdots \\ 3h_3& h_2& h_1& 1\\ ⋮& & & \ddots & \ddots \\ n{h}_n& h_{n-1}& \cdots & & h_1\end{array}\right|\\ h_n=\frac{1}{n!}& \left|\begin{array}{cccc}{p}_1& -1& 0& \cdots \\ p_2& p_1& -2& 0& \cdots \\ ⋮& & \ddots & \ddots \\ p_{n-1}& p_{n-2}& \cdots & p_1& 1-n\\ p_n& p_{n-1}& \cdots & p_2& p_1\end{array}\right|.\end{array}$

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 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.

Proofs via generating functions

We can show the relationships between Template:Math, Template:Math, and Template:Math via the generating functions $$\begin{array}{cc}E(t)& =\sum _{k=0}^{\mathrm{\infty }}(-1{)}^k{e}_k(x_1,\dots ,x_n)t^k=\prod _{j=1}^n(1-x_{j}t)\\ P(t)& =\sum _{k=1}^{\mathrm{\infty }}{p}_k(x_1,\dots ,x_n)t^k=\sum _{j=1}^n(x_{j}t+(x_{j}t{)}^2+\dots )=\sum _{j=1}^n\frac{x_{j}t}{1-x_{j}t}\\ H(t)& =\sum _{k=0}^{\mathrm{\infty }}{h}_k(x_1,\dots ,x_n)t^k=\prod _{j=1}^n(1+x_{j}t+(x_{j}t{)}^2+\dots )=\prod _{j=1}^n\frac{1}{1-x_{j}t}.\end{array}$$

E and H

Equality of the coefficient of Template:Tmath on each side of the equation $E(t)H(t)=1$ gives us that $$\sum _{j=0}^{min(n,k)}{e}_j{h}_{k-j}={\delta }_{k0},$$ where we take advantage of the fact that Template:Tmath for Template:Tmath, and where Template:Math is the Kronecker delta function, which is 1 when Template:Tmath and is 0 otherwise. That is, the sum on the left hand side equals zero except in the trivial case that Template:Tmath.

E and P

The equation $$\frac{1}{E(t)}\frac{dE(t)}{dt}=\frac{d}{dt}\ln E(t)=\sum _{j=1}^n\frac{d}{dt}\ln (1-x_{j}t)=\sum _{j=1}^n\frac{-x_j}{1-x_{j}t}=-\frac{P(t)}{t}$$ gives us $$-t\frac{dE(t)}{dt}=P(t)E(t),$$ and equality of the coefficient of Template:Tmath on each side of that equation gives $$(-1{)}^{k+1}k{e}_k=\sum _{j=0}^{min(n,k-1)}(-1{)}^j{e}_j{p}_{k-j},$$ where we have used that Template:Tmath.

Another relationship can be found by repeatedly differentiating the right-hand side of the equation $$P(t)=-t\frac{1}{E(t)}\frac{dE(t)}{dt}$$ to get its Taylor series around Template:Tmath; its Template:Mvar-th term equals Template:Tmath.

H and P

Plugging $$\frac{1}{H(t)}\frac{dH(t)}{dt}=-\frac{1}{E(t)}\frac{dE(t)}{dt}$$ into the relationship between Template:Tmath and Template:Tmath gives $$t\frac{dH(t)}{dt}=P(t)H(t),$$ and equality of the coefficient of Template:Tmath on each side of that equation gives $$k{h}_k=\sum _{j=0}^{k-1}{h}_j{p}_{k-j}.$$

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 Template:Math, and define the symmetric function Template:Math for Template:Math as the sum of all distinct monomials of degree Template:Mvar obtained by multiplying one variable raised to the power Template:Mvar with Template:Math distinct other variables (this is the monomial symmetric function Template:Math where Template:Mvar is a hook shape Template:Math. In particular Template:Math; for Template:Math the description would amount to that of Template:Math, but this case was excluded since here monomials no longer have any distinguished variable. All products Template:Math can be expressed in terms of the Template:Math with the first and last case being somewhat special. One has

$p_i{e}_{k-i}=r_k(i)+r_k(i+1)\text{for }1<i<k$

since each product of terms on the left involving distinct variables contributes to Template:Math, while those where the variable from Template:Math already occurs among the variables of the term from Template:Math contributes to Template:Math, and all terms on the right are so obtained exactly once. For Template:Math one multiplies by Template:Math, giving trivially

$p_k{e}_0=p_k=r_k(k).$

Finally the product Template:Math for Template:Math gives contributions to Template:Math like for other values Template:Math, but the remaining contributions produce Template:Mvar times each monomial of Template:Math, since any one of the variables may come from the factor Template:Math; thus

$p_1{e}_{k-1}=k{e}_k+r_k(2).$

The Template:Mvar-th Newton identity is now obtained by taking the alternating sum of these equations, in which all terms of the form Template:Math cancel out.

Combinatorial proof

A short combinatorial proof of Newton's identities was given by Doron Zeilberger in 1984.

See also

• Power sum symmetric polynomial
• Elementary symmetric polynomial
• Newton's inequalities
• 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.

References

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite conference
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book

External links

• Newton–Girard formulas on MathWorld
• A Matrix Proof of Newton's Identities in Mathematics Magazine
• Application on the number of real roots
• A Combinatorial Proof of Newton's Identities by Doron Zeilberger