Elementary symmetric polynomial
Encyclopedia
In mathematics
, specifically in commutative algebra
, the elementary symmetric polynomials are one type of basic building block for symmetric polynomial
s, 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.
variables X1, …, Xn, written ek(X1, …, Xn) for k = 0, 1, ..., n, can be defined as
and so forth, down to
(sometimes the notation σk is used instead of ek).
In general, for k ≥ 0 we define
Thus, for each positive integer
less than or equal to 
, there exists exactly one elementary symmetric polynomial of degree 
in 
variables. To form the one which has degree 
, we form all products of 
-tuples of the 
variables and add up these terms.
The fact that
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.
For n = 1:
For n = 2:
For n = 3:
For n = 4:
That is, when we substitute numerical values for the variables
, we obtain the monic univariate
polynomial (with variable λ) whose roots are the values substituted for
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
variables generates the ring
of symmetric polynomial
s in
variables. More specifically, the ring of symmetric polynomials with integer coefficients equals the integral polynomial ring 
(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 polynomial
s and complete homogeneous symmetric polynomial
s.
A denote the ring of symmetric polynomials in the variables
with coefficients in A by 
.
is a polynomial ring in the n elementary symmetric polynomials 
for k = 1, ..., n.
(Note that
is not among these polynomials; since 
, it cannot be member of any set of algebraically independent elements.)
This means that every symmetric polynomial
has a unique representation
for some polynomial
.
Another way of saying the same thing is that
is isomorphic to the polynomial ring 
through an isomorphism that sends 
to 
for 
.
s 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
variables and all symmetric polynomials in n variables with degree < d. Every homogeneous symmetric polynomial P in 
can be decomposed as a sum of homogeneous symmetric polynomials
Here the "lacunary part"
is defined as the sum of all monomials in P which contain only a proper subset of the n variables X1, ..., Xn, i.e., where at least one variable Xj is missing.
Because P is symmetric, the lacunary part is determined by its terms containing only the variables X1, ..., Xn−1, i.e., which do not contain Xn. These are precisely the terms that survive the operation of setting Xn to 0, so their sum equals
, which is a symmetric polynomial in the variables X1, ..., Xn−1 that we shall denote by 
. By the inductive assumption, this polynomial can be written as
for some
. Here the doubly indexed 
denote the elementary symmetric polynomials in n−1 variables.
Consider now the polynomial
Then
is a symmetric polynomial in X1, ..., Xn, of the same degree as 
, which satisfies
(the first equality holds because setting Xn to 0 in
gives 
, for all 
), 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 
of all variables, which equals the elementary symmetric polynomial 
. Then writing 
, 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
are algebraically independent over the ring A.)
The fact that the polynomial representation is unique implies that
is isomorphic to 
.
s in the variables lexicographically, where the individual variables are ordered , in other words the dominant term of a polynomial is one with the highest occurring power of , and among those the one with the highest power of , etc. Furthermore parametrize all products of elementary symmetric polynomials that have degree (they are in fact homogeneous) as follows by partitions of . Order the individual elementary symmetric polynomials in the product so that those with larger indices come first, then build for each such factor a column of boxes, and arrange those columns from left to right to form a Young diagram containing boxes in all. The shape of this diagram is a partition of , and each partition of arises for exactly one product of elementary symmetric polynomials, which we shall denote by ,…,) (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 .
Lemma. The leading term of is .
Now one proves by induction on the leading monomial in lexicographic order, that any nonzero homogenous symmetric polynomial of degree can be written as polynomial in the elementary symmetric polynomials. Since is symmetric, its leading monomial has weakly decreasing exponents, so it is some with a partition of . Let the coefficient of this term be , then 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 to it, one obtains the sought for polynomial expression for .
The fact that this expression is unique, or equivalently that all the products (monomials) 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 were zero, one focusses on the contribution in the linear combination with nonzero coefficient and with (as polynomial in the variables ) 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.
The symmetric polynomial
is a sum of monomials of the form 
, where the 
are nonnegative integers and 
is a scalar (i. e., an element of our ring A). We define a partial order on the monomials by specifying that
if
and there is some 
such that
for
but 
. For instance
and
. (You have probably realized that the coefficients 
and 
don't have any relevance in whether 
or not, as long as they are nonzero. It is the exponents that matter.) In words, starting in the nth position in
both monomials, go back until the two exponents are not equal. The monomial
with the larger exponent in that position is the larger monomial. This is
called a lexicographic order on the monomials.
We reduce P into elementary symmetric polynomials by successively
subtracting from P a product of elementary symmetric polynomials
eliminating the largest monomial according to this order without introducing
any larger monomials. This way, in each step, the largest monomial becomes
smaller and smaller until it becomes zero, and we are done: the sum of the
subtracted-off polynomials is the desired expression of P as a polynomial
function of elementary polynomials.
Here is how each step of this algorithm works: Suppose
is the largest monomial in
P. Then we must have
, since otherwise this monomial could not be the largest one of P (in fact, due to P being symmetric, the polynomial P must also have the monomial 
where 
is the sequence 
sorted in increasing order; but this monomial is larger than the monomial 
unless we have 
). Thus, we can define a symmetric polynomial R by
where
is the kth elementary symmetric polynomial in the
n variables
. Clearly R is a polynomial in the elementary symmetric polynomials. Now we claim that the largest monomial of R is 
. To prove this, we notice that the largest monomial of 
is clearly equal to
(since the largest monomial of
is 
for every i).
In this monomial, the variable
occurs with exponent 
(since it occurs with exponent 
in
the first term,
in the second term, and so on,
down to
times in the final term), the variable 
occurs with exponent 
(since it occurs with exponent 
in the second term, 
in the third term, and so on, down to 
times in the final term), and so on for the remaining
variables. Hence, this monomial must be
. Thus we have shown that the largest monomial of R is 
. Therefore, subtracting R from P eliminates the monomial 
, and all monomials of P-R are smaller than the one just eliminated. Thus, we have found a polynomial R, which is a polynomial in the symmetric polynomials, such that subtracting R from P leaves us with a new symmetric polynomial P-R whose largest monomial is smaller than that of P. We can now continue the process until nothing remains in P.
Here is an example of the above algorithm. Suppose
. Expanding
this into monomials, we get
The largest monomial is
, so we subtract off
, getting
Now the largest monomial is
, so we subtract off
,
getting
Now the largest monomial is
, so we subtract off
, getting
This gives
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, specifically in commutative algebra
Commutative algebra
Commutative algebra is the branch of abstract algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra...
, the elementary symmetric polynomials are one type of basic building block for symmetric polynomial
Symmetric polynomial
In mathematics, a symmetric polynomial is a polynomial P in n variables, such that if any of the variables are interchanged, one obtains the same polynomial...
s, 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 variables X1, …, Xn, written ek(X1, …, Xn) for k = 0, 1, ..., n, can be defined asand so forth, down to
(sometimes the notation σk is used instead of ek).
In general, for k ≥ 0 we define
Thus, for each positive integer
less than or equal to , there exists exactly one elementary symmetric polynomial of degree in variables. To form the one which has degree , we form all products of -tuples of the variables and add up these terms.The fact that
and so forth is the defining feature of commutative algebra. That is, the polynomial ringPolynomial 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 Hilbert basis theorem, to the construction of...
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, e0 = 1 is also one of the polynomials.)For n = 1:
For n = 2:
For n = 3:
For n = 4:
Properties
The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identityThat is, when we substitute numerical values for the variables
, we obtain the monic univariateUnivariate
In mathematics, univariate refers to an expression, equation, function or polynomial of only one variable. Objects of any of these types but involving more than one variable may be called multivariate...
polynomial (with variable λ) whose roots are the values substituted for
and whose coefficients are the elementary symmetric polynomials.The characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
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
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
and its applications and generalizations, like tensor algebra
Tensor algebra
In mathematics, the tensor algebra of a vector space V, denoted T or T•, is the algebra of tensors on V with multiplication being the tensor product...
and disciplines which extensively employ tensor fields, such as differential geometry.
The set of elementary symmetric polynomials in
variables generates the ringPolynomial 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 Hilbert basis theorem, to the construction of...
of symmetric polynomial
Symmetric polynomial
In mathematics, a symmetric polynomial is a polynomial P in n variables, such that if any of the variables are interchanged, one obtains the same polynomial...
s in
variables. More specifically, the ring of symmetric polynomials with integer coefficients equals the integral polynomial ring (See below for a more general statement and proof.) This fact is one of the foundations of invariant theoryInvariant theory
Invariant theory is a branch of abstract algebra dealing with actions of groups on algebraic varieties from the point of view of their effect on functions...
. For other systems of symmetric polynomials with a similar property see power sum symmetric polynomial
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 sum and difference of products of power sum symmetric...
s and complete homogeneous symmetric polynomial
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...
s.
The fundamental theorem of symmetric polynomials
For any commutative ringRing (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
A denote the ring of symmetric polynomials in the variables
with coefficients in A by . is a polynomial ring in the n elementary symmetric polynomials for k = 1, ..., n.(Note that
is not among these polynomials; since , it cannot be member of any set of algebraically independent elements.)This means that every symmetric polynomial
has a unique representationfor some polynomial
.Another way of saying the same thing is that
is isomorphic to the polynomial ring through an isomorphism that sends to for .Proof sketch
The theorem may be proved for symmetric homogeneous polynomialHomogeneous polynomial
In mathematics, a homogeneous polynomial is a polynomial whose monomials with nonzero coefficients all have thesame total degree. For example, x^5 + 2 x^3 y^2 + 9 x y^4 is a homogeneous polynomial...
s by a double mathematical induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
with respect to the number of variables n and, for fixed n, with respect to the degree
Degree of a polynomial
The degree of a polynomial represents the highest degree of a polynominal's terms , should the polynomial be expressed in canonical form . The degree of an individual term is the sum of the exponents acting on the term's variables...
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
variables and all symmetric polynomials in n variables with degree < d. Every homogeneous symmetric polynomial P in can be decomposed as a sum of homogeneous symmetric polynomialsHere the "lacunary part"
is defined as the sum of all monomials in P which contain only a proper subset of the n variables X1, ..., Xn, i.e., where at least one variable Xj is missing.Because P is symmetric, the lacunary part is determined by its terms containing only the variables X1, ..., Xn−1, i.e., which do not contain Xn. These are precisely the terms that survive the operation of setting Xn to 0, so their sum equals
, which is a symmetric polynomial in the variables X1, ..., Xn−1 that we shall denote by . By the inductive assumption, this polynomial can be written asfor some
. Here the doubly indexed denote the elementary symmetric polynomials in n−1 variables.Consider now the polynomial
Then
is a symmetric polynomial in X1, ..., Xn, of the same degree as , which satisfies(the first equality holds because setting Xn to 0 in
gives , for all ), 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 of all variables, which equals the elementary symmetric polynomial . Then writing , 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
are algebraically independent over the ring A.)The fact that the polynomial representation is unique implies that
is isomorphic to .An alternative proof
The following proof is also inductive, but does not involve other polynomials than those symmetric in ,...,, 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 ; different homogeneous components can be decomposed separately. Order the monomialMonomial
In mathematics, in the context of polynomials, the word monomial can have one of two different meanings:*The first is a product of powers of variables, or formally any value obtained by finitely many multiplications of a variable. If only a single variable x is considered, this means that any...
s in the variables lexicographically, where the individual variables are ordered , in other words the dominant term of a polynomial is one with the highest occurring power of , and among those the one with the highest power of , etc. Furthermore parametrize all products of elementary symmetric polynomials that have degree (they are in fact homogeneous) as follows by partitions of . Order the individual elementary symmetric polynomials in the product so that those with larger indices come first, then build for each such factor a column of boxes, and arrange those columns from left to right to form a Young diagram containing boxes in all. The shape of this diagram is a partition of , and each partition of arises for exactly one product of elementary symmetric polynomials, which we shall denote by ,…,) (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 .
Lemma. The leading term of is .
- Proof. To get the leading term of the product one must select the leading term in each factor , which is clearly , and multiply these together. 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…, 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 (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 of degree can be written as polynomial in the elementary symmetric polynomials. Since is symmetric, its leading monomial has weakly decreasing exponents, so it is some with a partition of . Let the coefficient of this term be , then 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 to it, one obtains the sought for polynomial expression for .
The fact that this expression is unique, or equivalently that all the products (monomials) 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 were zero, one focusses on the contribution in the linear combination with nonzero coefficient and with (as polynomial in the variables ) 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.
A Self-Contained Algorithmic Proof
The following proof of the existence (not of the uniqueness) of Q is the same as the above, but rewritten in elementary terms and with slightly different choice of lexicographic order.The symmetric polynomial
is a sum of monomials of the form , where the are nonnegative integers and is a scalar (i. e., an element of our ring A). We define a partial order on the monomials by specifying thatif
and there is some such that for but . For instance and. (You have probably realized that the coefficients and don't have any relevance in whether or not, as long as they are nonzero. It is the exponents that matter.) In words, starting in the nth position inboth monomials, go back until the two exponents are not equal. The monomial
with the larger exponent in that position is the larger monomial. This is
called a lexicographic order on the monomials.
We reduce P into elementary symmetric polynomials by successively
subtracting from P a product of elementary symmetric polynomials
eliminating the largest monomial according to this order without introducing
any larger monomials. This way, in each step, the largest monomial becomes
smaller and smaller until it becomes zero, and we are done: the sum of the
subtracted-off polynomials is the desired expression of P as a polynomial
function of elementary polynomials.
Here is how each step of this algorithm works: Suppose
is the largest monomial inP. Then we must have
, since otherwise this monomial could not be the largest one of P (in fact, due to P being symmetric, the polynomial P must also have the monomial where is the sequence sorted in increasing order; but this monomial is larger than the monomial unless we have ). Thus, we can define a symmetric polynomial R bywhere
is the kth elementary symmetric polynomial in then variables
. Clearly R is a polynomial in the elementary symmetric polynomials. Now we claim that the largest monomial of R is . To prove this, we notice that the largest monomial of is clearly equal to(since the largest monomial of
is for every i).In this monomial, the variable
occurs with exponent (since it occurs with exponent inthe first term,
in the second term, and so on,down to
times in the final term), the variable occurs with exponent (since it occurs with exponent in the second term, in the third term, and so on, down to times in the final term), and so on for the remainingvariables. Hence, this monomial must be
. Thus we have shown that the largest monomial of R is . Therefore, subtracting R from P eliminates the monomial , and all monomials of P-R are smaller than the one just eliminated. Thus, we have found a polynomial R, which is a polynomial in the symmetric polynomials, such that subtracting R from P leaves us with a new symmetric polynomial P-R whose largest monomial is smaller than that of P. We can now continue the process until nothing remains in P.Here is an example of the above algorithm. Suppose
. Expandingthis into monomials, we get
The largest monomial is
, so we subtract off, gettingNow the largest monomial is
, so we subtract off,getting
Now the largest monomial is
, so we subtract off, gettingThis gives