Английская Википедия:Elementary symmetric polynomial
Шаблон:No footnotes 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 Шаблон:Math is given by an expression involving only additions and multiplication of constants and elementary symmetric polynomials. There is one elementary symmetric polynomial of degree Шаблон:Math in Шаблон:Math variables for each positive integer Шаблон:Math, and it is formed by adding together all distinct products of Шаблон:Math distinct variables.
Definition
The elementary symmetric polynomials in Шаблон:Math variables Шаблон:Math, written Шаблон:Math for Шаблон:Math, are defined by
- <math>\begin{align}
e_1 (X_1, X_2, \dots,X_n) &= \sum_{1 \leq j \leq n} X_j,\\
e_2 (X_1, X_2, \dots,X_n) &= \sum_{1 \leq j < k \leq n} X_j X_k,\\
e_3 (X_1, X_2, \dots,X_n) &= \sum_{1 \leq j < k < l \leq n} X_j X_k X_l,\\
\end{align}</math> and so forth, ending with
- <math> e_n (X_1, X_2, \dots,X_n) = X_1 X_2 \cdots X_n.</math>
In general, for Шаблон:Math we define
- <math> e_k (X_1 , \ldots , X_n )=\sum_{1\le j_1 < j_2 < \cdots < j_k \le n} X_{j_1} \dotsm X_{j_k},</math>
so that Шаблон:Math if Шаблон:Math. (Sometimes, Шаблон:Math is included among the elementary symmetric polynomials, but excluding it allows generally simpler formulation of results and properties.)
Thus, for each positive integer Шаблон:Mvar less than or equal to Шаблон:Mvar there exists exactly one elementary symmetric polynomial of degree Шаблон:Mvar in Шаблон:Mvar variables. To form the one that has degree Шаблон:Mvar, we take the sum of all products of Шаблон:Mvar-subsets of the Шаблон: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 non-increasing sequence of positive integers) Шаблон:Math, one defines the symmetric polynomial Шаблон:Math, also called an elementary symmetric polynomial, by
- <math>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)</math>.
Sometimes the notation Шаблон:Math is used instead of Шаблон:Math.
Examples
The following lists the Шаблон:Math elementary symmetric polynomials for the first four positive values of Шаблон:Math.
For Шаблон:Math:
- <math>e_1(X_1) = X_1.</math>
For Шаблон:Math:
- <math>\begin{align}
e_1(X_1,X_2) &= X_1 + X_2,\\ e_2(X_1,X_2) &= X_1X_2.\,\\
\end{align}</math>
For Шаблон:Math:
- <math>\begin{align}
e_1(X_1,X_2,X_3) &= X_1 + X_2 + X_3,\\ e_2(X_1,X_2,X_3) &= X_1X_2 + X_1X_3 + X_2X_3,\\ e_3(X_1,X_2,X_3) &= X_1X_2X_3.\,\\
\end{align}</math>
For Шаблон:Math:
- <math>\begin{align}
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_1X_2 + X_1X_3 + X_1X_4 + X_2X_3 + X_2X_4 + X_3X_4,\\ e_3(X_1,X_2,X_3,X_4) &= X_1X_2X_3 + X_1X_2X_4 + X_1X_3X_4 + X_2X_3X_4,\\ e_4(X_1,X_2,X_3,X_4) &= X_1X_2X_3X_4.\,\\
\end{align}</math>
Properties
The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identity
- <math>\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 +(-1)^n e_n(X_1,\ldots,X_n).</math>
That is, when we substitute numerical values for the variables Шаблон:Math, we obtain the monic univariate polynomial (with variable Шаблон:Math) whose roots are the values substituted for Шаблон:Math and whose coefficients are – up to their sign – the elementary symmetric polynomials. These relations between the roots and the coefficients of a polynomial are called Vieta's formulas.
The characteristic polynomial of a square matrix is an example of application of Vieta's formulas. The roots of this polynomial are the eigenvalues of the matrix. When we substitute these eigenvalues into the elementary symmetric polynomials, we obtain – up to their sign – the coefficients of the characteristic polynomial, which are invariants of the matrix. In particular, the trace (the sum of the elements of the diagonal) is the value of Шаблон:Math, and thus the sum of the eigenvalues. Similarly, the determinant is – up to the sign – the constant term of the characteristic polynomial, i.e. the value of Шаблон:Math. Thus the determinant of a square matrix is the product of the eigenvalues.
The set of elementary symmetric polynomials in Шаблон:Math variables generates the ring of symmetric polynomials in Шаблон:Math variables. More specifically, the ring of symmetric polynomials with integer coefficients equals the integral polynomial ring Шаблон:Math. (See below for a more general statement and proof.) This fact is one of the foundations of invariant theory. For another system of symmetric polynomials with the same property see Complete homogeneous symmetric polynomials, and for a system with a similar, but slightly weaker, property see Power sum symmetric polynomial.
Fundamental theorem of symmetric polynomials
For any commutative ring Шаблон:Math, denote the ring of symmetric polynomials in the variables Шаблон:Math with coefficients in Шаблон:Math by Шаблон:Math. This is a polynomial ring in the n elementary symmetric polynomials Шаблон:Math for Шаблон:Math.
This means that every symmetric polynomial Шаблон:Math has a unique representation
- <math> P(X_1,\ldots, X_n)=Q\big(e_1(X_1 , \ldots ,X_n), \ldots, e_n(X_1 , \ldots ,X_n)\big) </math>
for some polynomial Шаблон:Math. Another way of saying the same thing is that the ring homomorphism that sends Шаблон:Math to Шаблон:Math for Шаблон:Math defines an isomorphism between Шаблон:Math and Шаблон:Math.
Proof sketch
The theorem may be proved for symmetric homogeneous polynomials by a double induction with respect to the number of variables Шаблон:Math and, for fixed Шаблон:Math, 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 Шаблон:Math the result is trivial because every polynomial in one variable is automatically symmetric.
Assume now that the theorem has been proved for all polynomials for Шаблон:Math variables and all symmetric polynomials in Шаблон:Math variables with degree Шаблон:Math. Every homogeneous symmetric polynomial Шаблон:Math in Шаблон:Math can be decomposed as a sum of homogeneous symmetric polynomials
- <math> P(X_1,\ldots,X_n)= P_{\text{lacunary}} (X_1,\ldots,X_n) + X_1 \cdots X_n \cdot Q(X_1,\ldots,X_n). </math>
Here the "lacunary part" Шаблон:Math is defined as the sum of all monomials in Шаблон:Math which contain only a proper subset of the Шаблон:Math variables Шаблон:Math, i.e., where at least one variable Шаблон:Math is missing.
Because Шаблон:Math is symmetric, the lacunary part is determined by its terms containing only the variables Шаблон:Math, i.e., which do not contain Шаблон:Math. More precisely: If Шаблон:Math and Шаблон:Math are two homogeneous symmetric polynomials in Шаблон:Math having the same degree, and if the coefficient of Шаблон:Math before each monomial which contains only the variables Шаблон:Math equals the corresponding coefficient of Шаблон:Math, then Шаблон:Math and Шаблон:Math have equal lacunary parts. (This is because every monomial which can appear in a lacunary part must lack at least one variable, and thus can be transformed by a permutation of the variables into a monomial which contains only the variables Шаблон:Math.)
But the terms of Шаблон:Math which contain only the variables Шаблон:Math are precisely the terms that survive the operation of setting Шаблон:Math to 0, so their sum equals Шаблон:Math, which is a symmetric polynomial in the variables Шаблон:Math that we shall denote by Шаблон:Math. By the inductive hypothesis, this polynomial can be written as
- <math> \tilde{P}(X_1, \ldots, X_{n-1})=\tilde{Q}(\sigma_{1,n-1}, \ldots, \sigma_{n-1,n-1})</math>
for some Шаблон:Math. Here the doubly indexed Шаблон:Math denote the elementary symmetric polynomials in Шаблон:Math variables.
Consider now the polynomial
- <math>R(X_1, \ldots, X_{n}):= \tilde{Q}(\sigma_{1,n}, \ldots, \sigma_{n-1,n}) .</math>
Then Шаблон:Math is a symmetric polynomial in Шаблон:Math, of the same degree as Шаблон:Math, which satisfies
- <math>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)</math>
(the first equality holds because setting Шаблон:Math to 0 in Шаблон:Math gives Шаблон:Math, for all Шаблон:Math). In other words, the coefficient of Шаблон:Math before each monomial which contains only the variables Шаблон:Math equals the corresponding coefficient of Шаблон:Math. As we know, this shows that the lacunary part of Шаблон:Math coincides with that of the original polynomial Шаблон:Math. Therefore the difference Шаблон:Math has no lacunary part, and is therefore divisible by the product Шаблон:Math of all variables, which equals the elementary symmetric polynomial Шаблон:Math. Then writing Шаблон:Math, the quotient Шаблон:Math is a homogeneous symmetric polynomial of degree less than Шаблон:Math (in fact degree at most Шаблон:Math) which by the inductive hypothesis can be expressed as a polynomial in the elementary symmetric functions. Combining the representations for Шаблон:Math and Шаблон:Math one finds a polynomial representation for Шаблон:Math.
The uniqueness of the representation can be proved inductively in a similar way. (It is equivalent to the fact that the Шаблон:Math polynomials Шаблон:Math are algebraically independent over the ring Шаблон:Math.) The fact that the polynomial representation is unique implies that Шаблон:Math is isomorphic to Шаблон:Math.
Alternative proof
The following proof is also inductive, but does not involve other polynomials than those symmetric in Шаблон:Math, 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 Шаблон:Mvar; different homogeneous components can be decomposed separately. Order the monomials in the variables Шаблон:Mvar lexicographically, where the individual variables are ordered Шаблон:Math, in other words the dominant term of a polynomial is one with the highest occurring power of Шаблон:Math, and among those the one with the highest power of Шаблон:Math, etc. Furthermore parametrize all products of elementary symmetric polynomials that have degree Шаблон:Math (they are in fact homogeneous) as follows by partitions of Шаблон:Math. Order the individual elementary symmetric polynomials Шаблон:Math in the product so that those with larger indices Шаблон:Mvar come first, then build for each such factor a column of Шаблон:Mvar boxes, and arrange those columns from left to right to form a Young diagram containing Шаблон:Mvar boxes in all. The shape of this diagram is a partition of Шаблон:Mvar, and each partition Шаблон:Mvar of Шаблон:Math arises for exactly one product of elementary symmetric polynomials, which we shall denote by Шаблон:Math) (the Шаблон:Math is present only because traditionally this product is associated to the transpose partition of Шаблон:Mvar). The essential ingredient of the proof is the following simple property, which uses multi-index notation for monomials in the variables Шаблон:Math.
Lemma. The leading term of Шаблон:Math is Шаблон:Math.
- 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 Шаблон:Math is clearly Шаблон:Math. 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 Шаблон:Math 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 Шаблон:Math.
Now one proves by induction on the leading monomial in lexicographic order, that any nonzero homogeneous symmetric polynomial Шаблон:Mvar of degree Шаблон:Mvar can be written as polynomial in the elementary symmetric polynomials. Since Шаблон:Mvar is symmetric, its leading monomial has weakly decreasing exponents, so it is some Шаблон:Math with Шаблон:Mvar a partition of Шаблон:Math. Let the coefficient of this term be Шаблон:Mvar, then Шаблон:Math 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 Шаблон:Math to it, one obtains the sought for polynomial expression for Шаблон:Math.
The fact that this expression is unique, or equivalently that all the products (monomials) Шаблон:Math 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 Шаблон:Math were zero, one focuses on the contribution in the linear combination with nonzero coefficient and with (as polynomial in the variables Шаблон:Math) 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
- Newton's inequalities
- Maclaurin's inequality
- MacMahon Master theorem
- Symmetric function
- Representation theory
References
