# reduction algorithm for symmetric polynomials

We give here an algorithm for reducing a symmetric polynomial^{} into a polynomial^{} in the elementary symmetric polynomials.

We define the height of a monomial^{} ${x}_{1}^{{e}_{1}}\mathrm{\cdots}{x}_{n}^{{e}_{n}}$ in $R[{x}_{1},\mathrm{\dots},{x}_{n}]$ to be ${e}_{1}+2{e}_{2}+\mathrm{\cdots}+n{e}_{n}$. The height of a polynomial is defined to be the maximum height of any of its monomial terms, or 0 if it is the zero polynomial^{}.

Let $f$ be a symmetric polynomial. We reduce $f$ into elementary symmetric polynomials by induction^{} on the height of $f$. Let $c{x}_{1}^{{e}_{1}}\mathrm{\cdots}{x}_{n}^{{e}_{n}}$ be the monomial term of maximal height in $f$. Consider the polynomial

$$g:=f-c{s}_{1}^{{e}_{n}-{e}_{n-1}}{s}_{2}^{{e}_{n-1}-{e}_{n-2}}\mathrm{\cdots}{s}_{n-1}^{{e}_{2}-{e}_{1}}{s}_{n}^{{e}_{1}}$$ |

where ${s}_{k}$ is the $k$–th elementary symmetric polynomial in the $n$ variables ${x}_{1},\mathrm{\dots},{x}_{n}$. Then $g$ is a symmetric polynomial of lower height than $f$, so by the induction hypothesis, $g$ is a polynomial in ${s}_{1},\mathrm{\dots},{s}_{n}$, and it follows immediately that $f$ is also a polynomial in ${s}_{1},\mathrm{\dots},{s}_{n}$.

Title | reduction algorithm for symmetric polynomials |
---|---|

Canonical name | ReductionAlgorithmForSymmetricPolynomials |

Date of creation | 2013-03-22 12:11:17 |

Last modified on | 2013-03-22 12:11:17 |

Owner | djao (24) |

Last modified by | djao (24) |

Numerical id | 6 |

Author | djao (24) |

Entry type | Proof |

Classification | msc 05E05 |

Classification | msc 12F10 |

Defines | height |