Newton's Identities

Recursively translate between power sums p_k and elementary symmetric polynomials e_k.

The idea

Let $x_1, \ldots, x_n$ be numbers. Write $p_k = \sum_i x_i^k$ for the $k$-th power sum, and $e_k$ for the $k$-th elementary symmetric polynomial, the sum of all products of $k$ distinct variables (so $e_1 = \sum_i x_i$, $e_2 = \sum_{i < j} x_i x_j$, and so on, with $e_n = x_1 x_2 \cdots x_n$, and $e_k = 0$ for $k > n$).

Theorem (Newton's identities).

For every $k \geq 1$, $p_k - e_1\, p_{k-1} + e_2\, p_{k-2} - \cdots + (-1)^{k-1} e_{k-1}\, p_1 + (-1)^{k}\, k\, e_k = 0.$

The $p_k$ and the $e_k$ are two summaries of the same numbers, and the identities translate between them. The $e_k$ come from polynomials: if $x_1, \ldots, x_n$ are the roots of a monic polynomial, its coefficients are the $e_k$ up to sign. The $p_k$ are often the quantities we can compute directly — for the eigenvalues of a matrix $M$, $p_k = \operatorname{tr}(M^k)$.

The identity for each $k$ involves $p_k$, the earlier power sums, and the $e_j$. Solving it for $p_k$ therefore computes $p_1, p_2, p_3, \ldots$ in turn from the $e_k$; solving it for $e_k$ instead runs the translation the other way.

Ways to work on it

• Walkthrough. Convert between power sums and elementary symmetric polynomials with Newton's identities.
• Practice. Recover a power sum from the elementary symmetric polynomials in two variables.
• Hardest. Run the identities three deep, then backward, and see how far they reach.

Not sure where to start? Take the ten-question placement test.