First read the writeup on
symmetric polynomials 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
particular case.
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
p=ax1i1....axnin
and q=bx1j1....xnjn
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
s(p)=axs(1)i1....xs(n)in
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
g=as1i1-i2s2i2-i3....snin.
Now considering all the monomials that occur
in g we can see that one of these monomials is
ax1i1-i2(x1x2)i2-i3...(x1...xn)in
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.