Sunday, July 15, 2007

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:

xn + a1xn-1 + ... + an-1x + an = (x - r1)(x - r2)*...*(x-rn)

where ri are real or complex numbers.

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

xn + a1xn-1 + ... + an

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 { r1, r2, ..., rn } such that:

σk = r1*...*rk + ... + rn-k+1*...*rn

Here are some examples:

σ1 = r1 + r2 + ... + rn

σ2 = r1*r2 + r2*r3 + ... + rn-1*rn

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:

xn + a1xn-1 + ... + an-1x + an = 0

σk = (-1)k*ak


(1) From the Fundamental Theorem of Algebra (see here), we know that there exists r1, r2, ..., rn such that:

xn + a1xn-1 + ... + an-1x + an = (x - r1)*(x - r2)*...*(x - rn)

(2) Now, each coefficient ai 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:

aixn-i = (-r1)*...*(-ri)*x*... + (-r1)*...*(-ri+1)*x*.. + ...

(4) Dividing both sides by xn-i gives us:

ai = (-r1)*...*(-ri) + (-r1)*...*(-ri+1) + ...

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

ai = (-r1)*...*(-ri) + (-r1)*...*(-ri+1) + ... =

= (-1)i(r1)*...*(ri) + (-1)i(r1)*...*(ri+1) + ... =

= (-1)i[ (r1)*...*(ri) + (r1)*...*(ri+1) + ... ]

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

ai = (-1)i[ σi ]

which is the same as:

σi = (-1)i(ai)