Sergei Yakovenko's blog: on Math and Teaching

Monday, April 25, 2011

Lectures 5-6, April 26-May 3, 2011

Filed under: lecture,Rothschild Course "Symmetry" — Sergei Yakovenko @ 3:59
Tags: ,

Symmetric polynomials in several variables

Because of the numerous mathematical formulas and no figures, the notes for these lectures are provided in the pdf format.

For your convenience, the list of sections is supplied.

  1. Multi-index notation
  2. Definition of symmetric polynomials in several variables
  3. Construction of symmetric polynomials: averaging over the group. Young tableaux
  4. Elementary symmetric polynomials
  5. Main theorem on representation of symmetric polynomials: formulation
  6. Symmetry break and lexicographic order of monomials. Proof of the Main theorem
  7. Power sums, a.k.a Newton sums a.k.a. symmetric powers
  8. Generating functions and representation of symmetric powers
  9. Miscellaneous problems concerning symmetric polynomials

Enjoy the notes and let me know if any problems arise.

Sunday, April 10, 2011

Lecture 4, April 12, 2011

Filed under: lecture,Rothschild Course "Symmetry",Uncategorized — Sergei Yakovenko @ 2:09
Tags:

Symmetric polynomials

Definition
A polynomial p\in\mathbb R[x,y] is symmetric, if p(x,y)=p(y,x) (the equality is understood as the polynomial identity).

Examples

  1. p(x,y)\equiv1
  2. x+y
  3. x^2+y^2,\ xy
  4. x^3+y^3,\ x^2y+xy^2
  5. x^4+y^4,\ x^3y+xy^3,\ x^2y^2

Some of them can be expressed through others.

Problem
Let k\ge 2. Prove that the sum of powers s_k(x,y)=x^k+y^k can be expressed through
\sigma_0(x,y)=1,\ \sigma_1(x,y)=x+y,\sigma_2(x,y)=xy.

Solution
The first case can be seen outright: s_2=(x+y)^2-2xy=\sigma_1^2-2\sigma_2.

To check the general case, multiply x^k+y^k by x+y: we get (x^k+y^k)(x+y)=(x^{k+1}+y^{k+1})+xy(x^{k-1}+y^{k-1}). This identity can be rewritten as follows:

s_k\sigma_1=s_{k+1}+\sigma_2 s_{k-1}.

One can resolve this identity and obtain the recursive (inductive) formula s_{k+1}=\sigma_1 s_k-\sigma_2 s_{k-1}. With the initial conditions s_0=2,\ s_1=\sigma_1, this allows to compute all s_k one by one.

Theorem
Any symmetric polynomial in two variables can be expressed as a polynomial in \sigma_1,\sigma_2.

Proof
A polynomial is symmetric if and only if each its homogeneous component (collection of terms of the same degree) is also symmetric. Thus it is sufficient to prove the theorem only for homogeneous symmetric polynomials.

A homogeneous polynomial in two variables p(x,y)=a_0 x^n + a_1 x^{n-1}y+\cdots+a_{n-1}xy^{n-1}+a_n y^n is symmetric if and only if its string of coefficients (a_0,a_1,\dots,a_{n-1},a_n) is palindromic: a_0=a_n,\ a_1=a_{n-1} etc. In this case the terms can be rearranged as follows:

p(x,y)=a_0(x^n+y^n)+a_1 (xy)(x^{n-2}+y^{n-2})+ a_2 (xy)^2(x^{n-4}+y^{n-4})+\cdots\\=a_0 s_n+a_1\sigma_1 s_{n-2}+a_2\sigma_1^2 s_{n-4}+\cdots.

Since each sum of powers s_k(x,y) is already expressed as a polynomial in \sigma_1,\sigma_2, we obtain the required expression for the homogeneous polynomial p.

Uniqueness of the representation
Can a symmetric polynomial admit two different representations via \sigma_1,\sigma_2? It is sufficient to study only the trivial case of identically zero polynomial (why?).

Theorem
If a polynomial p(\sigma_1,\sigma_2) is identically zero as polynomial in x,y, then it is identically zero also as a polynomial in \sigma_1,\sigma_2.

The idea of the proof is to introduce the notion of a “leading term” for polynomials in two variables x,y and for polynomials p(\sigma_1,\sigma_2) in the variables \sigma_1,\sigma_2 such a way that the leading terms can be easily compared for p and its expansion.

Example (bad)
Declare for a polynomial p(x,y)=\sum_{i+j=0}^d a_{ij}x^i y^j the leading term be the monomial of the highest degree i+j (with nonzero coefficient) and, in case there are several such terms, the one whose degree i in x is the highest.

How to find the leading term of a polynomial p(\sigma_1,\sigma_2)=\sum_{k+l=0}^N A_{kl}\sigma_1^k\sigma_2^l? One has to find the monomial with the highest value of k+2l, but what next? in the case there are several such monomials with the nonzero coefficients, all of them will contribute to the leading term of the expansion, so theoretically can cancel each other and as a result we cannot guarantee that the outcome will be nonzero.

One has to be more smart in defining what is the leading term.

Example (good)
Declare the leading term of a polynomial p(x,y)=\sum_{i+j=0}^d a_{ij}x^i y^j the monomial of highest degree i in x with a nonzero coefficient. In case there are several such monomials, choose the one which has largest degree also in y. (Such order is called “lexicographical”: it is used to arrange words in the dictionaries. The order is alphabetic in the initial letter, and all words starting with the same letter, are arranged alphabetically in the second letter. If necessary, the process can continue further).

How to determine the leading term of the composite polynomial p(\sigma_1,\sigma_2)=\sum_{k+l=0}^N A_{kl}\sigma_1^k\sigma_2^l? Clearly, one has to choose the terms of the highest total degree k+l (which will give the degree in x). In case there are several nonzero terms with the same value k+l, clearly, the largest degree in y will contribute the term with the largest value of l (why?). Such term is only one: the corresponding coefficient A_{kl} will give the coefficient before the leading term in the expansion of p.

Proof of the uniqueness theorem
Assume that the polynomial p(\sigma_1,\sigma_2)=\sum_{k+l=0}^N A_{kl}\sigma_1^k\sigma_2^l is nonzero, i.e., not all A_{kl} are zeros. Choose the coefficient with the largest value of k+l, and in case there are several such, take the one with the largest l. As follows from the above (good) Example, the lexicographically leading term of the expansion will have the same nonzero coefficient, thus after expansion we get nonzero polynomial, contrary to our assumption.

Problems for homework/class
Solve the following systems of equations, using their symmetry.

Problem
Compose a quadratic equation, whose roots are cubes of the equation x^2+6x+10=0.

Solution
Denoting the roots x_1,x_2, we know that \sigma_1(x_1,x_2)=-6,\ \sigma_2(x_1,x_2)=10. It is required to find an equation z^2+\alpha z+\beta=0 whose roots will be z_i=x_i^3. By the same Vieta formulas, -\alpha=x_1^3+x_2^3, \beta = x_1^3x_2^3. Expressing these symmetric functions of x_1,x_2 via \sigma_1,\sigma_2, we obtain the answer without solving explicitly any of the equations.

Generalizing this trick, we come to the following conclusion: any rational symmetric function of the roots of a quadratic equation z^2+\alpha z+\beta=0 can be expressed as a rational function of \alpha,\beta (without radicals).

Further observations

  1. Since the degree of \sigma_2 is 2, it enters in the expression of symmetric polynomials of degree d in the degree not exceeding d/2. This in many cases simplifies factorization of symmetric polynomials into symmetric factors.
  2. Palindromic polynomials in one variable, having the form q(x)=a_0 x^n+a_1 x^{n-1}+\cdots +a_{n-1}x+a_n with a_i=a_{n-i} for all i=0,1,\dots,n can be reduced to a symmetric form.If the degree n=2k is even, then after division by x^k we obtain a rational function which is in fact a polynomial of degree k in the variable \sigma=x+\frac1x (prove it!).

    If n=2k+1 is odd, then q(x) is divisible by x+1, i.e., q(x)=(1+x)p(x), and the quotient p is a palindromic polynomial of an even degree. Indeed, the divisibility follows from the fact that q(-1) is an alternating sum of the coefficients a_i, which cancel each other because of the parity together with palindromic condition, thus q(-1)=0.

    The second assumption follows from the following obvious characterization: q(x) is palindromic, if and only if x^n q(1/x)\equiv q(x). Applied to the representation q(x)=(x+1)p(x), we see that x^{n}q(1/x)=x^n (1+\frac 1x)p(1/x)=x^{n-1}(1+x)p(1/x)=(x+1)p(x), which implies that p is palindromic.

    This observation allows to reduce degree of palindromic polynomial equations by half.

Theme: Rubric. Get a free blog at WordPress.com

Follow

Get every new post delivered to your Inbox.