Symmetric Polynomials

We introduced 𝕂[x] the ring of polynomials in one indeterminate with coefficients over 𝕂. This definition can be extended to a case in which the coefficients vary over a commutative ring (e.g: ℤ) rather than a field. In this case we have a ring of polynomials with coefficients in a ring R and will be indicated by R[x].

5.10.1 Definition. The ring R of polynomials in n indeterminates and coefficients over the field 𝕂 is defined inductively in the following way

R₁ ≡ 𝕂[x], R_n ≡ R_{n − 1}[x]

we write R_n ≡ 𝕂[x₁, x₂, ..., x_n]. □

So a polynomials with n indeterminates is thought as a polynomial in one variable, with coefficients in the ring of the polynomials with n-1 variables. An element of 𝕂[x,y] = (𝕂[x])[y] is of the kind

∑ⁿ_{_j=0} f_jy^j, f_j ∈ 𝕂[x]

like for example

∑²_{_j=0} (∑¹_{_i=0} a_ijxⁱ)y^j = (a₀₀ + a₁₀x) + (a₀₁ + a₁₁x)y + (a₀₂ + a₁₂ x)y² =
a₀₀ + a₁₀x + a₀₁y + a₀₂y² + a₁₁ xy + a₁₂ xy².

We can represent in general the elements of 𝕂[x₁, x₂, ..., x_n] in the form

f(x₁, x₂, ..., x_n) = ∑ a_{i₁i₂...i_n} x₁^i₁ x₂^i₂ ... x_n^i_n

They are added and multiplied in the familiar way, making use of the associative, commutative, and distributive laws of addition and multiplication.

The degree of the indeterminate x_i is the highest exponent that occurs in the polynomial with a nonzero coefficient.

Given the monomial

x₁^h₁, x₂^h₂, ..., x_n^h_n

the degree of the polynomials is the integer h₁ + h₂ + ... + h_n. The degree of the polynomials f(x₁, x₂, ..., x_n) is defined as the highest degree of its monomials.

A polynomial in general can have different highest degree monomials. It is thus relevant to order the monomials of a polynomial. The common order is the lexicographic ordering: In practice, given an ordered alphabet of variables x₁, x₂,..., x_n you can sort all the monomials by first considering the exponent of x₁, x₂,..., x_n, then the exponent of x₂ and so on, until a difference is found between the exponents. At this point, the monomial is considered minor for which the exponent is minor. In symbols

αx₁^h₁x₂^h₁ ⋅⋅⋅ x₃^h_n, α ∈ 𝕂, h_i ≥ 0

and

βx₁^k₁x₂^k₁ ⋅⋅⋅ x₃^k_n, β ∈ 𝕂, k_i ≥0

two mononomers of the polynomial f(x₁, x₂,.., x_n). We say that

αx₁^h₁x₂^h₁ ⋅⋅⋅ x_n^h_n < βx₁^k₁x₂^k₁ ⋅⋅⋅ x_n^k_n

if the least integer m, for which h_i ≠ k_i, such that h_m < k_m.

For example

x₁⁴x₂²x₃ ≻ x₁⁴x₂x₃³ (same total degree, equal x₁ exponent, greater x₂ exponent)

x₁⁴x₂²x₃³ ≺ x₁⁴x₂³x₃³ (smaller total degree)

We introduce now an important class of polynomials: symmetric polynomials. Given the definition of permutation we have the following

5.10.2 Definition. A polynomial f(x₁,x₂,..., x_n) ∈ 𝕂[x₁, x₂, ..., x_n] is said symmetric if for any permutation of its indeterminate it remains invariant. □

For example the polynomials in 𝕂[x₁, x₂, ..., x₃]

2x₁ + 2x₂ + 2x₃ −3x₁² −3x₂² −3x₃²

x₁x₂³ + x₂x₁³ + x₁x₃ + x₃x₁³ + x₂x₃³ + x₃x₂³

instead the following are not symmetric polynomials

x₁² + x₂² − x₃², x₁ + 3x₂ + 7x₃

The following symmetric polynomial are said elementary symmetric polynomials (or functions) in 𝕂[x₁, x₂, ..., x_n]

σ₁(x₁, x₂,..., x_n) = x₁ + x₂ + ... + x_n = ∑ⁿ_{_i=1} x_i

σ₁(x₁, x₂,..., x_n) = x₁ x₂ + x₁ x₃ + ... + x_n−1 x_n = ∑ⁿ_{_{i≤i < j ≤ n}} x_ix_j

σ₁(x₁,x₂,..., x_n) = x₁ x₂x₃ + x₁ x₂ x₄ + ...+ x_n−2 x_n−1 x_n = ∑ⁿ_{_{i ≤ i < j < k ≤ n}} x_ix_jx_k

...

σ₁(x₁,x₂,...,x_n) = x₁x₂⋅⋅⋅x_n

We shall show, these functions connenct coefficients and roots of a polynomial equation in one variable.

Consider the equation

f(t) = tⁿ + a₁tⁿ⁻¹ + ... + a_n−1t + a_n = 0 (5.10.1)

Let r₁, r₂, r_n be its roots, we can write

f(t) = (t − r₁) (t − r₂) ⋅⋅⋅ (t − r_n) (5.10.2)

expanding the factored form of 5.10.2 and setting the coefficients equal to those of (5.10.2), we obtain the following relations

a₁ = −(r₁ + r₂ + r_n)

a₂ = r₁r₂ + r₁x₃ + ... + r₁x_n + r₂x₃ + ... + r_n−1 r_n

a₃ = −(r₁r₂x₃ + r₁r₂x₄ + ... + r_n−2x_n−1 x_n)

...

a_n = (−1)ⁿ r₁x₂⋅⋅⋅r_n

The above relations are known as the Viète formulas: they relate the coefficients of a polynomial to sums and products of its roots. We examine the case n = 2.

Vieta's Formula. Quadratic Equations. Let r₁ and r₂ be the roots of the quadratic equation ax² + bx + c = 0. Then the two identities

−b/a = r₁ + r₂ c/a = r₁r₂

both hold.

Proof. Write ax² + bx + c = a(x − r₁) (x − r₂) = ax² −ax(r₁ + r²) + ar₁r₂. From which the relations above must be satisfied. □

In general we have σ_k = (−1)^k σ_k (r₁, r₂, ..., r_n), hence the coefficients of every monic polynomial of one indeterminate with coefficients in a field, are the elementary symmetric functions of its roots.

The set S of all symmetric polynomials in n variables with coefficients in 𝕂[x₁, x₂, ..., x_n]. Every polynomial f(σ₁, σ₂, ..., σ_n) of 𝕂[x₁, x₂, ..., x_n] can be expressed in terms of elementary symmetric polynomials and thus contained in S. We have the following inclusions

We make this precise in the next theorem, showing that the first inclusion is an equality.

𝕂[σ₁, σ₂, ..., σ_n] ⊆ S ⊂ 𝕂[x₁, x₂, ..., x_n]

5.10.3 Theorem. (Fundamental theorem of symmetric polynomials). Every symmetric polynomial f(x₁,x₂,..., x_n) of 𝕂[x₁, x₂, ..., x_n] can be expressed uniquely in terms of elementary symmetric polynomials with coefficients in 𝕂.

Proof. Let

αx₁^h₁x₂^h₁ ⋅⋅⋅ x_n^h_n

the highest degree monomial function occurring in the polynomial function using the lexicographic ordering. Then necessarily h₁ ≥ h₂, ≥ ..., ≥ h_n; If for example we had h₁ < h₂, we could exchange x₁ with x₂, obtaining the monomial

αx₂^h₁x₁^h₁ ⋅⋅⋅ x_n^h_n = αx₁^h₁x₂^h₁ ⋅⋅⋅ x_n^h_n

which is again a monomial of f(x₁,x₂, ..., x_n), being f by hypothesis symmetric.

Consider now the symmetric polynomial (in x₁, x₂, ..., x_n)

φ₁ = ασ₁^h₁−h₂σ₂^h₂−h₃ ⋅⋅⋅ σ_n−1^{h_n−1−h_n} σ_n^h_n

The leading term of φ₁ is given by the product of α for the leading terms of each σ_i raised to the power h₁ − h₂, h₂−h₃, .., ecc. respectively.

αx₁^h₁−h₂(x₁x₂)^h₂−h₃ ⋅⋅⋅(x₁x₂⋅⋅⋅x_n)^h_n = αx₁^h₁x₂^h₂ ⋅⋅⋅ x_n^h_n

This shows that f and φ₁ have the same leading term. Hence f₁ = f — φ₁ has a strictly smaller leading term according to the lexicographic ordering. Note that f₁ is symmetric, since f and g are. Now repeat this process, starting with f₁ instead of f. Since f₁ is symmetric, it has a leading term with coefficient α₁ and exponents b₁ > ··· > b_n. As above, this will give an expression φ₂ in the elementary symmetric polynomials such that f₁ and φ₂ have the same leading term.

This process will terminate if we find some m with f_m = 0, for the zero polynomial has no leading term. If, on the other hand, we never had f_m = 0, then the above would give an infinite sequence of nonzero polynomials with strictly decreasing leading terms. But we showed above that there are only finitely many monomials strictly smaller than the leading term off. Hence the above process must terminate.

So we've proven that f − φ₁−φ₂ − ... −φ_m is the zero polynomial, hence

f = φ₁ + φ₂ + ... + φ_m

Each φ_i, is a product of the σ, to various powers, which proves that f is a polynomial in the elementary symmetric polynomials.

Uniqueness. The uniqueness of the expression follows from the algebraic independence of the elementary symmetric functions.

To prove the uniqueness of the expression we have to prove that if a polynomial (symmetric) can be written in two forms as

∑ α_{i₁i₂...i_n} σ₁^i₁ σ₂^i₂ ... σ_n^i_n = ∑ β_{i₁i₂...i_n} σ₁^i₁ σ₂^i₂ ... σ_n^i_n

then α_{i₁i₂...i_n} = β_{i₁i₂...i_n} for all index i_j, j=1,...,n. It is sufficient to prove that if φ(σ₁,...,σ_n) = 0 then all coefficients of φ(σ₁,...,σ_n) are zero i.e. the polynomial φ(z₁,...,z_n) in the indeterminates z_i is the zero polynomial. This is equivalent to say that the σ_i are algebrically independent. In other words we have to prove that

φ(z₁,...,z_n) ≠ 0 ⇒ φ(σ₁,...,σ_n) ≠ 0

Let αz₁^h₁z₂^h₁ ⋅⋅⋅ z_n^h_n be the leading term (using the lexicographic order), of φ(z₁,...,z_n). Substitute z_i = σ_i in φ(z₁,..., z_n). By expanding σ_i in terms of the x_i (since σ_i is a function of x) the monomial αz₁^h₁z₂^h₁ ⋅⋅⋅ z_n^h_n becomes the following polynomial in the x_i:

α_{i₁i₂...i_n} σ₁^i₁ σ₂^i₂ ... σ_n^i_n = a(x₁ + x₂ + ... + x_n)^h₁(x₁x₂ + ...)^h₂ ⋅⋅⋅ (x₁⋅⋅⋅x_n)^h_n

The leading term of this polynomial is

ax₁^{h₁ + h₂ + ... + h_n} x₂^{h₁ + h₂ + ... + h_n}x_n^h_n

which has a non-zero coefficient and cannot vanish by combination with any other monomial. This completes the proof.□

This theorem asserts that the ring of all symmetric polynomials S, in n indeterminates is

S = 𝕂[x₁, x₂, ..., x_n]

Example 5.10.4 Write the symmetric polynomial in 𝕂[x₁, x₂, x₃]

f = ∑_{_{i ≠ j}} x_i²x_j = x₁²x₂ + x₁²x₃ + x₂²x₁ + x₂²x₃ + x₃²x₁ + x₃²x₂

in terms of elementary symmetric polynomials σ_k.

Solution. We use the same method applied to prove theorem 5.10.3. The highest degree monomial is x₁²x₂ with h₁ = 2, h₂ = 1, h₃ = 0. φ₁ = σ₁²⁻¹ σ₂¹ = σ₁ σ₂

f₁ = f − φ₁ = ∑_{_{i ≠ j}} x_i²x_j − (x₁ + x₂ + x₃)(x₁ x₂ + x₁x₃ + x₂x₃) = ∑_{_{i ≠ j}} x_i²x_j − ∑_{_{i ≠ j}} x_i²x_j − 3(x₁x₂x₃)

The highest monomial of f₁ is −3(x₁x₂x₃) so h₁ = 1, h₂ = 1, h₃ = 1. We have

φ₂ = −3σ₁¹⁻¹ σ₂¹⁻¹ σ₃ = −3σ₃ = −3(x₁x₂x₃)

and

f₂ = f₁ − φ₂ = −3(x₁x₂x₃) +3(x₁x₂x₃) = 0

thus f = φ₁ + φ₂ = σ₁σ₂ −3σ₃.

The ring of polynomials in n indeterminates in a field 𝕂, is an integral domain (see exercise 1).

«Solutions of Cubic and Quartic equations Index Rational functions »