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 e_i‘s the elementary symmetric polynomials in the x_i‘s. Note that each e_i is the coefficient of Tⁱ 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 S_k.

Newton’s Identities. Let $S_k = \sum_{i=1}^n x_i^k$ be the sum of the k-th powers of the variables x_i. 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 S_k.

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 x_i, 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 x_iare equal. But LHS = 1/2 = RHS, so indeed equality holds, so each x_i = 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 T³, 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 x_i‘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$ .

Symmetric Polynomials (III)

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages

Symmetric Polynomials (III)

Share this:

Like this:

Related

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages