Elementary symmetric polynomial

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 "P" can be expressed as a polynomial in elementary symmetric polynomials: "P" can be 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 any "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"1, …, "X""n", written "e""k"("X"1, …, "X""n") for "k" = 0, 1, ..., "n", can be defined as:egin{align} e_0 (X_1, X_2, dots,X_n) &= 1,\ e_1 (X_1, X_2, dots,X_n) &= extstylesum_{1 leq j leq n} X_j,\ e_2 (X_1, X_2, dots,X_n) &= extstylesum_{1 leq j < k leq n} X_j X_k,\ e_3 (X_1, X_2, dots,X_n) &= extstylesum_{1 leq j < k < l leq n} X_j X_k X_l,\end{align}and so forth, down to : e_n (X_1, X_2, dots,X_n) = X_1 X_2 cdots X_n(sometimes the notation σ"k" is used instead of "e""k").In general, for "k" ≥ 0 we define: e_k (X_1 , ldots , X_n )=sum_{1le j_1 < j_2 < cdots < j_k le n} X_{j_1} cdots X_{j_k}.

Thus, for each positive integer k, less than or equal to n, there exists exactly one elementary symmetric polynomial of degree k in n variables. To form the one which has degree k, we form all products of k-tuples of the n variables and add up these terms.

The fact that X_1X_2=X_2X_1 and so forth is the defining feature of commutative algebra. That is, the polynomial ring formed by taking all linear combinations of products of the elementary symmetric polynomials is a commutative ring.

Examples

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

For n = 1::e_1(X_1) = X_1.

For n = 2: :egin{align} e_1(X_1,X_2) &= X_1 + X_2,\ e_2(X_1,X_2) &= X_1X_2.,\end{align}

For n = 3::egin{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}

For n = 4::egin{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}

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+(-1)^n 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 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 &lt; "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 depend only on a proper subset of the "n" variables "X"1, ..., "X""n", i.e., where one variable "X""j" is missing.

Because "P" is symmetric the lacunary part is determined by the coefficients of all monomials which only depend on the variables "X"1, ..., "X""n"−1. The sum of all these monomials is equal to a polynomial ilde{P}(X_1, ldots, X_{n-1})=P(X_1, ldots,X_{n-1},0) which is symmetric in "n"−1 variables. According to the induction assumption ilde{P}(X_1, ldots. X_{n-1}) can be written as : ilde{P}(X_1, ldots, X_{n-1})= ilde{Q}(sigma_{1,n-1}, ldots, sigma_{n-1,n-1}) for some ilde{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}):= ilde{Q}(sigma_{1,n}, ldots, sigma_{n-1,n}) .Then R(X_1, ldots, X_{n}) is a symmetric polynomial whose lacunary part coincides with that of the original polynomial "P" (note here that the difference sigma_{j,n}-sigma_{j,n-1} is divisible by "X""n", therefore in the three polynomials "R", ilde{P} and finally P_{mbox{lacunary all monomials involving only "X"1, ... ,"X""n"−1 are identical). Therefore the difference "P"−"R" has zero lacunary part and is of the form X_1 cdots X_n cdot Q(X_1, ldots, X_n) . The first factor coincides with the elementary symmetric polynomial sigma_{n,n} , the second factor "Q" is a homogeneous symmetric polynomial of lower degree d which by the induction 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 quotient field of "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_1,ldots,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 homogenous of degree "d"; different homogeneous components can be decomposed separately. Order the monomials in the variables "X""i" lexicographically, where the individual variables are ordered X_1>cdots>X_n, in other words the dominant term of a polynomial is one with the highest occurring power of "X"1, and among those the one with the highest power of "X"2, 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_1,ldots,X_n) in the product so that those with larger indices "i" come first, then build for each such factor a column of "i" boxes, and arrange those columns from left to right to form a Young diagram containing "d" boxes in all. The shape of this diagram is a partition of "d", and each parition λ of "d" arises for exactly one product of elementary symmetric polynomials, which we shall denote by "e"λt ("X"1,…,"X""n") (the "t" is present only because traditionally this product is associated to the transpose partition of λ). 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"1,…,"X""n") is "X"λ.

:"Proof". To get the leading term of the product one must select the leading term in each factor e_i(X_1,ldots,X_n), which is clearly X_1X_2cdots X_i, and multiply these together. To count the occurences of the individual variables in the resulting monomial, fill the column of the Young diagram corresponding to the factor concerned with the numbers 1,&hellip;,"i" 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"&lambda; (its coefficient is 1 because there is only one choice that leads to this monomial).

Now one proves by induction on the leading monomial in lexicographic order, that any nonzero homogenous symmetric polynomial "P" of degree "d" can be written as polynomial in the elementary symmetric polynomials. Since "P" is symmetric, its leading monomial has weakly decreasing exponents, so it is some "X"λ with λ a partition of "d". Let the coefficient of this term be "c", then "P"–"ce"λt ("X"1,…,"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"1,…,"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"1,…,"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"1,…,"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.

ee also

*Newton's identities
*Schur polynomial
*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. Camridge: Cambridge University Press. ISBN 0-521-56069-1


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • elementary symmetric polynomial — noun a coefficient of some power of t in , for any …   Wiktionary

  • Symmetric polynomial — This article is about individual symmetric polynomials. For the ring of symmetric polynomials, see ring of symmetric functions. In mathematics, a symmetric polynomial is a polynomial P(X1, X2, …, Xn) in n variables, such that if any of the… …   Wikipedia

  • Elementary symmetric mean — The elementary symmetric mean is based on elementary symmetric polynomials.If x is a tuple with x = (x 1,dots,x n) andalpha p(x) is the corresponding elementary symmetric term of order p,then the respective mean is:M p(x) = sqrt [p] {frac{alpha… …   Wikipedia

  • 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… …   Wikipedia

  • Power sum symmetric polynomial — In mathematics, specifically in commutative algebra, the power sum symmetric polynomials are a type of basic building block for symmetric polynomials, in the sense that every symmetric polynomial with rational coefficients can be expressed as a… …   Wikipedia

  • Elementary — Elementary: *Education ** Elementary education, consists of the first years of formal, structured education that occur during childhood. **Elementary school, a school providing elementary or primary education. Historically, a school in the UK… …   Wikipedia

  • Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… …   Wikipedia

  • Schur polynomial — In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in n variables with integral coefficients. The elementary symmetric polynomials and the complete homogeneous symmetric polynomials are special cases of… …   Wikipedia

  • Elementary algebra — is a fundamental and relatively basic form of algebra taught to students who are presumed to have little or no formal knowledge of mathematics beyond arithmetic. It is typically taught in secondary school under the term algebra. The major… …   Wikipedia

  • Polynomial ring — In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”