Elimination theory

Last updated

In commutative algebra and algebraic geometry, elimination theory is the classical name for algorithmic approaches to eliminating some variables between polynomials of several variables, in order to solve systems of polynomial equations.

Contents

Classical elimination theory culminated with the work of Francis Macaulay on multivariate resultants, as described in the chapter on Elimination theory in the first editions (1930) of Bartel van der Waerden's Moderne Algebra . After that, elimination theory was ignored by most algebraic geometers for almost thirty years, until the introduction of new methods for solving polynomial equations, such as Gröbner bases, which were needed for computer algebra.

History and connection to modern theories

The field of elimination theory was motivated by the need of methods for solving systems of polynomial equations.

One of the first results was Bézout's theorem, which bounds the number of solutions (in the case of two polynomials in two variables at Bézout time).

Except for Bézout's theorem, the general approach was to eliminate variables for reducing the problem to a single equation in one variable.

The case of linear equations was completely solved by Gaussian elimination, where the older method of Cramer's rule does not proceed by elimination, and works only when the number of equations equals the number of variables. In the 19th century, this was extended to linear Diophantine equations and abelian group with Hermite normal form and Smith normal form.

Before the 20th century, different types of eliminants were introduced, including resultants , and various kinds of discriminants . In general, these eliminants are also invariant under various changes of variables, and are also fundamental in invariant theory.

All these concepts are effective, in the sense that their definitions include a method of computation. Around 1890, David Hilbert introduced non-effective methods, and this was seen as a revolution, which led most algebraic geometers of the first half of the 20th century to try to "eliminate elimination". Nevertheless Hilbert's Nullstellensatz, may be considered to belong to elimination theory, as it asserts that a system of polynomial equations does not have any solution if and only if one may eliminate all unknowns to obtain the constant equation 1 = 0.

Elimination theory culminated with the work of Leopold Kronecker, and finally Macaulay, who introduced multivariate resultants and U-resultants, providing complete elimination methods for systems of polynomial equations, which are described in the chapter on Elimination theory in the first editions (1930) of van der Waerden's Moderne Algebra .

Later, elimination theory was considered old-fashioned and removed from subsequent editions of Moderne Algebra. It was generally ignored until the introduction of computers, and more specifically of computer algebra, which again made relevant the design of efficient elimination algorithms, rather than merely existence and structural results. The main methods for this renewal of elimination theory are Gröbner bases and cylindrical algebraic decomposition, introduced around 1970.

Connection to logic

There is also a logical facet to elimination theory, as seen in the Boolean satisfiability problem. In the worst case, it is presumably hard to eliminate variables computationally. Quantifier elimination is a term used in mathematical logic to explain that, in some theories, every formula is equivalent to a formula without quantifier. This is the case of the theory of polynomials over an algebraically closed field, where elimination theory may be viewed as the theory of the methods to make quantifier elimination algorithmically effective. Quantifier elimination over the reals is another example, which is fundamental in computational algebraic geometry.

See also

Related Research Articles

Algebraic geometry Branch of mathematics

Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical problems about these sets of zeros.

Magma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma. It runs on Unix-like operating systems, as well as Windows.

Bézout's theorem is a statement in algebraic geometry concerning the number of common zeros of n polynomials in n indeterminates. In its original form the theorem states that in general the number of common zeros equals the product of the degrees of the polynomials. It is named after Étienne Bézout.

Emmy Noether German mathematician

Amalie Emmy Noether was a German mathematician who made many important contributions to abstract algebra. She discovered Noether's theorem, which is fundamental in mathematical physics. She was described by Pavel Alexandrov, Albert Einstein, Jean Dieudonné, Hermann Weyl and Norbert Wiener as the most important woman in the history of mathematics. As one of the leading mathematicians of her time, she developed some theories of rings, fields, and algebras. In physics, Noether's theorem explains the connection between symmetry and conservation laws.

In mathematics and specifically in algebraic geometry, the dimension of an algebraic variety may be defined in various equivalent ways.

In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring K[x1, …, xn] over a field K. A Gröbner basis allows many important properties of the ideal and the associated algebraic variety to be deduced easily, such as the dimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solving systems of polynomial equations and computing the images of algebraic varieties under projections or rational maps.

In mathematics, an algebraic equation or polynomial equation is an equation of the form

Seki Takakazu

Seki Takakazu, also known as Seki Kōwa, was a Japanese mathematician and author of the Edo period.

In computational algebraic geometry and computational commutative algebra, Buchberger's 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. It was invented by Austrian mathematician Bruno Buchberger. One can view it as a generalization of the Euclidean algorithm for univariate GCD computation and of Gaussian elimination for linear systems.

In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root, or, equivalently, a common factor. In some older texts, the resultant is also called the eliminant.

In mathematics, real algebraic geometry is the sub-branch of algebraic geometry studying real algebraic sets, i.e. real-number solutions to algebraic equations with real-number coefficients, and mappings between them.

Wenjun Wu's method is an algorithm for solving multivariate polynomial equations introduced in the late 1970s by the Chinese mathematician Wen-Tsun Wu. This method is based on the mathematical concept of characteristic set introduced in the late 1940s by J.F. Ritt. It is fully independent of the Gröbner basis method, introduced by Bruno Buchberger (1965), even if Gröbner bases may be used to compute characteristic sets.

A system of polynomial equations is a set of simultaneous equations f1 = 0, ..., fh = 0 where the fi are polynomials in several variables, say x1, ..., xn, over some field k.

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form

Daniel Lazard is a French mathematician and computer scientist. He is emeritus professor at Université Pierre et Marie Curie.

In algebraic geometry, the main theorem of elimination theory states that every projective scheme is proper. A version of this theorem predates the existence of scheme theory. It can be stated, proved, and applied in the following more classical setting. Let k be a field, denote by the n-dimensional projective space over k. The main theorem of elimination theory is the statement that for any n and any algebraic variety V defined over k, the projection map sends Zariski-closed subsets to Zariski-closed subsets.

Ferdinando 'Teo' Mora is an Italian mathematician, and since 1990 until 2019 a professor of algebra at the University of Genoa.

Deepak Kapur is a Distinguished Professor in the Department of Computer Science at the University of New Mexico.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.