Quantifier elimination is a term used in mathematical logic to explain that, in some theories, every formula is equivalent to a formula without quantifier. In the worst case, it is presumably hard to eliminate variables computationally. There is also a logical facet to elimination theory, as seen in the Boolean satisfiability problem. The main methods for this renewal of elimination theory are Gröbner bases and cylindrical algebraic decomposition, introduced around 1970. 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.
Later, elimination theory was considered old-fashioned and removed from subsequent editions of Moderne Algebra.
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.Įlimination 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. 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". In general, these eliminants are also invariant under various changes of variables, and are also fundamental in invariant theory.Īll these concepts are effective, in the sense that their definitions include a method of computation. In the 19th century, this was extended to linear Diophantine equations and abelian group with Hermite normal form and Smith normal form.īefore the 20th century, different types of eliminants were introduced, including resultants, and various kinds of discriminants. 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. 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).Įxcept for Bézout's theorem, the general approach was to eliminate variables for reducing the problem to a single equation in one variable. The field of elimination theory was motivated by the need of methods for solving systems of polynomial equations. History and connection to modern theories 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. 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.Ĭlassical 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. Part of algebraic geometry devoted to the elimination of variables between polynomials
0 kommentar(er)
