Elementary symmetric polynomial ($e_k(x_1,\dots ,x_n)$)

The $k$th elementary symmetric polynomial adds every product obtained by choosing $k$ distinct positions from $x_1,\dots ,x_n$:The conventions are $e_0=1$ and $e_k=0$ for $k>n$. The positions must be distinct, but their values may coincide. Each permutation of the variables merely rearranges the summands, so this is a symmetric polynomial.

For $x_1=1$, $x_2=2$, $x_3=3$, we obtain $e_1=1+2+3=6$, $e_2=1\cdot 2+1\cdot 3+2\cdot 3=11$, and $e_3=1\cdot 2\cdot 3=6$. Expanding the product givesIn general, ${\prod }_{i=1}^n(z-x_i)=z^n-e_1{z}^{n-1}+e_2{z}^{n-2}-\cdots +(-1{)}^n{e}_n$. Thus the coefficients of a monic polynomial collect elementary symmetric polynomials of its roots of a polynomial, with alternating signs. These are the Vieta formulas.^[ref]

Every symmetric polynomial over a commutative ring has a unique expression as a polynomial in the elementary symmetric polynomials.

Newton's identities let two different summaries of the same polynomial roots talk to each other. Elementary symmetric polynomials record products of distinct root positions; power sums record sums of individual powers, $p_r={\sum }_{i=1}^n{x}_i^r$. Either can be easier to obtain in a particular problem. The identities turn one into the other, often avoiding any need to find the individual polynomial roots.

Write $e_0=1$ and $e_m=0$ for $m>n$. For every positive integer $m$, the identity isIt is a polynomial identity over the integers, so it remains true on substitution in any commutative ring. To solve it for $e_m$ by division, however, $m$ must have a multiplicative inverse. Over a field of characteristic zero, the first $n$ power sums recover every elementary symmetric polynomial. The same recovery works when the positive characteristic of a field is greater than $n$; small characteristic needs care.^[ref]

The first three relations are $e_1=p_1$, $2e_2=e_1{p}_1-p_2$, and $3e_3=e_2{p}_1-e_1{p}_2+p_3$. When division by two and three is permitted, this becomesFor the three roots $1,2,3$, their power sums are $p_1=6$, $p_2=14$, and $p_3=36$. The formulas give $e_2=(36-14)/2=11$ and $e_3=(216-252+72)/6=6$, recovering the polynomial $z^3-6z^2+11z-6$ from aggregate data.

The beauty is that the summaries do not depend on the order of the polynomial roots. In symmetric polynomials, one can work with quantities that survive every relabeling; in linear algebra, traces of matrix powers give the same kind of aggregate information about eigenvalues. The identities convert those summaries into coefficients of a characteristic polynomial.

A short derivation packages the identities into a formal power series. Let $E(t)={\prod }_i(1+x_{i}t)={\sum }_{m\ge 0}{e}_m{t}^m$. Since its constant coefficient is one, it has an inverse as a formal power series, and its formal derivative satisfiesMultiply by $E(t)$ and compare the coefficient of $t^{m-1}$. This gives Newton's identities without a convergence assumption or division by $m$. The division issue arises only when using them to recover $e_m$. The logarithmic-derivative approach is also developed in Newton's Identities (January 2019 notes) by Milan Mossé (§4, pp. 6–8).

The alternate name Newton-Girard identities recalls Albert Girard's earlier work. A modern historical account credits formulas through sixth powers to Albert Girard in 1629 and discusses their later appearance in Isaac Newton's Arithmetica universalis.^[ref] This citation refers to that account; the original historical editions have not been inspected here.

For the monic polynomial $q(z)=z^n-e_1{z}^{n-1}+\cdots +(-1{)}^n{e}_n$, its root power sums satisfyEach root obeys $q(x_i)=0$. Multiplying that equation by $x_i^{m-n}$ and summing over root positions proves the recurrence relation. The first $n$ power sums are initialized by Newton's identities; their later values require only this fixed-order recurrence. For $q(z)=z^3-6z^2+11z-6$, it gives $p_4=6\cdot 36-11\cdot 14+6\cdot 6=98$. Directly, $1^4+2^4+3^4=98$. No new root-solving step is needed.^[ref]

For a complex $n\times n$ matrix $A$, $\mathrm{tr}(A^k)$ is the sum of the $k$th powers of its eigenvalues, counted with algebraic multiplicity. This does not require diagonalizability: a similar upper triangular matrix has the eigenvalues on its diagonal, and taking powers raises those diagonal entries to their corresponding powers. Newton's identities therefore recover its characteristic polynomial from the first $n$ such traces.

For the Jordan block $A=\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$, $\mathrm{tr}A=4$ and $\mathrm{tr}(A^2)=8$. Hence $e_1=4$ and $e_2=(4^2-8)/2=4$, giving $\det (zI-A)=z^2-4z+4=(z-2{)}^2$. The repeated eigenvalue is recovered even though this matrix is not diagonalizable.^[ref]

Exact reconstruction does not promise that small errors in power sums produce proportionally small errors in individual polynomial roots. For two roots, let $p_1=2$ and $p_2=2+\delta$. Newton's identities give $e_1=2$ and $e_2=1-\delta /2$, so the monic polynomial is $(z-1{)}^2-\delta /2$. Its polynomial roots are $1\pm \sqrt{\delta /2}$. A zero value of $\delta$ gives a multiple root; positive $\delta$ splits it into two real roots, and negative $\delta$ splits it into a complex-conjugate pair.

With $\delta =2{\epsilon }^2>0$, the second power sum changes by $2{\epsilon }^2$ while each polynomial root moves by $\epsilon$. The ratio $1/(2\epsilon )$ grows without bound as $\epsilon$ tends to zero. Thus coefficients can stay close while individual root locations are more sensitive. This is a reason to distinguish recovering coefficients by Newton's identities from subsequently approximating the polynomial roots.

The polynomial identities remain true in positive characteristic of a field, but recovering elementary symmetric polynomials by division can fail. In the prime field ${\mathbb{F}}_2$ of characteristic two, the root lists $(0,0)$ and $(1,1)$ have the same power sum zero for every positive exponent: $0^k+0^k=0$ and $1^k+1^k=0$. Their monic polynomials differ, however: $z^2$ and $(z-1{)}^2=z^2+1$. Thus even all positive power sums need not determine the polynomial when its degree meets the characteristic. The relation $2e_2=e_1{p}_1-p_2$ becomes $0=0$ and supplies no value for $e_2$.