Elementary symmetric polynomial

In mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial can be expressed as a polynomial in elementary symmetric polynomials. That is, any symmetric polynomial P is given by an expression involving only additions and multiplication of constants and elementary symmetric polynomials. There is one elementary symmetric polynomial of degree d in n variables for each nonnegative integer d ≤ n, and it is formed by adding together all distinct products of d distinct variables.

Definition

The elementary symmetric polynomials in $n$ variables X₁, …, X_n, written e_k(X₁, …, X_n) for k = 0, 1, ..., n, are defined by

${\begin{aligned}e_{0}(X_{1},X_{2},\dots ,X_{n})&=1,\\e_{1}(X_{1},X_{2},\dots ,X_{n})&=\textstyle \sum _{1\leq j\leq n}X_{j},\\e_{2}(X_{1},X_{2},\dots ,X_{n})&=\textstyle \sum _{1\leq j<k\leq n}X_{j}X_{k},\\e_{3}(X_{1},X_{2},\dots ,X_{n})&=\textstyle \sum _{1\leq j<k<l\leq n}X_{j}X_{k}X_{l},\\\end{aligned}}$

and so forth, ending with

$e_{n}(X_{1},X_{2},\dots ,X_{n})=X_{1}X_{2}\ldots X_{n}$.

In general, for k ≥ 0 we define

$e_{k}(X_{1},\ldots ,X_{n})=\sum _{1\leq j_{1}<j_{2}<\ldots <j_{k}\leq n}X_{j_{1}}\dotsm X_{j_{k}},$

so that e_k(X₁, …, X_n) = 0 if k > n.

Thus, for each positive integer Template:Mvar less than or equal to Template:Mvar there exists exactly one elementary symmetric polynomial of degree Template:Mvar in Template:Mvar variables. To form the one that has degree Template:Mvar, we take the sum of all products of Template:Mvar-subsets of the Template:Mvar variables. (By contrast, if one performs the same operation using multisets of variables, that is, taking variables with repetition, one arrives at the complete homogeneous symmetric polynomials.)

Given an integer partition (that is, a finite decreasing sequence of positive integers) λ = (λ₁, …, λ_m), one defines the symmetric polynomial $e_{\lambda }(X_{1},\dots ,X_{n})$, also called an elementary symmetric polynomial, by

$e_{\lambda }(X_{1},\dots ,X_{n})=e_{\lambda _{1}}(X_{1},\dots ,X_{n})\cdot e_{\lambda _{2}}(X_{1},\dots ,X_{n})\cdots e_{\lambda _{m}}(X_{1},\dots ,X_{n})$.

Sometimes the notation σ_k is used instead of e_k.

Examples

The following lists the n elementary symmetric polynomials for the first four positive values of n. (In every case, e₀ = 1 is also one of the polynomials.)

For n = 1:

$e_{1}(X_{1})=X_{1}.\,$

For n = 2:

${\begin{aligned}e_{1}(X_{1},X_{2})&=X_{1}+X_{2},\\e_{2}(X_{1},X_{2})&=X_{1}X_{2}.\,\\\end{aligned}}$

For n = 3:

${\begin{aligned}e_{1}(X_{1},X_{2},X_{3})&=X_{1}+X_{2}+X_{3},\\e_{2}(X_{1},X_{2},X_{3})&=X_{1}X_{2}+X_{1}X_{3}+X_{2}X_{3},\\e_{3}(X_{1},X_{2},X_{3})&=X_{1}X_{2}X_{3}.\,\\\end{aligned}}$

For n = 4:

${\begin{aligned}e_{1}(X_{1},X_{2},X_{3},X_{4})&=X_{1}+X_{2}+X_{3}+X_{4},\\e_{2}(X_{1},X_{2},X_{3},X_{4})&=X_{1}X_{2}+X_{1}X_{3}+X_{1}X_{4}+X_{2}X_{3}+X_{2}X_{4}+X_{3}X_{4},\\e_{3}(X_{1},X_{2},X_{3},X_{4})&=X_{1}X_{2}X_{3}+X_{1}X_{2}X_{4}+X_{1}X_{3}X_{4}+X_{2}X_{3}X_{4},\\e_{4}(X_{1},X_{2},X_{3},X_{4})&=X_{1}X_{2}X_{3}X_{4}.\,\\\end{aligned}}$

Properties

The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identity

$\prod _{j=1}^{n}(\lambda +X_{j})=\lambda ^{n}+e_{1}(X_{1},\ldots ,X_{n})\lambda ^{n-1}+e_{2}(X_{1},\ldots ,X_{n})\lambda ^{n-2}+\cdots +e_{n}(X_{1},\ldots ,X_{n}).$

That is, when we substitute numerical values for the variables $X_{1},X_{2},\dots ,X_{n}$, we obtain the monic univariate polynomial (with variable λ) whose roots are the values substituted for $X_{1},X_{2},\dots ,X_{n}$ and whose coefficients are the elementary symmetric polynomials.

The characteristic polynomial of a linear operator is an example of this. The roots are the eigenvalues of the operator. When we substitute these eigenvalues into the elementary symmetric polynomials, we obtain the coefficients of the characteristic polynomial, which are numerical invariants of the operator. This fact is useful in linear algebra and its applications and generalizations, like tensor algebra and disciplines which extensively employ tensor fields, such as differential geometry.

The set of elementary symmetric polynomials in $n$ variables generates the ring of symmetric polynomials in $n$ variables. More specifically, the ring of symmetric polynomials with integer coefficients equals the integral polynomial ring $\mathbb {Z} [e_{1}(X_{1},\ldots ,X_{n}),\ldots ,e_{n}(X_{1},\ldots ,X_{n})].$ (See below for a more general statement and proof.) This fact is one of the foundations of invariant theory. For other systems of symmetric polynomials with a similar property see power sum symmetric polynomials and complete homogeneous symmetric polynomials.

The fundamental theorem of symmetric polynomials

For any commutative ring A denote the ring of symmetric polynomials in the variables $X_{1},\ldots ,X_{n}$ with coefficients in A by $A[X_{1},\ldots ,X_{n}]^{S_{n}}$.

$A[X_{1},\ldots ,X_{n}]^{S_{n}}$ is a polynomial ring in the n elementary symmetric polynomials $e_{k}(X_{1},\ldots ,X_{n})$ for k = 1, ..., n.

(Note that $e_{0}$ is not among these polynomials; since $e_{0}=1$, it cannot be member of any set of algebraically independent elements.)

This means that every symmetric polynomial $P(X_{1},\ldots ,X_{n})\in A[X_{1},\ldots ,X_{n}]^{S_{n}}$ has a unique representation

$P(X_{1},\ldots ,X_{n})=Q(e_{1}(X_{1},\ldots ,X_{n}),\ldots ,e_{n}(X_{1},\ldots ,X_{n}))$

for some polynomial $Q\in A[Y_{1},\ldots ,Y_{n}]$. Another way of saying the same thing is that $A[X_{1},\ldots ,X_{n}]^{S_{n}}$ is isomorphic to the polynomial ring $A[Y_{1},\ldots ,Y_{n}]$ through an isomorphism that sends $Y_{k}$ to $e_{k}(X_{1},\ldots ,X_{n})$ for $k=1,\ldots ,n$.

Proof sketch

The theorem may be proved for symmetric homogeneous polynomials by a double mathematical induction with respect to the number of variables n and, for fixed n, with respect to the degree of the homogeneous polynomial. The general case then follows by splitting an arbitrary symmetric polynomial into its homogeneous components (which are again symmetric).

In the case n = 1 the result is obvious because every polynomial in one variable is automatically symmetric.

Assume now that the theorem has been proved for all polynomials for $m<n$ variables and all symmetric polynomials in n variables with degree < d. Every homogeneous symmetric polynomial P in $A[X_{1},\ldots ,X_{n}]^{S_{n}}$ can be decomposed as a sum of homogeneous symmetric polynomials

$P(X_{1},\ldots ,X_{n})=P_{\mbox{lacunary}}(X_{1},\ldots ,X_{n})+X_{1}\cdots X_{n}\cdot Q(X_{1},\ldots ,X_{n}).$

Here the "lacunary part" $P_{\mbox{lacunary}}$ is defined as the sum of all monomials in P which contain only a proper subset of the n variables X₁, ..., X_n, i.e., where at least one variable X_j is missing.

Because P is symmetric, the lacunary part is determined by its terms containing only the variables X₁, ..., X_n−1, i.e., which do not contain X_n. These are precisely the terms that survive the operation of setting X_n to 0, so their sum equals $P(X_{1},\ldots ,X_{n-1},0)$, which is a symmetric polynomial in the variables X₁, ..., X_n−1 that we shall denote by ${\tilde {P}}(X_{1},\ldots ,X_{n-1})$. By the inductive assumption, this polynomial can be written as

${\tilde {P}}(X_{1},\ldots ,X_{n-1})={\tilde {Q}}(\sigma _{1,n-1},\ldots ,\sigma _{n-1,n-1})$

for some ${\tilde {Q}}$. Here the doubly indexed $\sigma _{j,n-1}$ denote the elementary symmetric polynomials in n−1 variables.

Consider now the polynomial

$R(X_{1},\ldots ,X_{n}):={\tilde {Q}}(\sigma _{1,n},\ldots ,\sigma _{n-1,n})\ .$

Then $R(X_{1},\ldots ,X_{n})$ is a symmetric polynomial in X₁, ..., X_n, of the same degree as $P_{\mbox{lacunary}}$, which satisfies

$R(X_{1},\ldots ,X_{n-1},0)={\tilde {Q}}(\sigma _{1,n-1},\ldots ,\sigma _{n-1,n-1})=P(X_{1},\ldots ,X_{n-1},0)$

(the first equality holds because setting X_n to 0 in $\sigma _{j,n}$ gives $\sigma _{j,n-1}$, for all $j<n$), in other words, the lacunary part of R coincides with that of the original polynomial P. Therefore the difference P−R has no lacunary part, and is therefore divisible by the product $X_{1}\cdots X_{n}$ of all variables, which equals the elementary symmetric polynomial $\sigma _{n,n}$. Then writing $P-R=\sigma _{n,n}\,Q$, the quotient Q is a homogeneous symmetric polynomial of degree less than d (in fact degree at most d − n) which by the inductive assumption can be expressed as a polynomial in the elementary symmetric functions. Combining the representations for P−R and R one finds a polynomial representation for P.

The uniqueness of the representation can be proved inductively in a similar way. (It is equivalent to the fact that the n polynomials $e_{1},\ldots ,e_{n}$ are algebraically independent over the ring A.) The fact that the polynomial representation is unique implies that $A[X_{1},\ldots ,X_{n}]^{S_{n}}$ is isomorphic to $A[Y_{1},\ldots ,Y_{n}]$.

An alternative proof

The following proof is also inductive, but does not involve other polynomials than those symmetric in X₁,...,X_n, and also leads to a fairly direct procedure to effectively write a symmetric polynomial as a polynomial in the elementary symmetric ones. Assume the symmetric polynomial to be homogeneous of degree Template:Mvar; different homogeneous components can be decomposed separately. Order the monomials in the variables Template:Mvar lexicographically, where the individual variables are ordered X₁ > … > X_n, in other words the dominant term of a polynomial is one with the highest occurring power of X₁, and among those the one with the highest power of X₂, etc. Furthermore parametrize all products of elementary symmetric polynomials that have degree d (they are in fact homogeneous) as follows by partitions of d. Order the individual elementary symmetric polynomials e_i(X₁,…,X_n) in the product so that those with larger indices Template:Mvar come first, then build for each such factor a column of Template:Mvar boxes, and arrange those columns from left to right to form a Young diagram containing Template:Mvar boxes in all. The shape of this diagram is a partition of Template:Mvar, and each partition Template:Mvar of d arises for exactly one product of elementary symmetric polynomials, which we shall denote by e_λ^t (X₁,…,X_n) (the "t" is present only because traditionally this product is associated to the transpose partition of Template:Mvar). The essential ingredient of the proof is the following simple property, which uses multi-index notation for monomials in the variables X_i.

Lemma. The leading term of e_λ^t (X₁,…,X_n) is X^λ.

Proof. The leading term of the product is the product of the leading terms of each factor (this is true whenever one uses a monomial order, like the lexicographic order used here), and the leading term of the factor e_i(X₁,…,X_n) is clearly X₁X₂…X_i. To count the occurrences of the individual variables in the resulting monomial, fill the column of the Young diagram corresponding to the factor concerned with the numbers 1…,Template:Mvar of the variables, then all boxes in the first row contain 1, those in the second row 2, and so forth, which means the leading term is X^λ.

Now one proves by induction on the leading monomial in lexicographic order, that any nonzero homogeneous symmetric polynomial Template:Mvar of degree Template:Mvar can be written as polynomial in the elementary symmetric polynomials. Since Template:Mvar is symmetric, its leading monomial has weakly decreasing exponents, so it is some X^λ with Template:Mvar a partition of d. Let the coefficient of this term be Template:Mvar, then P − ce_λ^t (X₁,…,X_n) is either zero or a symmetric polynomial with a strictly smaller leading monomial. Writing this difference inductively as a polynomial in the elementary symmetric polynomials, and adding back ce_λ^t (X₁,…,X_n) to it, one obtains the sought for polynomial expression for P.

The fact that this expression is unique, or equivalently that all the products (monomials) e_λ^t (X₁,…,X_n) of elementary symmetric polynomials are linearly independent, is also easily proved. The lemma shows that all these products have different leading monomials, and this suffices: if a nontrivial linear combination of the e_λ^t (X₁,…,X_n) were zero, one focusses on the contribution in the linear combination with nonzero coefficient and with (as polynomial in the variables X_i) the largest leading monomial; the leading term of this contribution cannot be cancelled by any other contribution of the linear combination, which gives a contradiction.

See also

• Symmetric polynomial
• Complete homogeneous symmetric polynomial
• Schur polynomial
• Newton's identities
• MacMahon Master theorem
• Symmetric function
• Representation theory

References

• Macdonald, I.G. (1995), Symmetric Functions and Hall Polynomials, second ed. Oxford: Clarendon Press. ISBN 0-19-850450-0 (paperback, 1998).
• Richard P. Stanley (1999), Enumerative Combinatorics, Vol. 2. Cambridge: Cambridge University Press. ISBN 0-521-56069-1