I was browsing through the Art Of Problem Solving website and came across this:
"Any symmetric sum can be written as a Polynomial of the elementary symmetric sum functions, for example
$x^3 + y^3 + z^3 = (x + y + z)(x^2 + y^2 + z^2 - xy - yz - xz) + 3xyz = S^3_1 - 3S_1S_2 + 3S_3$ (*)
This is often used to solve systems of equations involving power sums, combined with Vieta's formulas."
However, I do not understand how the expression (*) above was derived and, I also do not understand how it can be used to solve systems of equations involving power sums. Please someone should help with a detailed explanation and also an example on how it can be used to solve systems of equations involving power sums.
There is a simple algorithm of Gauss to rewrite a symmetric polynomial $f(x,y)$ as polynomial in the elementary symmetric polynomials $\,s_1\! = x+y,\ \ s_2 = xy.\,$ Namely if $\,f\,$ has highest degree term $\ c x^a y^b $ in the lex (dictionary) order (i.e. $\,(a,b) > (c,d)\, $ if $\,a >c,\,$ or $\,a= c\,$ and $\, b > d)\,$ then cancel the highest term of $\,f\,$ by subtracting $\,cs_1^{a-b} s_2^b,\, $ then recurse on what remains.
Let's perform Gauss's algorithm on the simpler example $\, f = x^3 + y^3.\, $ Since $\,(3,0) > (0,3)\,$ the highest degree monomial is $\ 1\cdot x^\color{#0a0}3y^\color{#c00}0,\, $ so we subtract $\ 1\cdot s_1^{\color{#0a0}3-\color{#c00}0} s_2^\color{#c00}0\, =\, (x+y)^3 $ yielding
$$\ x^3+y^3\ -\ (x+y)^3\, =\ {-}3x^2 y - 3x y^2$$
By $(2,1)>(1,2),\, $ RHS has high term $\,-3x^{\color{#0a0}2} y^\color{#c00}1$ so we subtract $\, {-}3 s_1^{\color{#0a0}2-\color{#c00}1} s_2^\color{#c00}1 =\, -3(x\!+\!y)(xy)$
$$\ x^3+y^3\, -\ (x+y)^3\, +\ 3(x+y)(xy) \ =\ 0$$
So the algorithm terminates, yielding $\ f = s_1^3 - 3s_1 s_2.\ $
Exactly the same algorithm works for polynomials in any number of variables: for the high term $\,c\, x_1^{\large a_1}\cdots x_k^{\large a_k}\,$ we subtract $\,c\, s_1 ^{\large a_1-a_2} s_2^{\large a_2-a_3}\cdots s_{k-1}^{\large a_{k-1}-a_k}s_k^{\large a_k},\,$ e.g. in your trivariate example, for high term $\,c\, x^a y^b z^c\, $ we subtract $\,c\, s_1^{a-b} s_2^{b-c} s_3^c.\,$ This reduces such problems to rote mechanical computation, i.e. no guesswork is required to solve such problems, only simple polynomial arithmetic. The algorithm yields a constructive interpretation of the Fundamental Theorem of Symmetric Polynomials, that every symmetric polynomial has a unique representation as a polynomial in the elementary symmetric polynomials.
Gauss's algorithm may be viewed as a special case of Gröbner basis methods (which may be viewed both as a multivariate generalization of the (Euclidean) polynomial division algorithm, as well as a nonlinear generalization of Gaussian elimination for linear systems of equation). Gauss's algorithm is the earliest known use of such a lexicographic order for term-rewriting (now mechanized by the Grobner basis algorithm and related methods).