Elimination theory
Encyclopedia
In commutative algebra
and algebraic geometry
, elimination theory is the classical name for algorithmic approaches to eliminating between polynomial
s of several variables.
The linear case would now routinely be handled by Gaussian elimination
, rather than the theoretical solution provided by Cramer's rule
. In the same way, computational techniques for elimination can in practice be based on Gröbner basis
methods. There is however older literature on types of eliminant, including resultants to find common roots of polynomials, discriminant
s and so on. In particular the discriminant appears in invariant theory
, and is often constructed as the invariant of either a curve or an n-ary k-ic form. Whilst discriminants are always constructed resultants, the variety of constructions and their meaning tends to vary. A modern and systematic version of theory of the discriminant has been developed by Gelfand
and coworkers. Some of the systematic methods have a homological
basis, that can be made explicit, as in Hilbert's theorem on syzygies
. This field is at least as old as Bézout's theorem
.
The historical development of commutative algebra
, which was initially called ideal
theory, is closely linked to concepts in elimination theory: ideas of Kronecker
, who wrote a major paper on the subject, were adapted by Hilbert
and effectively 'linearised' while dropping the explicit constructive content. The process continued over many decades: the work of F.S. Macaulay
who gave his name to Cohen-Macaulay modules was motivated by elimination.
There is also a logical content to elimination theory, as seen in the Boolean satisfiability problem
. In the worst case it is presumably hard to eliminate variables computationally. Elimination of quantifiers is a term used in mathematical logic
to explain that in some cases—algebraic geometry
of projective space
over an algebraically closed field
being one—existential quantifiers
can be removed. The content of this, in the geometric case, is that an algebraic correspondence (i.e., a Zariski-closed relation) between two projective space
s projects to a Zariski-closed set: the condition on x that x R y for some y is a polynomial condition on x. There is some historical evidence that this fact influenced Hilbert's thinking about the prospects for proof theory
.
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...
and algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
, elimination theory is the classical name for algorithmic approaches to eliminating between polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s of several variables.
The linear case would now routinely be handled by Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
, rather than the theoretical solution provided by Cramer's rule
Cramer's rule
In linear algebra, Cramer's rule is a theorem, which gives an expression for the solution of a system of linear equations with as many equations as unknowns, valid in those cases where there is a unique solution...
. In the same way, computational techniques for elimination can in practice be based on Gröbner basis
Gröbner basis
In computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating subset of an ideal I in a polynomial ring R...
methods. There is however older literature on types of eliminant, including resultants to find common roots of polynomials, discriminant
Discriminant
In algebra, the discriminant of a polynomial is an expression which gives information about the nature of the polynomial's roots. For example, the discriminant of the quadratic polynomialax^2+bx+c\,is\Delta = \,b^2-4ac....
s and so on. In particular the discriminant appears in invariant theory
Invariant 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...
, and is often constructed as the invariant of either a curve or an n-ary k-ic form. Whilst discriminants are always constructed resultants, the variety of constructions and their meaning tends to vary. A modern and systematic version of theory of the discriminant has been developed by Gelfand
Israel Gelfand
Israel Moiseevich Gelfand, also written Israïl Moyseyovich Gel'fand, or Izrail M. Gelfand was a Soviet mathematician who made major contributions to many branches of mathematics, including group theory, representation theory and functional analysis...
and coworkers. Some of the systematic methods have a homological
Homological algebra
Homological algebra is the branch of mathematics which studies homology in a general algebraic setting. It is a relatively young discipline, whose origins can be traced to investigations in combinatorial topology and abstract algebra at the end of the 19th century, chiefly by Henri Poincaré and...
basis, that can be made explicit, as in Hilbert's theorem on syzygies
Hilbert's syzygy theorem
In mathematics, Hilbert's syzygy theorem is a result of commutative algebra, first proved by David Hilbert in connection with the syzygy problem of invariant theory. Roughly speaking, starting with relations between polynomial invariants, then relations between the relations, and so on, it...
. This field is at least as old as Bézout's theorem
Bézout's theorem
Bézout's theorem is a statement in algebraic geometry concerning the number of common points, or intersection points, of two plane algebraic curves. The theorem claims that the number of common points of two such curves X and Y is equal to the product of their degrees...
.
The historical development of 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...
, which was initially called ideal
Ideal (ring theory)
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring. The ideal concept allows the generalization in an appropriate way of some important properties of integers like "even number" or "multiple of 3"....
theory, is closely linked to concepts in elimination theory: ideas of Kronecker
Leopold Kronecker
Leopold Kronecker was a German mathematician who worked on number theory and algebra.He criticized Cantor's work on set theory, and was quoted by as having said, "God made integers; all else is the work of man"...
, who wrote a major paper on the subject, were adapted by Hilbert
David Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
and effectively 'linearised' while dropping the explicit constructive content. The process continued over many decades: the work of F.S. Macaulay
Francis Sowerby Macaulay
Francis Sowerby Macaulay FRS was an English mathematician who made significant contributions to algebraic geometry. He is most famous for his 1916 book, The Algebraic Theory of Modular Systems, which greatly influenced the later course of algebraic geometry...
who gave his name to Cohen-Macaulay modules was motivated by elimination.
There is also a logical content to elimination theory, as seen in the Boolean satisfiability problem
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
. In the worst case it is presumably hard to eliminate variables computationally. Elimination of quantifiers is a term used in mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
to explain that in some cases—algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
of projective space
Projective space
In mathematics a projective space is a set of elements similar to the set P of lines through the origin of a vector space V. The cases when V=R2 or V=R3 are the projective line and the projective plane, respectively....
over an algebraically closed field
Algebraically closed field
In mathematics, a field F is said to be algebraically closed if every polynomial with one variable of degree at least 1, with coefficients in F, has a root in F.-Examples:...
being one—existential quantifiers
Existential quantification
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ , which is called the existential quantifier...
can be removed. The content of this, in the geometric case, is that an algebraic correspondence (i.e., a Zariski-closed relation) between two projective space
Projective space
In mathematics a projective space is a set of elements similar to the set P of lines through the origin of a vector space V. The cases when V=R2 or V=R3 are the projective line and the projective plane, respectively....
s projects to a Zariski-closed set: the condition on x that x R y for some y is a polynomial condition on x. There is some historical evidence that this fact influenced Hilbert's thinking about the prospects for proof theory
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
.