First read the writeup on symmetric polynomial
s to see the
statement of The Fundamental Theorem. Before we start the proof
it's worth noting that it is constructive, in the sense that it
actually gives an algorithm that you can carry out in any
Proof: Let f(x1,...,xn) be a symmetric
polynomial. We have to express it in terms on the elementary
symmetric polynomials s1,...,sn.
Well our polynomial f is a sum of monomials, that is terms
of the form a(x1)i1....(xn)in
where a is a nonzero scalar (from our field) and
(i1,...,in) are all natural numbers.
First of all we have to locate the biggest monomial. To do this we
use the lexicographic ordering on n-tuples of natural numbers. If we have two monomials
then we say that p < q iff
(i1,...,in) < (i1,...,in).
Suppose then that p is the largest monomial in f with
respect to this order. Since f is symmetric we must have that
is also a monomial of f for any permutation
s in the symmetric group. Because we chose p to be the largest
we can see from this that we must have that
i1 >= i2 >=...>= in.
Next we want to find a first approximation to f made from symmetric
polynomials. So let
Now considering all the monomials that occur
in g we can see that one of these monomials is
which is exactly equal to the largest monomial of f.
Now consider the polynomial f-g, it is symmetric and its largest
monomial is smaller than the largest monomial of f. So we are
done by induction.