Elimination theory

2020 Mathematics Subject Classification: Primary: 12-XX [MSN][ZBL]

The theory of eliminating unknowns from systems of algebraic equations. More precisely, suppose one is given a system of equations

$$f_i(x_1,\dots,x_n) = 0,\quad i=1,\dots,m,\label{1}$$ where $f_i$ are polynomials with coefficients in a given field $P$. The problem of eliminating $x_1,\dots,x_k$ from (1) (the inhomogeneous problem in elimination theory) can be formulated as follows: Find the projection of the set of solutions of (1) on the coordinate space of $x_{k+1},\dots,x_n$. If all equations are homogeneous with respect to the set of variables $x_1,\dots,x_k$, one also consider the homogeneous problem in elimination theory (the inhomogeneous problem is trivial in this case): Find the projection on the coordinate space of $x_{k+1},\dots,x_n$ of the set of those solutions of (1) in which not all unknowns $x_1,\dots,x_k$ are zero.

The inhomogeneous problem can also be regarded as the problem of finding conditions on the coefficients of the system of algebraic equations ensuring that this system is compatible; the homogeneous problem is then that of finding conditions on the coefficients of a system of homogeneous algebraic equations ensuring that this system has a non-zero solution.

The fundamental result of elimination theory is that if $P$ is an algebraically closed field, then the solution of the homogeneous problem is an algebraic set, i.e. the set of solutions of a system of algebraic equations, while the solution of the inhomogeneous problem is a constructible subset in the sense of algebraic geometry, i.e. a finite union of sets of the form $M\setminus N$, where $M$ and $N$ are algebraic sets. An explicit solution to problems in elimination theory is known in some of the simplest cases.

1) Consider a system of equations that are linear and homogeneous in $x_1,\dots,x_k$, i.e. of the form

$$\sum_{j=1}^k a_{ij}x_j = 0,\quad i=1,\dots,m,\label{2}$$ where $a_{ij}$ are polynomials in $x_{k+1},\dots,x_n$. For given values of $x_{k+1},\dots,x_n$ the system (2) has a non-zero solution if and only if the rank of the matrix $A=(a_{ij})$ is less than $k$ (cf. Linear equation). The solution of the homogeneous problem now is the set in the coordinate space of $x_{k+1},\dots,x_n$ described by the vanishing of all minors of rank $k$ of $A$.

2) Consider a system of equations that are linear in $x_1,\dots,x_k$, i.e. of the form

$$\sum_{j=1}^k a_{ij}x_j = b_i,\quad i=1,\dots,m,\label{3}$$ where $a_{ij}$, $b_i$ are polynomials in $x_{k+1},\dots,x_n$. Let $\def\tA{ {\tilde A}}\tA$ be the matrix obtained from $A=(a_{ij})$ by addition of the column $(b_i)$. For given values of $x_{k+1},\dots,x_n$ the system (3) is compatible if and only if the rank of $\tA$ equals the rank of $A$. Hence, the result of eliminating $x_1,\dots,x_k$ from (3) is

$$\bigcap_{r=0}^k M_r\setminus N_r,$$ where $M_r$ is the set of points $(x_{k+1},\dots,x_n)$ at which the rank of $\tA$ is at most $r$, while $N_r$ is the set of points at which the rank of $A$ is less than $r$ (both $M_r$ and $N_r$ are algebraic sets).

3) Let $k=2$, let $P$ be an algebraically closed field and consider a system of two equations that are homogeneous in $x_1$, $x_2$:

$$\begin{align}&a_0x_1^n+a_1x_1^{n-1}x_2+\cdots+a_nx_2^n = 0,\\ &b_0x_1^m+b_1x_1^{m-1}x_2+\cdots+b_mx_2^m = 0,\end{align}\label{4}$$ where $a_0,\dots,a_n, \ b_0,\dots,b_m$ are polynomials in $x_3,\dots,x_n$. For given values of $x_3,\dots,x_n$ the system (4) has a non-zero solution if and only if the resultant $R$ vanishes. Here $R$ is given by

$$R(a_0,\dots,a_n; b_0,\dots,b_m) = \det\begin{pmatrix} a_0 &\cdots&a_{n-1}& a_n & & \\ \cdots&\cdots&\cdots &\cdots& & \\ & & a_0 &\cdots&a_{n-1}&a_n\\ b_0 &\cdots&b_{m-1}& a_m & & \\ \cdots&\cdots&\cdots &\cdots& & \\ & & b_0 &\cdots&b_{m-1}&b_m\\ \end{pmatrix} $$

($m$ rows of $a_0,\dots,a_n$; $n$ rows of $ b_0,\dots,b_m$). This also gives a solution of the homogeneous problem in the case considered.

4) Let $k=1$, let $P$ be an algebraically closed field and consider the system of two equations

$$\begin{align}a_0x_1^n+a_1x_1^{n-1}+\cdots+a_n = 0, b_0x_1^m+b_1x_1^{m-1}+\cdots+b_m = 0,\end{align},\label{5}$$ where $a_0,\dots,a_n, \ b_0,\dots,b_m$ are polynomials in $x_2,\dots,x_n$. For given values of $x_2,\dots,x_n$ at which either $a_0$ or $b_0$ does not vanish, (5) is a compatible system if and only if

$$R(a_0,\dots,a_n;\ b_0,\dots,b_m)=0.$$ If $a_0=b_0=0$, one must consider

$$R(a_1,\dots,a_n;\ b_1,\dots,b_m).$$ etc. This makes it possible to describe explicitly the result of eliminating $x_1$ from (5).

The elimination of unknowns from arbitrary systems of algebraic equations can be done successively (i.e. first one eliminates one unknown, then the second, etc.) using the "elementary transformations" described below. Since after eliminating a single unknown one obtains a constructible set instead of an algebraic set, the problem of projecting an arbitrary constructible set in $P^n$ on the coordinate space of $x_2,\dots,x_n$ must be considered.

Every constructible set $X\subset P^n$ can be represented as the union of sets of solutions of a collection of systems of algebraic equations and inequalities. (An algebraic inequality is of the form $f(x_1,\dots,x_n)\ne 0$, where $f$ is a polynomial.) An elementary transformation of such a collection is a transformation of one of the following kinds: in one of the systems one adds to one of the equations another equation, multiplied by a polynomial; in a system containing an inequality $f\ne 0$, one of the equations is multiplied by $f$; in one of the systems, one adds to one of the inequalities an equation, multiplied by a polynomial; one of the systems is divided into two systems, determined by adding the equation $f=0$, respectively the inequality $f\ne 0$, to it ($f$ is an arbitrary polynomial); or, in one of the systems, two inequalities are replaced by their product.

The elementary transformations do not change the union of the sets of solutions of the systems in the original collection. By applying elementary transformations, any collection of algebraic equations and inequalities in unknowns $x_1,\dots,x_n$ can be reduced to a form in which each of the systems contains at most one equation or inequality containing $x_1$, and, moreover, together with this equation, $f=0$, or inequality, $f\ne 0$, the inequality $f_0\ne 0$ is contained in it, where $f_0$, a polynomial in $x_2,\dots,x_n$, is the leading coefficient of the expansion of $f$ in powers of $x_1$. If $P$ is an algebraically closed field, then by disregarding in the systems the equations and inequalities in $x_1$ thus obtained, one obtains a collection of systems of algebraic and inequalities in $x_2,\dots,x_n$. This gives the projection of the set $X$ on the coordinate space of $x_2,\dots,x_n$.

Sequential elimination of unknowns by elementary transformations allows one to reduce, in principle, the solution of any system of algebraic equations in $n$ unknowns to the solution of a number of algebraic equations in one unknown.

For a non-constructive approach to elimination theory see [Mu], § 2C.

References

[HoPe]	W.V.D. Hodge, D. Pedoe, "Methods of algebraic geometry", 1, Cambridge Univ. Press (1947) MR0028055 Zbl 0796.14002 Zbl 0796.14003 Zbl 0796.14001 Zbl 0157.27502 Zbl 0157.27501 Zbl 0055.38705 Zbl 0048.14502
[Mu]	D. Mumford, "Algebraic geometry", 1. Complex projective varieties, Springer (1976) MR0453732 Zbl 0356.14002
[Wa]	B.L. van der Waerden, "Algebra", 1–2, Springer (1967–1971) (Translated from German) MR1541390 Zbl 1032.00002 Zbl 1032.00001 Zbl 0903.01009 Zbl 0781.12003 Zbl 0781.12002 Zbl 0724.12002 Zbl 0724.12001 Zbl 0569.01001 Zbl 0534.01001 Zbl 0997.00502 Zbl 0997.00501 Zbl 0316.22001 Zbl 0297.01014 Zbl 0221.12001 Zbl 0192.33002 Zbl 0137.25403 Zbl 0136.24505 Zbl 0087.25903 Zbl 0192.33001 Zbl 0067.00502