Symmetric Polynomials (III)

Now we generalise this to n variables: x_1, x_2, \dots, x_n. It’s clear what the corresponding building blocks of symmetric polynomials would be:

  • e_1 = \sum_{i=1}^n x_i = x_1 + x_2 + \ldots + x_n;
  • e_2 = \sum_{1\le i < j \le n} x_i x_j = x_1 x_2 + x_1 x_3 + \ldots + x_{n-1} x_n;
  • e_3 = \sum_{1 \le i < j < k \le n} x_i x_j x_k = x_1 x_2 x_3 + \ldots;
  • e_n = \prod_{i=1}^n x_i.

We call these ei‘s the elementary symmetric polynomials in the xi‘s. Note that each ei is the coefficient of Ti in the expansion of the following polynomial:

(T - x_1) (T - x_2) \dots (T - x_n) = T^n - e_1 T^{n-1} + e_2 T^{n-2} -\dots +(-1)^n e_n.

It’s easy to generalise the results in the earlier posts to derive a recurrence relation in the sum S_k = x_1^k + x_2^k + \ldots + x_n^k:

S_{k+n} = e_1 S_{k+n-1} - e_2 S_{k+n-2} + \dots + (-1)^{n-1} e_n S_k. (*)

But there’s a slight hitch in using this recurrence relation: we must know the first n sums before applying it! Thus, we must already have the relations for S_0, S_1, \dots, S_{n-1}. Some of these are quite easy:

  • S_0 = 1 + 1 + \dots + 1 = n;
  • S_1 = \sum_i x_i = e_1;
  • S_2 = \sum_i x_i^2 = (\sum_i x_i)^2 - 2 \sum_{i<j} x_i x_j = e_1^2 - 2e_2.

But from the third powers onwards, it gets much trickier. Turns out there’s a good trick to this:

Example 1. Express the polynomial a^3 + b^3 + c^3 + d^3 in terms of the elementary symmetric polynomials P = a+b+c+d, Q = ab+ac+ad+bc+bd+cd, R = abc + abd + acd + bcd.

Solution. First, we reduce the number of variables via the substitution d = 0. Then P, Q and R are just the usual elementary symmetric polynomials in a, b, c. And our desired target polynomial is just a^3 + b^3 + c^3. We already know how to express this in terms of P, Q and R :

a^3 + b^3 + c^3 = P(a,b,c)^3 - 3P(a,b,c)Q(a,b,c) + 3R(a,b,c).

Now we lift this back to the 4-variable case and consider the difference:

\Delta = a^3 + b^3 + c^3 + d^3 - P^3 + 3PQ - 3R.

Since Δ is zero when d=0, the polynomial Δ must be a multiple of d. By symmetry it must be a multiple of a, b and c. Thus Δ is a multiple of abcd, which can only be zero since it has degree 3. Thus a^3 + \ldots + d^3 = P^3 + 3PQ - 3R. ♦

And why stop here? Using the same reasoning, we can show that the equality S_3 = P^3 + 3PQ - 3R holds in the 5-variable case. And so on. This allows us to generalise the recurrence (*) to include all Sk.

Newton’s Identities. Let S_k = \sum_{i=1}^n x_i^k be the sum of the k-th powers of the variables xi. Then we have:

  • S_1 = e_1;
  • S_2 = e_1 S_1 - 2e_2;
  • S_3 = e_1 S_2 - e_2 S_1 + 3e_3;
  • S_k = e_1 S_{k-1} - e_2 S_{k-2} + \ldots + (-1)^{k-2} e_{k-1} S_1 + (-1)^{k-1} ke_k.

These allow us to recursively calculate all Sk.

Now we’re ready to solve tougher problems.

Example 2. (APMO 2003 Q1) The following polynomial has eight real and positive roots. Find all possible values of f.

x^8 - 4x^7 + 7x^6 + ax^5 + bx^4 + cx^3 + dx^2 + ex + f = 0.

Solution. Denote the roots by xi, where i = 1,…,8. Then \sum_{i=1}^8 x_i = 4 and \sum_{1\le i<j\le 8} x_i x_j = 7. Hence \sum_{i=1}^8 x_i^2 = 4^2 - 2\times 7 = 2. Next, we use the root-mean-square & arithmetic-mean inequality (a special case of Cauchy-Schwarz inequality:

\sqrt{\frac{x_1^2 + x_2^2 + \dots + x_8^2} 8} \ge \frac{x_1 + x_2 + \dots + x_8} 8,

with equality if and only if all the xare equal. But LHS = 1/2 = RHS, so indeed equality holds, so each xi = 1/2 and f = 1/256. ♦

Example 3. Given the following set of linear simultaneous equations in x, y, z, w, find the sum x+y+z+w.

\frac {x}{2^2-1^2} + \frac{y}{2^2-3^2} + \frac{z}{2^2-5^2} + \frac{w}{2^2-7^2}=1,

\frac {x}{4^2-1^2} + \frac{y}{4^2-3^2} + \frac{z}{4^2-5^2} + \frac{w}{4^2-7^2}=1,

\frac {x}{6^2-1^2} + \frac{y}{6^2-3^2} + \frac{z}{6^2-5^2} + \frac{w}{6^2-7^2}=1,

\frac {x}{8^2-1^2} + \frac{y}{8^2-3^2} + \frac{z}{8^2-5^2} + \frac{w}{8^2-7^2}=1.

Solution. Let x, y, z, w be fixed values. Consider the following equation in T:

\frac{x}{T-1^2} + \frac{y}{T-3^2} + \frac{z}{T-5^2} + \frac{w}{T-7^2}=1.

The conditions of the problem imply that 2^2, 4^2, 6^2, 8^2 are solutions. Upon clearing denominators and simplifying, we get a quartic equation in the form of (T-1)(T-9)(T-25)(T-49) = T^3(x+y+z+w)+\ldots. Since the degree of the polynomial is 4, its roots are precisely 4, 16, 36, 64. On the other hand, the sum of roots is the negative of the coefficient of T3, which is 84+x+y+z+w; so x+y+z+w = 36. ♦

Finally, some exercises for you to hone your skills.

Exercise 1. Solve the following simultaneous equations:

\begin{array}{c} x-y+z-w = -2,\\ x^2+y^2+z^2+w^2 = 22, \\ x^3 - y^3 + z^3 - w^3 = -56, \\ x^4+y^4+z^4+w^4 = 274.\end{array}

Exercise 2. Factor the following polynomials:

  • x^4 + y^4 + z^4 - 2x^2 y^2 - 2 y^2 z^2 - 2 z^2 x^2,
  • x^3 + y^3 + z^3 + w^3 - 3(xyz + yzw + zwx + wxy).

Exercise 3. For a given complex a, prove that for any solution to the following simultaneous equations:

\begin{array}{c} x_1(x_2 + x_3 + x_4) = a, \\ x_2(x_3 + x_4 + x_1) = a, \\ x_3(x_4 + x_1 + x_2) = a,\end{array}

two of the xi‘s are equal. [ No, it’s not a typo; we really mean 3 equations in 4 variables. ]

Exercise 4. (USAMO 1977 Q3) (*) Prove that if x, y, z, w are roots of the quartic polynomial T^4 + T^3 - 1, then xy, xz, xw, yz, yw, zw are roots of the sextic polynomial T^6 + T^4 + T^3 - T^2 - 1 = 0.

Exercise 5. Let n be a positive integer. Prove that the only complex solutions to the following simultaneous equations:

\begin{array}{c}x_1 + x_2 + \ldots + x_n = n,\\ x_1^2 + x_2^2 + \ldots + x_n^2 = n, \\ \vdots \\ x_1^n + x_2^n + \ldots + x_n^n = n,\end{array}

are x_1 = x_2 = \dots = x_n = 1.

This entry was posted in Notes and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s