Elementary Symmetric Polynomials

The Fundamental Theorem of Algebra tells us that if you take any polynomial of degree n, there are n solutions. This theorem guarantees us that there are two sides to any polynomial:

xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = (x - r₁)(x - r₂)*...*(x-r_n)

where r_i are real or complex numbers.

If you want to build a polynomial that has the n solutions { r₁, ..., r_n) just multiply (x - r₁)*...*(x - r_n). The result will be a polynomial of the form:

xⁿ + a₁x^n-1 + ... + a_n

On the other hand, if you have a polynomial of order n, the fundamental theorem tells us that n solutions exist but it doesn't tell us how to find them. Niels Henrik Abel and then later Evariste Galois proved that there is no general method for finding solutions for polynomials of degree 5 or greater. Earlier, Girolamo Cardano and Lodovico Ferari had found equations for the cubic and the quartic equation.

In today's blog, I will discuss how the elementary symmetric polynomials emerge from the discussion of polynomials and their roots.

Definition 1: Elementary Symmetric Polynomials σ_k

The elementary symmetric polynomial σ_k is the sum of all possible k-way products from a set of n variables { r₁, r₂, ..., r_n } such that:

σ_k = r₁*...*r_k + ... + r_n-k+1*...*r_n

Here are some examples:

σ₁ = r₁ + r₂ + ... + r_n

σ₂ = r₁*r₂ + r₂*r₃ + ... + r_n-1*r_n

In each of these cases, we can see that there C(n,k) terms in the elementary polynomial for σ_k. [C(n,k) = n!/(n-k)!k!. For proof that each σ_k consists of C(n,k) terms, see here]

The reason that these polynomials are called symmetric is because you could switch the values of any two of the variables and the result doesn't change.

The reason that these polynomials are called elementary symmetric polynomials is because it turns out that all symmetric polynomials can be restated in terms of these elementary symmetric polynomials. For a proof of this important fact, see here.

Elementary symmetric polynomials characterize the relationship between the roots of a polynomial and the coefficients that make up the polynomial.

Lemma 1:

For any given polynomial of the form:

xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = 0

σ_k = (-1)^k*a_k

Proof:

(1) From the Fundamental Theorem of Algebra (see here), we know that there exists r₁, r₂, ..., r_n such that:

xⁿ + a₁x^n-1 + ... + a_n-1x + a_n = (x - r₁)*(x - r₂)*...*(x - r_n)

(2) Now, each coefficient a_i is the sum of all multiplications that involve exactly (n-i) x's and (i) r's. In other words, it is a sum of C(n,i) terms since there are C(n,i) combinations possible [see here for review of C(n,i)]

(3) In other words:

a_ix^n-i = (-r₁)*...*(-r_i)*x*... + (-r₁)*...*(-r_i+1)*x*.. + ...

(4) Dividing both sides by x^n-i gives us:

a_i = (-r₁)*...*(-r_i) + (-r₁)*...*(-r_i+1) + ...

(5) We can also pull out (-1)ⁱ so that we have:

a_i = (-r₁)*...*(-r_i) + (-r₁)*...*(-r_i+1) + ... =

= (-1)ⁱ(r₁)*...*(r_i) + (-1)ⁱ(r₁)*...*(r_i+1) + ... =

= (-1)ⁱ[ (r₁)*...*(r_i) + (r₁)*...*(r_i+1) + ... ]

(6) Now based on the definition for σ_k, we have:

a_i = (-1)ⁱ[ σ_i ]

which is the same as:

σ_i = (-1)ⁱ(a_i)

QED

References

• "Elementary Symmetric Polynomials", Wikipedia
• Harold M. Edwards, Galois Theory, Springer, 1984.