NationMaster - Encyclopedia: Newton's identities

In mathematics, Newton's identities relate two different ways of describing the roots of a polynomial. They were found by Isaac Newton in about 1666, apparently in ignorance of earlier work (1629) by Albert Girard. These useful identities have immediate applications in many areas of mathematics, including Galois theory, invariant theory, group theory, combinatorics, as well as further applications outside mathematics, including general relativity. They can be considered as applications of ideas in computational algebraic geometry, particularly Gröbner bases. Mathematics is often defined as the study of topics such as quantity, structure, space, and change. ... In mathematics, a root (or a zero) of a function f is an element x in the domain of f such that f(x) = 0. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ... Sir Isaac Newton, PRS (4 January [O.S. 25 December 1642] 1643 â€“ 31 March [O.S. 20 March] 1727) was an English physicist, mathematician, astronomer, alchemist, inventor and natural philosopher who is regarded by many as the most influential scientist in history. ... Events September 2 - Great Fire of London: A large fire breaks out in London in the house of Charles IIs baker on Pudding Lane near London Bridge. ... Albert Girard (1595â€“1632) was a French-born mathematician. ... In mathematics, Galois theory is a branch of abstract algebra. ... In mathematics, invariant theory refers to the study of invariant algebraic forms (equivalently, symmetric tensors) for the action of linear transformations. ... Group theory is that branch of mathematics concerned with the study of groups. ... Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. ... General relativity (GR) is the geometrical theory of gravitation published by Albert Einstein in 1915. ... Algebraic geometry is a branch of mathematics which, as the name suggests, combines abstract algebra, especially commutative algebra, with geometry. ... In computer algebra, computational algebraic geometry, and computational commutative algebra, a GrÃ¶bner basis G (named after Wolfgang GrÃ¶bner) is a particular kind of generating subset of an ideal I in a polynomial ring R. One can view it as a multivariate, non-linear generalization of: the Euclidean algorithm...

1 Mathematical statement
2 Relation with invariant theory
3 Relation with symmetric groups
4 Relation with enumerative combinatorics
5 Relation with computational algebraic geometry
6 See also
7 References

Mathematical statement

Consider the polynomial

$p(lambda) = prod_{alpha=1}^n left( lambda - x_alpha right) = sum_{j=0}^n a_j lambda^j$

where the $x α$ 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 eigenvalues. In mathematics, a coefficient is a multiplicative factor that belongs to a certain object such as a variable (for example, the coefficients of a polynomial), a basis vector, a basis function and so on. ... In linear algebra, one associates a polynomial to every square matrix, its characteristic polynomial. ... In mathematics, a linear transformation (also called linear operator or linear map) is a function between two vector spaces that respects the arithmetical operations addition and scalar multiplication defined on vector spaces, or, in other words, it preserves linear combinations. Definition and first consequences Formally, if V and W are... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, of elements of a ring-like algebraic structure. ... In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...

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 traces of the powers of the matrix In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal (the diagonal from the upper left to the lower right) of A, i. ...

$t_j = {rm tr} , left( A^j right)$ .

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 = frac{1}{2} left( t_1^2 - t_2 right)$

$a_3 = frac{1}{6} left( t_1^3 - 3 t_1 t_2 + 2 t_3 right)$

$a_4 = frac{1}{24} left( t_1^4 - 6 t_1^2 t_2 + 3 t_2^2 + 8 t_1 t_3 - 6 t_4 right)$

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 forms, and more generally, polynomial invariants of tensors. From the latter, we obtain connections with the representation theory of groups. In mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables. ... In mathematics, a tensor is a generalized quantity or a certain kind of geometrical entity that includes all the ideas of scalars, vectors, matrices and linear operators. ... In mathematics Representation theory is the name given to the study of standard representations of abstract mathematical structures. ...

A fundamental topic in invariant theory concerns the symmetric polynomials, which arise when we express the coefficients of a polynomial in terms of its roots. That is, multiplying out In mathematics, a symmetric polynomial is a polynomial in n variables , such that if some of the variables are interchanged, the polynomial stays the same. ...

$p(lambda) = prod_{alpha=1}^n left( lambda - x_alpha right)$

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 $α j$ . For this reason, $alpha_1, , alpha_2, dots alpha_n$ are called the elementary symmetric polynomials. In linear algebra, a basis is a minimum set of vectors that, when combined, can address every vector in a given space. ...

The point is that the expressions above give a different basis for the space of symmetric polynomials, namely

$tau_1 = alpha_1,$

$tau_2 = alpha_1^2 - 2 alpha_2$

$tau_3 = alpha_1^3 - 3 alpha_1 alpha_2 + 3 alpha_3$

$tau_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 $τ 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 polynomials; 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 polynomials, which correspond to the partitions of an integer, which can be enumerated by Ferrers diagrams (this is the "unlabeled" combinatorial concept corresponding to Young diagrams). For example, corresponding to the partition 4+2+1 = 7, we have the Schur polynomial In mathematics, homogeneous has a variety of meanings. ... This article is about the term degree as used in mathematics. ... In commutative algebra and invariant theory, Schur polynomials are certain homogeneous symmetric polynomials. ... This is a list of partition topics, in the mathematical sense. ... In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ... In mathematics, a Young tableau is a combinatorial object useful in representation theory. ...

$sigma_{4,2,1} (x_1, x_2, x_3) = frac{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} right] }{det left[ begin{matrix} x_1^2 & x_2^2 & x_3^2 x_1 & x_2 & x_3 1 & 1 & 1 end{matrix} right] }$

which is a homogenous 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 right.$

$; ; ; 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) right)$

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 groups, particularly the Pólya enumeration formula, will have noticed two striking facts in the discussion above: In mathematics, a finite group is a group which has finitely many elements. ... Burnsides lemma, sometimes also called Burnsides counting theorem, PÃ³lyas formula, the Cauchy-Frobenius lemma or the orbit-counting theorem, is a result in group theory which is often useful in taking account of symmetry when counting mathematical objects. ...

the Schur polynomials are defined in terms of integer partitions (or Ferrers diagrams), which correspond to the conjugacy classes 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 polynomials 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 In mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure. ... In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functions from X to X, in which the group operation is that of composition of functions, i. ... Joseph Louis Lagrange (January 25, 1736 – April 10, 1813) was an Italian mathematician and astronomer who later lived in France and Prussia. ... George PÃ³lya (December 13, 1887 - September 7, 1985, in Hungarian PÃ³lya GyÃ¶rgy) was a mathematician, who was born in Budapest, Hungary and died in Palo Alto, USA. He worked on a great variety of mathematical topics, including series, number theory, combinatorics, and probability. ...

$F(u,t_1,t_2,dots) = prod_alpha left( u - x_alpha right) = sum_{n=0}^infty a_n u^n$

where the $x α$ 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 In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...

$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 frac{t_m}{m} , u^m right)$

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: See: Recursion Recursively enumerable language Recursively enumerable set Recursive filter Recursive function Recursive set Primitive recursive function This is a disambiguation page â€” a list of pages that otherwise might share the same title. ...

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 digraphs 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 functions which was introduced by the infatigable Leonhard Euler. This article just presents the basic definitions. ... In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

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 structors (also known as combinatorial species). These are certain functors 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. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them. ... This article is about a concept in combinatorial mathematics. ... Did somebody just say functor? In category theory, a functor is a special type of mapping between categories. ... First-order predicate calculus or first-order logic (FOL) permits the formulation of quantified statements such as there exists an x such that. ...

Often, connected with a counting problem like those already mentioned, we have a closely related problem, counting

the number of n-node binary trees (connected forests),
the number of connected sparse digraphs.

Also, we may want to solve more precise counting problems, such as counting A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

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 equations, 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: In classical algebraic geometry (and to some extent also in modern algebraic geometry), the main objects of study are algebraic varieties. ... In mathematics, a differential equation is an equation in which the derivatives of a function appear as variables. ... In computer algebra, computational algebraic geometry, and computational commutative algebra, a GrÃ¶bner basis G (named after Wolfgang GrÃ¶bner) is a particular kind of generating subset of an ideal I in a polynomial ring R. One can view it as a multivariate, non-linear generalization of: the Euclidean algorithm... In computational algebraic geometry and computational commutative algebra, Buchbergers algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. ...

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. In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ... In mathematics, the term ideal has multiple meanings. ... In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have similar (but not identical) properties to those familiar from the integers. ... In linear algebra, a basis is a minimum set of vectors that, when combined, can address every vector in a given space. ... Screenshot (from SSCX Star Warzone). ... A vector space (or linear space) is the basic object of study in the branch of mathematics called linear algebra. ... Hilberts Nullstellensatz (German: theorem of zeros) is a theorem in algebraic geometry that relates varieties and ideals in polynomial rings over algebraically closed fields. ... David Hilbert David Hilbert (January 23, 1862 â€“ February 14, 1943) was a German mathematician born in Wehlau, near KÃ¶nigsberg, Prussia (now Znamensk, near Kaliningrad, Russia) who is recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ... Variety (linguistics) is a concept that includes for instance dialects, standard language and jargon. ... In mathematics, an affine space is an abstract structure that generalises the affine-geometric properties of Euclidean space. ... In mathematics, a projective space is a fundamental construction from any vector space. ...

Gröbner bases are defined with respect to choice of a certain term order (which specifies "priority" among monomials 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. In mathematics, a monomial is a particular kind of polynomial, having just one term. ...

References

[[|Tignol, Jean-Pierre, ]], () ( 2001). "" [ Galois's theory of algebraic equations], , , , : Singapore: World Scientific. ISBN 981-02-4561-6.. A readable, historically oriented introduction to Galois theory.

[[|Cameron, Peter J., ]], () ( 1999). "" [ Permutation Groups], , , , : Cambridge: Cambridge University Press. ISBN 0-521-65378-9.. A fascinating introduction to permutation groups, including the Pólya cycle index, oligomorphic permutation groups, and the connection with mathematical logic.

[[|Bergeron, F.; Labelle, G.; and Leroux, P., ]], () ( 1998). "" [ Combinatorial species and tree-like structures], , , , : Cambridge: Cambridge University Press. ISBN 0-521-57323-8.. 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.

[[|Sturmfels, Bernd, ]], () ( 1992). "" [ Algorithms in Invariant Theory], , , , : New York:Springer-Verlag. ISBN 0-387-84445-6.. 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.

[[|Cox, David; Little, John, and O'Shea, Donal, ]], () ( 1992). "" [ Ideals, Varieties, and Algorithms], , , , : New York:Springer-Verlag. ISBN 0-387-97847-X.. A beautiful introduction to algebraic geometry using Gröbner bases, including a chapter on invariants of finite groups.

[[|Tucker, Alan, ]], () ( 1980). "" [ Applied Combinatorics], , , , : New York:Wiley. ISBN 0-471086371-8.. One of the most elementary and readable textbooks discussing Pólya's enumeration formula and cycle index polynomials.

Categories: Linear algebra | Invariant theory | Group theory | Symmetric functions | Identities

Results from FactBites:

Vector (spatial) - Wikipedia, the free encyclopedia (3080 words)
	Informally, a vector is a quantity characterized by a magnitude (in mathematics a number, in physics a number times a unit) and a direction, often represented graphically by an arrow.
	Examples are "moving north at 90 km/h" or "pulling towards the center of Earth with a force of 70 newtons".
	Thus there is typically consistency in scale among quantities of the same dimension, but otherwise scale ratios may vary; for example, if "1 newton" and "5 m" are both represented with an arrow of 2cm, the scales are 1:250 and 1m:50N respectively.

More results at FactBites »

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Mathematical statement GA_googleFillSlot("encyclopedia_square");