Wednesday, September 09, 2009

Elementary Symmetric Polynomials

If we look at Girard's Theorem, we see that:

xn + a1xn-1 + a2xx-2 + ... + an = (x - x1)*...*(x - xn)

Now if we solve for each ai in terms of xi, we can restate the equation in terms of the elementary symmetric polynomials. In today's blog, I will show a proof of this using induction.


Definition 1: Elementary Symmetric Polynomials

s1, ..., sn such that:

s1 = x1 + ... + xn

s2 = x1x2 + ... + xn-1xn

s3 = x1x2x3 + ... + xn-2xn-1xn

...

sn = x1x2*...*xn

So, let get down to showing the theorem.

Theorem 1: Restatement of Girard's Theorem in terms of the Elementary Symmetric Polynomials:

Xn - s1Xn-1 + s2Xn-2 - ... + (-1)nsn = (X - x1)(X - x2)*...*(X-xn)

Proof:

(1) xn + a1xn-1 + a2xx-2 + ... + an = (x - x1)*...*(x - xn) [see Girard's Theorem]

(2) Assume n=1

(3) x + a1 = x - x1 = x - s1

(4) Assume that the theorem holds true up until n.

(5) So that we have:

Xn - (x1 + ... + xn)Xn-1 + (x1x2 + ... + xn-1xn)Xn-2 - ... + (-1)n(x1x2*...*xn) = (X - x1)(X - x2)*...*(X-xn)

(6) Multiplying (X - xn+1) to both sides gives us:

(X - x1)(X - x2)*...*(X-xn)*(X - xn+1) = (X - xn+1)[Xn - (x1 + ... + xn)Xn-1 + (x1x2 + ... + xn-1xn)Xn-2 - ... + (-1)n(x1x2*...*xn)] =

[Xn+1 - (x1 + ... + xn)Xn + (x1x2 + ... + xn-1xn)Xn-1 - ... + (-1)nX(x1x2*...*xn)] - [Xn(xn+1) - (xn+1)(x1 + ... + xn)Xn-1 + (xn+1)(x1x2 + ... + xn-1xn)Xn-2 - ... + (-1)n(x1x2*...*xn*xn+1)]

= Xn+1 - (x1 + ... + xn + xn+1)Xn + (x1x2 + ... + xnxn+1)Xn-1 ... + (-1)n+1(x1*...*xn+1) =

= Xn+1 - s1Xn + s2Xn-1 - ... + (-1)n+1sn+1

QED

No comments :