Английская Википедия:Complete homogeneous symmetric polynomial
In mathematics, specifically in algebraic combinatorics and commutative algebra, the complete homogeneous symmetric polynomials are a specific kind of symmetric polynomials. Every symmetric polynomial can be expressed as a polynomial expression in complete homogeneous symmetric polynomials.
Definition
The complete homogeneous symmetric polynomial of degree Шаблон:Math in Шаблон:Math variables Шаблон:Math, written Шаблон:Math for Шаблон:Math, is the sum of all monomials of total degree Шаблон:Math in the variables. Formally,
- <math>h_k (X_1, X_2, \dots,X_n) = \sum_{1 \leq i_1 \leq i_2 \leq \cdots \leq i_k \leq n} X_{i_1} X_{i_2} \cdots X_{i_k}.</math>
The formula can also be written as:
- <math>h_k (X_1, X_2, \dots,X_n) = \sum_{l_1+l_2+ \cdots + l_n=k \atop l_i \geq 0 } X_{1}^{l_1} X_{2}^{l_2} \cdots X_{n}^{l_n}.</math>
Indeed, Шаблон:Math is just the multiplicity of Шаблон:Math in the sequence Шаблон:Math.
The first few of these polynomials are
- <math>\begin{align}
h_0 (X_1, X_2, \dots,X_n) &= 1, \\[10px] h_1 (X_1, X_2, \dots,X_n) &= \sum_{1 \leq j \leq n} X_j, \\ h_2 (X_1, X_2, \dots,X_n) &= \sum_{1 \leq j \leq k \leq n} X_j X_k, \\ h_3 (X_1, X_2, \dots,X_n) &= \sum_{1 \leq j \leq k \leq l \leq n} X_j X_k X_l. \end{align}</math>
Thus, for each nonnegative integer Шаблон:Math, there exists exactly one complete homogeneous symmetric polynomial of degree Шаблон:Math in Шаблон:Math variables.
Another way of rewriting the definition is to take summation over all sequences Шаблон:Math, without condition of ordering Шаблон:Math:
- <math>h_k (X_1, X_2, \dots, X_n) = \sum_{1 \leq i_1, i_2 , \cdots , i_k \leq n} \frac{m_1! m_2 !\cdots m_n!}{k!} X_{i_1} X_{i_2} \cdots X_{i_k},</math>
here Шаблон:Math is the multiplicity of number Шаблон:Math in the sequence Шаблон:Math.
For example
- <math>h_2 (X_1, X_2) = \frac{2!0!}{2!}X_1^2 +\frac{1!1!}{2!}X_1X_2 +\frac{1!1!}{2!}X_2X_1 + \frac{0!2!}{2!}X_2^2 = X_1^2+X_1X_2+X_2^2.</math>
The polynomial ring formed by taking all integral linear combinations of products of the complete homogeneous symmetric polynomials is a commutative ring.
Examples
The following lists the Шаблон:Math basic (as explained below) complete homogeneous symmetric polynomials for the first three positive values of Шаблон:Math.
For Шаблон:Math:
- <math>h_1(X_1) = X_1\,.</math>
For Шаблон:Math:
- <math>\begin{align}
h_1(X_1,X_2)&= X_1 + X_2\\ h_2(X_1,X_2)&= X_1^2 + X_1X_2 + X_2^2.
\end{align}</math>
For Шаблон:Math:
- <math>\begin{align}
h_1(X_1,X_2,X_3) &= X_1 + X_2 + X_3\\ h_2(X_1,X_2,X_3) &= X_1^2 + X_2^2 + X_3^2 + X_1X_2 + X_1X_3 + X_2X_3\\ h_3(X_1,X_2,X_3) &= X_1^3+X_2^3+X_3^3 + X_1^2X_2+X_1^2X_3+X_2^2X_1+X_2^2X_3+X_3^2X_1+X_3^2X_2 + X_1X_2X_3.
\end{align}</math>
Properties
Generating function
The complete homogeneous symmetric polynomials are characterized by the following identity of formal power series in Шаблон:Math:
- <math>\sum_{k=0}^\infty h_k(X_1,\ldots,X_n)t^k = \prod_{i=1}^n\sum_{j=0}^\infty(X_it)^j = \prod_{i=1}^n\frac1{1-X_it}</math>
(this is called the generating function, or generating series, for the complete homogeneous symmetric polynomials). Here each fraction in the final expression is the usual way to represent the formal geometric series that is a factor in the middle expression. The identity can be justified by considering how the product of those geometric series is formed: each factor in the product is obtained by multiplying together one term chosen from each geometric series, and every monomial in the variables Шаблон:Math is obtained for exactly one such choice of terms, and comes multiplied by a power of Шаблон:Math equal to the degree of the monomial.
The formula above can be seen as a special case of the MacMahon master theorem. The right hand side can be interpreted as <math>1/\!\det(1-tM)</math> where <math>t \in \mathbb{R}</math> and <math>M = \text{diag}(X_1, \ldots, X_N)</math>. On the left hand side, one can identify the complete homogeneous symmetric polynomials as special cases of the multinomial coefficient that appears in the MacMahon expression.
Performing some standard computations, we can also write the generating function as <math display="block">\sum_{k=0}^\infty h_k(X_1,\ldots,X_n)\, t^k = \exp \left( \sum_{j=1}^\infty (X_1^j+\cdots+X_n^j) \frac{t^j}j \right)</math>which is the power series expansion of the plethystic exponential of <math>(X_1+\cdots +X_n)t</math> (and note that <math>p_j:=X_1^j+\cdots+X_n^j</math> is precisely the j-th power sum symmetric polynomial).
Relation with the elementary symmetric polynomials
There is a fundamental relation between the elementary symmetric polynomials and the complete homogeneous ones:
- <math>\sum_{i=0}^m(-1)^ie_i(X_1,\ldots,X_n)h_{m-i}(X_1,\ldots,X_n)=0,</math>
which is valid for all Шаблон:Math, and any number of variables Шаблон:Math. The easiest way to see that it holds is from an identity of formal power series in Шаблон:Math for the elementary symmetric polynomials, analogous to the one given above for the complete homogeneous ones, which can also be written in terms of plethystic exponentials as:
- <math>\sum_{k=0}^\infty e_k(X_1,\ldots,X_n)(-t)^k = \prod_{i=1}^n(1-X_it) = PE[-(X_1+\cdots+X_n)t]</math>
(this is actually an identity of polynomials in Шаблон:Math, because after Шаблон:Math the elementary symmetric polynomials become zero). Multiplying this by the generating function for the complete homogeneous symmetric polynomials, one obtains the constant series 1 (equivalently, plethystic exponentials satisfy the usual properties of an exponential), and the relation between the elementary and complete homogeneous polynomials follows from comparing coefficients of Шаблон:Math. A somewhat more direct way to understand that relation is to consider the contributions in the summation involving a fixed monomial Шаблон:Math of degree Шаблон:Math. For any subset Шаблон:Math of the variables appearing with nonzero exponent in the monomial, there is a contribution involving the product Шаблон:Math of those variables as term from Шаблон:Math, where Шаблон:Math, and the monomial Шаблон:Math from Шаблон:Math; this contribution has coefficient Шаблон:Math. The relation then follows from the fact that
- <math>\sum_{s=0}^l\binom{l}{s}(-1)^s=(1-1)^l=0\quad\mbox{for }l>0,</math>
by the binomial formula, where Шаблон:Math denotes the number of distinct variables occurring (with nonzero exponent) in Шаблон:Math. Since Шаблон:Math and Шаблон:Math are both equal to 1, one can isolate from the relation either the first or the last terms of the summation. The former gives a sequence of equations:
- <math>\begin{align}
h_1(X_1,\ldots,X_n)&=e_1(X_1,\ldots,X_n),\\ h_2(X_1,\ldots,X_n)&=h_1(X_1,\ldots,X_n)e_1(X_1,\ldots,X_n)-e_2(X_1,\ldots,X_n),\\ h_3(X_1,\ldots,X_n)&=h_2(X_1,\ldots,X_n)e_1(X_1,\ldots,X_n)-h_1(X_1,\ldots,X_n)e_2(X_1,\ldots,X_n)+e_3(X_1,\ldots,X_n),\\
\end{align}</math>
and so on, that allows to recursively express the successive complete homogeneous symmetric polynomials in terms of the elementary symmetric polynomials; the latter gives a set of equations
- <math>\begin{align}
e_1(X_1,\ldots,X_n)&=h_1(X_1,\ldots,X_n),\\ e_2(X_1,\ldots,X_n)&=h_1(X_1,\ldots,X_n)e_1(X_1,\ldots,X_n)-h_2(X_1,\ldots,X_n),\\ e_3(X_1,\ldots,X_n)&=h_1(X_1,\ldots,X_n)e_2(X_1,\ldots,X_n)-h_2(X_1,\ldots,X_n)e_1(X_1,\ldots,X_n)+h_3(X_1,\ldots,X_n),\\
\end{align}</math>
and so forth, that allows doing the inverse. The first Шаблон:Math elementary and complete homogeneous symmetric polynomials play perfectly similar roles in these relations, even though the former polynomials then become zero, whereas the latter do not. This phenomenon can be understood in the setting of the ring of symmetric functions. It has a ring automorphism that interchanges the sequences of the Шаблон:Math elementary and first Шаблон:Math complete homogeneous symmetric functions.
The set of complete homogeneous symmetric polynomials of degree 1 to Шаблон:Math 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>\mathbb Z\big[h_1(X_1,\ldots,X_n),\ldots,h_n(X_1,\ldots,X_n)\big].</math>
This can be formulated by saying that
- <math> h_1(X_1,\ldots,X_n),\ldots,h_n(X_1,\ldots,X_n) </math>
form a transcendence basis of the ring of symmetric polynomials in Шаблон:Math with integral coefficients (as is also true for the elementary symmetric polynomials). The same is true with the ring <math>\mathbb{Z}</math> of integers replaced by any other commutative ring. These statements follow from analogous statements for the elementary symmetric polynomials, due to the indicated possibility of expressing either kind of symmetric polynomials in terms of the other kind.
Relation with the Stirling numbers
The evaluation at integers of complete homogeneous polynomials and elementary symmetric polynomials is related to Stirling numbers:
- <math>\begin{align}
h_n(1,2,\ldots,k)&= \left\{\begin{matrix} n+k \\ k \end{matrix}\right\}\\ e_n(1,2,\ldots,k)&=\left[{k+1 \atop k+1-n}\right]\\ \end{align}</math>
Relation with the monomial symmetric polynomials
The polynomial Шаблон:Math is also the sum of all distinct monomial symmetric polynomials of degree Шаблон:Math in Шаблон:Math, for instance
- <math>\begin{align}
h_3(X_1,X_2,X_3)&=m_{(3)}(X_1,X_2,X_3)+m_{(2,1)}(X_1,X_2,X_3)+m_{(1,1,1)}(X_1,X_2,X_3)\\
&=\left(X_1^3+X_2^3+X_3^3\right)+\left(X_1^2X_2+X_1^2X_3+X_1X_2^2+X_1X_3^2+X_2^2X_3+X_2X_3^2\right)+(X_1X_2X_3).\\
\end{align}</math>
Relation with power sums
Newton's identities for homogeneous symmetric polynomials give the simple recursive formula
- <math>kh_k = \sum_{i=1}^kh_{k-i}p_i,</math>
where <math>h_k=h_k(X_1, \dots, X_n)</math> and pk is the k-th power sum symmetric polynomial: <math>p_k(X_1,\ldots,X_n)=\sum\nolimits_{i=1}^nx_i^k = X_1^k+\cdots+X_n^k</math>, as above.
For small <math>k</math> we have
- <math>\begin{align}
h_1 &= p_1,\\ 2h_2 &= h_1p_1 + p_2,\\ 3h_3 &= h_2p_1 + h_1p_2 + p_3.\\
\end{align}</math>
Relation with symmetric tensors
Consider an Шаблон:Math-dimensional vector space Шаблон:Math and a linear operator Шаблон:Math with eigenvalues Шаблон:Math. Denote by Шаблон:Math its Шаблон:Mathth symmetric tensor power and Шаблон:Math the induced operator Шаблон:Math.
Proposition:
- <math> \operatorname{Trace}_{\operatorname{Sym}^k(V)} \left(M^{\operatorname{Sym}(k)}\right) = h_{k}(X_1,X_2,\ldots,X_n).</math>
The proof is easy: consider an eigenbasis Шаблон:Math for Шаблон:Math. The basis in Шаблон:Math can be indexed by sequences Шаблон:Math, indeed, consider the symmetrizations of
- <math>e_{i_1} \otimes\, e_{i_2} \otimes \ldots \otimes\, e_{i_k}</math>.
All such vectors are eigenvectors for Шаблон:Math with eigenvalues
- <math>X_{i_1}X_{i_2}\cdots X_{i_k},</math>
hence this proposition is true.
Similarly one can express elementary symmetric polynomials via traces over antisymmetric tensor powers. Both expressions are subsumed in expressions of Schur polynomials as traces over Schur functors, which can be seen as the Weyl character formula for Шаблон:Math.
Complete homogeneous symmetric polynomial with variables shifted by 1
If we replace the variables <math>X_i</math> for <math>1+X_i</math>, the symmetric polynomial <math>h_k(1+X_1, \ldots, 1+X_n)</math> can be written as a linear combination of the <math>h_j(X_1, \ldots, X_n)</math>, for <math>0 \le j \le k</math>,
- <math>h_k(1+X_1, \ldots, 1+X_n) =
\sum_{j=0}^k \binom{n+k-1}{k-j} h_j(X_1, \ldots, X_n).</math>
The proof, as found in Lemma 3.5 of,[1] relies on the combinatorial properties of increasing <math>k</math>-tuples <math>(i_1, \ldots,i_k)</math> where <math>1 \le i_1 \le \cdots \le i_k \le n</math>.
See also
- Symmetric polynomial
- Elementary symmetric polynomial
- Schur polynomial
- Newton's identities
- MacMahon Master theorem
- Symmetric function
- Representation theory
References
- Macdonald, I.G. (1979), Symmetric Functions and Hall Polynomials. Oxford Mathematical Monographs. Oxford: Clarendon Press.
- Macdonald, I.G. (1995), Symmetric Functions and Hall Polynomials, second ed. Oxford: Clarendon Press. Шаблон:ISBN (paperback, 1998).
- Richard P. Stanley (1999), Enumerative Combinatorics, Vol. 2. Cambridge: Cambridge University Press. Шаблон:ISBN
