Newton's Identities: Symmetric Polynomials

It is very easy to build an equation that has a certain set of solutions. If we wanted to build an equation where the solutions are 1,2,3,4,5 then all we need to do is multiply out the following:

(x - 1)(x - 2)(x - 3)(x -4)(x - 5)=0

If we carry out the multiplication, we can be sure that the result is an algebraic equation of power n=5 where we have the following:

ax⁵ + bx⁴ + cx³ + dx² + e = 0

if x = 1, 2, 3, 4, or 5. We can figure out a,b,c,d,e by carrying out the multiplication.

Let's generalize this idea. Let's assume that the roots are r₁, r₂, ..., r_n. Further, let's call each coefficient of the final result a₁, a₂, ..., a_n.

Then we have:

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

If xⁿ has a coefficient, then we can divide the entire equation by a₀ to get the above result.

We call a polynomial that results in this way, a symmetric polynomial. The idea is that we can switch any r_i with any r_j and it doesn't change the resulting polynomial.

Definition 1: Symmetric Polynomial

Let P(x₁, x₂, ..., x_n) be a polynomial that consists of n variables. P(x₁, x₂, ..., x_n) is said to be a symmetric polynomial if any two of these variables can be interchanged without changing the value of the polynomial.

Examples:

The following polynomials are symmetric.

P(x₁, x₂) = (x₁)³ + (x₂)³ - 7.

P(x₁, x₂) = 4x₁x₂

P(x₁, x₂, x₃) = x₁x₂x₃x₂ - 2x₁x₃ - 2x₂x₃

The following polynomial is not:

P(x₁,x₂) = x₁ - x₂

Now, looking at the above equation again:

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

We can see that:

a₁ = -r₁ + -r₂ + ... + -r_n

We know this since there are n ways to get a value of x^n-1. And they are:

-r₁*x*x*x*...*x -r₂*x*x*x*...*x - ... -r_n*x*x*x*...*x

We can also see that a_n = (-r₁)*(-r₂)*(-r₃)*...*(-r_n)

since this is only way to multiply the values together to get x⁰. We can see that there exactly C(n,0)=1 ways to include x⁰. There are C(n,1)=n ways to to include only x¹ and C(n,2) = ways to include x², etc.

Indeed, in each case we can see that a_i is the sum of C(n,i) different terms (see Lemma 3, here for details on C(n,r) if needed):

a₂ = (-r₁)*(-r₂) + (-r₁)*(-r₃) + ... + (-r_n-1)*(-r_n) a₃ = (-r₁)*(-r₂)*(-r₃) + ... + (-r_n-2)*(-r_n-1)*(-r_n) ... a_n-1 = (-r₁)*...*(-r_n-1) + (-r₂)*...*(-r_n)

Each of these terms is itself a polynomial. They are called the elementary symmetric polynomials σ_i.

Definition 2: Kth Elementary Symmetric Polynomials

A kth elementary symmetric polynomial is defined as:



So, we have:

σ_k = (-1)^ka_k where σ_k is called the kth elementary symmetric polynomial in r₁, ..., r_n

In my next blog, I will show that for every symmetric polynomial in r₁, ..., r_n can be expressed as an elementary symmetric polynomial in r₁, ..., r_n

References

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