Power Sum Article Index for
Power 		Shopping
Identities 		Website Links For
Newtons 		 

Information About

Power Sum
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




MATHEMATICAL STATEMENT

Consider the polynomial
: p(\lambda) = \prod_{\alpha=1}^n \left( \lambda - x_\alpha ight) = \sum_{j=0}^n a_j \lambda^j
where the x_\alpha are the roots and the a_j are the Coefficients .
Frequently, this polynomial is regarded as the Characteristic Polynomial of a Linear Operator or Matrix ; then the roots are called Eigenvalue s.

Define the ''power sums''
: t_j = \sum_{\alpha=1}^n x_\alpha^j
If we regard the roots as eigenvalues of a matrix A, then these quantities are the Trace s of the powers of the matrix
:t_j = { m tr} \, \left( A^j ight).

Then the original form of Newton's identities is the recurrence
:t_1 = a_1\,
:t_2 = a_1 t_1 - 2 a_2\,
:t_3 = a_1 t_2 - a_2 t_1 + 3 a_3\,
:t_4 = a_1 t_3 - a_2 t_2 + a_3 t_1 - 4 a_4\,
:t_5 = a_1 t_4 - a_2 t_3 + a_3 t_2 - a_4 t_1 + 5 a_5\,
where the pattern is obvious. For an elementary proof see the book by Tignol cited below.

From these formulae we can readily obtain more useful formulae, expressing the power sums in terms of the coefficients:
:t_1 = a_1\,
:t_2 = a_1^2 - 2 a_2
:t_3 = a_1^3 - 3 a_1 a_2 + 3 a_3
:t_4 = a_1^4 - 4 a_1^2 a_2 + 4 a_1 a_3 + 2 a_2^2 - 4 a_4
Unfortunately, these formulae have the disadvantage that the pattern is no longer obvious.

Finally, we can solve to obtain expressions giving the coefficients in terms of the power sums:
:a_1 = t_1\,
:a_2 = rac{1}{2} \left( t_1^2 - t_2 ight)
:a_3 = rac{1}{6} \left( t_1^3 - 3 t_1 t_2 + 2 t_3 ight)
:a_4 = rac{1}{24} \left( t_1^4 - 6 t_1^2 t_2 + 3 t_2^2 + 8 t_1 t_3 - 6 t_4 ight)
and so forth, where we can see a partial pattern (factorials in the denominator, first term and last term), but again the general pattern is probably not obvious. But if you know about the theory of finite groups, take a hard second look! (Spoiler in a subsequent section.)

Newton seems to have left it there, and hence missed some lovely discoveries.


RELATION WITH INVARIANT THEORY

Invariant theory is concerned with polynomial invariants of various algebraic or geometric objects in mathematics, including polynomial invariants of Quadratic Form s, and more generally, polynomial invariants of Tensor s. From the latter, we obtain connections with the Representation Theory of groups.

A fundamental topic in invariant theory concerns the Symmetric Polynomial s, which arise when we express the coefficients of a polynomial in terms of its roots. That is, multiplying out
:p(\lambda) = \prod_{\alpha=1}^n \left( \lambda - x_\alpha ight)
we have
:\alpha_1 = -\sum_{j} x_j\,
:\alpha_2 = \sum_{j < k} x_j \, x_k
:\alpha_3 = -\sum_{j < k < \ell} x_j \, x_k \, x_\ell
and so forth. In particular, we can use such expressions to obtain the characteristic polynomial of a linear operator if we know its eigenvalues.

Now the point for the theory of invariants is that if we consider the \alpha_j(x_1,x_2,\dots) to be ''polynomials in the roots'', then for a given n they form a Basis for the space of symmetric polynomial functions of the roots. That is, every polynomial function of the roots which is invariant under any permutation of the roots, such as exchanging x_1, x_2, is given by a specific linear combination of the \alpha_j. For this reason, \alpha_1, \, \alpha_2, \dots \alpha_n are called the ''elementary symmetric polynomials''.

The point is that the expressions above give a ''different basis'' for the space of symmetric polynomials, namely
: au_1 = \alpha_1\,
: au_2 = \alpha_1^2 - 2 \alpha_2
: au_3 = \alpha_1^3 - 3 \alpha_1 \alpha_2 + 3 \alpha_3
: au_4 = \alpha_1^4 - 4 \alpha_1^2 \alpha_2 + 4 \alpha_1 \alpha_3 + 2 \alpha_2^2 - 4 \alpha_4
and so forth, where au_j is of course simply the sum of the j-th powers of the roots. The fact that we can obtain in this way two distinct ways of representing all symmetric functions of the roots of a polynomial, without knowing the roots themselves, is of fundamental importance for Galois theory.

We can obtain "finer" decompositions by writing general symmetric polynomials as sums of Homogeneous Polynomial s; that is, a symmetric polynomial in which all the terms have the same Degree . A convenient basis for the homogeneous symmetric polynomials is given by the Schur Polynomial s, which correspond to the Partition s of an integer, which can be enumerated by '' Ferrers Diagram s'' (this is the "unlabeled" combinatorial concept corresponding to Young Diagram s). For example, corresponding to the partition 4+2+1 = 7, we have the Schur polynomial
: \sigma_{4,2,1} (x_1, x_2, x_3) = rac{\det \left \begin{matrix} x_1^6 & x_2^6 & x_3^6 \ x_1^3 & x_2^3 & x_3^3 \ x_1 & x_2 & x_3 \end{matrix} ight }{\det \left \begin{matrix} x_1^2 & x_2^2 & x_3^2 \ x_1 & x_2 & x_3 \ 1 & 1 & 1 \end{matrix} ight }
which is a homogeneous symmetric ''polynomial'' of degree seven in three variables. Amazingly enough, the determinant in the denominator cancels out when everything is fully expanded:
: \sigma_{4,2,1} (x_1, x_2, x_3) = x_1 \, x_2 \, x_3 \; \left( x_1^3 \, x_2 + x_1 \, x_2^3 + x_1^3 \, x_3 + x_1 \, x_3^3 + x_2^3 \, x_3 + x_2 \, x_3^3 ight.
: \; \; \; \left. + x_1^2 \, x_2^2 + x_1^2 \, x_3^2 + x_2^2 \, x_3^2 + 2 \, (x_1^2 \, x_2 \, x_3 + x_1 \, x_2^2 \, x_3 + x_1 \, x_2 \, x_3^2) ight)
There are three other partitions of seven into three parts, so the space of homogeneous polynomials of degree seven in three variables has dimension four, with each polynomial uniquely expressible as a ''linear combination'' of four Schur polynomials. Each of these Schur polynomials can expressed in turn as an ''algebraic combination'' of (a polynomial function of) the three elementary symmetric polynomials in three variables, \alpha_1, \, \alpha_2, \, \alpha_3 .


RELATION WITH SYMMETRIC GROUPS

The alert reader with some knowledge of the theory of Finite Group s, particularly the Pólya Enumeration Formula , will have noticed two striking facts in the discussion above:

  • the Schur polynomials are defined in terms of integer partitions (or Ferrers diagrams), which correspond to the Conjugacy Class es of the Symmetric Group ,

  • up to alternating signs, the expressions found above giving the coefficients in terms of the power sums are exactly the Cycle Index Polynomial s of the symmetric groups.


This is no coincidence. Joseph Lagrange (and, with a little prior explanation, Isaac Newton) would have immediately understood the statement of the following theorem, which was found by George Pólya in the 1930s: define the ''characteristic function''
: F(u,t_1,t_2,\dots) = \prod_\alpha \left( u - x_\alpha ight) = \sum_{n=0}^\infty a_n u^n
where the x_\alpha are symbols which we think of as formal "roots" of the characteristic function, which we think of as a Generating Function for the coefficients a_j. Define also the ''alternating power sums''
: t_j = (-1)^{j+1} \, \sum_\alpha x_\alpha^j
(The alternating signs arise from the fact that transpositions or two-cycles are ''odd'' permutations, three-cycles are ''even permutations'', and so forth.) Then the characteristic function is given by
: F(u,t_1,t_2,\dots) = \exp \left( \sum_{m=1}^\infty rac{t_m}{m} \, u^m ight)
If you expand the right hand side as the first few terms of a Taylor series in the variable u (you need only write out the first few terms in the exponent), you will obtain the cycle index polynomials of the first few symmetric groups! And, up to alternating signs, these agree with the expressions we found earlier giving the coefficients of the characteristic polynomial of a linear operator in terms of the traces of the powers of the operator. Taking sufficiently many terms in the power series, one can efficiently obtain the cycle index of any symmetric group from Pólya's formula.


RELATION WITH ENUMERATIVE COMBINATORICS

Enumerative combinatorics concerns counting things, usually things defined by some kind of Recursive construction. Examples include:
  • the number of ways of partitioning the natural number ''n'' as a sum of natural numbers,

  • the number of ''n''-node binary ''forests'',

  • the number of ''sparse digraphs'', which are Digraph s with ''n''-nodes, having either one or two edges coming into each node.

    • In each of these examples, the answer to the counting problem is a particular function of the natural number ''n'', taking values in the natural numbers. Almost invariably, the most elegant way of solving such problems is to use the technique of Generating Function s which was introduced by the infatigable Leonhard Euler .


In recent years, with the rise of Category Theory , a highly abstract way of thinking about generating functions has been introduced by André Joyal , in which a generalization of Pólya's cycle index polynomials has been introduced. These Joyal index functions are defined in terms of Structor s (also known as Combinatorial Species ). These are certain Functor s which elegantly and precisely express the combinatorial notion of a ''recursive construction''. The Joyal index functions really are a natural generalization of the Pólya index function to an ''oligomorphic group'', a type of tractable infinite permutation group. This in turn leads to a beautiful connection with First-order Logic .

Often, connected with a counting problem like those already mentioned, we have a closely related problem, counting
  • the number of ''n''-node binary Tree s (connected forests),

  • the number of ''connected'' sparse digraphs.

    • Also, we may want to solve more precise counting problems, such as counting

  • the number of ways of partitioning the natural number ''n'' as a sum of ''k'' natural numbers,

  • the number of ''n''-node binary forests containing ''k'' trees.

    • It turns out that such problems are related to the original problems by formulas resembling the Pólya formula given in the previous section. Maximal information is obtained when we can find the Joyal index of the ''connected structor'' obtained from a more complicated structure, or when we can obtain an ''attribute index function'' enumerating in terms of some integer valued attribute.



RELATION WITH COMPUTATIONAL ALGEBRAIC GEOMETRY

Algebraic geometry is primarily concerned with the algebraic problem of finding the roots of systems of polynomials in many variables and the geometric interpretation of this problem in terms of Algebraic Varieties . A fundamental computational technique for algebraic geometry, which has far-reaching implications in many other fields of mathematics, including Differential Equation s, is the notion of a Gröbner Basis . For our purposes we don't need to know precisely what these are, we need only know that Buchberger's Algorithm for obtaining a Gröbner basis generalizes two of the most fundamental algorithms in mathematics:
  • Gauss's algorithm for obtaining the Row Reduction of a matrix,

  • division algorithm for dividing a polynomial in ''one'' variable by another such polynomial.

    • The resulting Gröbner basis of an Ideal in a Ring of multivariable polynomials

is analogous to a Vector Basis for a Subspace of Vector Space , and is ideally suited for computations involving ideals in polynomial rings, which is the basis concept of algebraic geometry. Indeed, the famous Nullstellensatz of David Hilbert establishes a perfect correspondence between a fundamental algebraic concept, the ideals of a nice kind of ring, and an equally fundamental geometric concept, Varieties in an Affine Space , or even in a Projective Space .

Gröbner bases are defined with respect to choice of a certain ''term order'' (which specifies "priority" among Monomial s in carrying out the generalized division algorithm), and one of the most useful choices for algebraic geometry is an ''elimination order''. In particular, using an elimination order we can solve a system of equations such as the identities giving the power sums in terms of the coefficients, to obtain equations giving the coefficients in terms of the power sums. Needless to say, we obtain the expressions found above.


SEE ALSO



REFERENCES

  • 1 A readable, historically oriented introduction to Galois theory.


  • 2 A fascinating introduction to permutation groups, including the Pólya cycle index, oligomorphic permutation groups, and the connection with mathematical logic.


  • 3 A fairly readable monograph, which may leave the incorrect impression that this seemingly abstract approach has no practical advantages over more conventional approaches to generating function techniques.


  • 4 A delightful monograph explaining the application of Gröbner bases to the invariant theory of finite groups, including Schur polynomials and an approach to Galois theory using invariants.


  • 5 A beautiful introduction to algebraic geometry using Gröbner bases, including a chapter on invariants of finite groups.


  • 6 One of the most elementary and readable textbooks discussing Pólya's enumeration formula and cycle index polynomials.