Linear inequality

An inequality of the form

$$ \tag{1 } l ( x) - a \equiv a _ {1} x _ {1} + \dots + a _ {n} x _ {n} - a \leq 0 $$

or of the form

$$ \tag{2 } l ( x) - a \equiv a _ {1} x _ {1} + \dots + a _ {n} x _ {n} - a < 0 , $$

where $ a _ {1} \dots a _ {n} , a $ are arbitrary real numbers and $ x = ( x _ {1} \dots x _ {n} ) $.

In a wider sense, a linear inequality is an inequality of the form

$$ \tag{3 } f ( x) - a \leq 0 $$

or of the form

$$ \tag{4 } f ( x) - a < 0 , $$

where $ f ( x) $ is a linear (that is, additive and homogeneous) function on a real vector space $ L ( \mathbf R ) $ with values from the field $ \mathbf R $ of real numbers and $ a \in \mathbf R $. A further generalization of the concept of a linear inequality is obtained if instead of $ \mathbf R $ one takes an arbitrary ordered field $ P $. The modern theory of linear inequalities has been constructed on the basis of this generalization (see [1]).

A number of important questions in analytical mechanics, the geometry of numbers and the approximation of functions reduce to the investigation of systems of linear inequalities. Results concerned with systems of linear inequalities have found very important applications to studies in economics. In such applications, in particular, linear programming did arise. Many practical problems in economic technology and economic planning reduce to the solution of specific systems of linear inequalities; this has significantly determined the modern trend of research in the area of linear inequalities.

In this way there arises, in particular, the main principle of the theory of linear inequalities, the principle of boundary solutions, which was first established (see [4]) for finite systems of linear inequalities in modulus form, that is, for systems of the form

$$ \tag{5 } | l _ {j} ( x) - a _ {j} | \equiv \ | a _ {j1} x _ {1} + \dots + a _ {jn} x _ {n} - a _ {j} | \leq d _ {j} , $$

$ j = 1 \dots m $, where all the $ a _ {j1} \dots a _ {jn} , a _ {j} $ are, in the most general case, elements of the field of complex numbers and all the $ d _ {j} $ are non-negative real numbers, $ j = 1 \dots m $.

The principle of boundary solutions consists of the following. In any compatible system of the form (5) of rank $ r > 0 $ one can select a subsystem of rank $ r $ consisting of $ r $ inequalities such that at least one solution of the latter, which makes all its inequalities into equalities, satisfies all the inequalities of the system (5), in other words, it is a solution of (5).

The principle of boundary solutions has been extended (see [5]) to systems of the form

$$ \tag{6 } l _ {j} ( x) - a \equiv a _ {j1} x _ {1} + \dots + a _ {jn} x _ {n} - a _ {j} \leq 0 , $$

$ j = 1 \dots m $, over the field $ \mathbf R $( that is, to systems with real $ a _ {j1} \dots a _ {jn} , a _ {j} $, $ j = 1 \dots m $) in the form of the following stronger assertion. In a complete system (6) of rank $ r > 0 $ one can select a subsystem of rank $ r $ consisting of $ r $ inequalities such that any solution of the subsystem that makes all its inequalities into equalities satisfies all the inequalities (6) (for a system of the form (6) this assertion turns out to be equivalent to the previous one). The rank of a system of linear inequalities is the largest number of linearly independent forms $ l _ {j} ( x) $ that occur in its inequalities.

The principle of boundary solutions has also been extended to systems of the form (6) over an arbitrary ordered field $ P $ and even to more general systems consisting of finitely many linear inequalities of the form (3) over $ P $( see [6]). This principle implies the following compatibility condition for systems of the form (6) over an arbitrary ordered field. A system (6) of rank $ r > 0 $ is compatible if and only if in its coefficient matrix there is a non-zero minor $ \Delta $ of order $ r $ such that for the determinants $ \Delta _ {j} $, $ j = 1 \dots m $, obtained by bordering it by means of the $ j $- th row of this matrix and the column of elements $ a _ {j} $, all the ratios $ \Delta _ {j} / \Delta $ are non-negative. In the case of a compatible system of linear equations (cf. Linear equation) $ a _ {j1} x _ {1} + \dots + a _ {jn} x _ {n} - a _ {j} = 0 $, $ j = 1 \dots m $, these ratios are zero for any non-zero $ r $- th order minor $ \Delta $ of its coefficient matrix.

The development of the theory of linear inequalities was begun at the end of the 19th century. One of the first propositions of a general character, established in [3], [9], was the Minkowski–Farkas theorem, which is now one of the key theorems in the theory of linear inequalities: If all solutions of a compatible system (6) over $ \mathbf R $ satisfy an inequality

$$ l ( x) - b = b _ {1} x _ {1} + \dots + b _ {n} x _ {n} - b \leq 0 , $$

$ b , b _ {i} \in \mathbf R $, $ i = 1 \dots n $, then there are non-negative numbers $ p _ {0} \dots p _ {m} $ such that the identity

$$ l ( x) - b = \sum _ { j= } 1 ^ { m } p _ {j} ( l _ {j} ( x) - a _ {j} ) - p _ {0} $$

holds for $ x = ( x _ {1} \dots x _ {n} ) $.

At the beginning of the 20th century, in the research of G.F. Voronoi devoted to quadratic forms in integer variables, there arose one of the main problems in the theory of linear inequalities, the problem of studying the properties of a convex polyhedron defined in the space $ \mathbf R ^ {n} $ by the solutions of a compatible finite system of linear inequalities of non-zero rank. The main theorem of Voronoi (see [1]) expresses conditions such that the polyhedron is non-degenerate, in other words, conditions for the compatibility of a finite system consisting of inequalities of the form (2). For a long time the problem of studying the polyhedron of solutions of systems of the form (6) and the results of H. Minkowski [3] and J. Farkas [9] determined the main trend of research on linear inequalities (see [10]).

Later it became clear how the results of the theory of linear inequalities concerned with finite systems of inequalities of the form (6), particularly the results of Minkowski, Farkas and Voronoi mentioned above, can be derived from the principle of boundary solutions by discrete methods, that is, without using topological properties of the field $ \mathbf R $ of real numbers (or any consequence of these properties), and the principle of boundary solutions itself was proved by discrete methods (see [1] and [6]). Therefore, it turned out to be possible to replace the ground field $ \mathbf R $ in the construction of the theory of finite systems of linear inequalities by an arbitrary ordered field $ P $. Thus the way was prepared for the construction of a purely algebraic theory of linear inequalities, using only discrete methods.

For a long time the theory of linear inequalities did not comprise efficient methods for finding solutions of finite systems of linear inequalities. The method consisting in the direct use of the principle of boundary solutions was not very efficient. Efficient methods for finding individual solutions of a finite system of linear inequalities (in particular, the simplex method) emerged with the rise of linear programming.

In 1960–1965 the so-called method of convolution of systems of linear inequalities was developed, which made it possible to find, from any finite system consisting, in general, of inequalities of the form (3) and (4), particularly of inequalities of the form (1) and (2), and from a given subspace of the space associated with it, a new finite system of linear inequalities whose solution set coincides with some projection of the solution set of the system in question on the chosen subspace (see [1]). The fundamental convolution algorithm developed on this basis (a special algorithm for the successive elimination of unknowns in the system (6)) makes it possible to obtain general formulas that determine the whole set of solutions of a compatible system of the form (6). The method of convolution can be used in problems of linear programming for reducing the number of unknowns, and also for obtaining general formulas that determine the whole set of optimal solutions (see [1]). It also has been shown [7] that by means of the method of convolution it is possible to distinguish maximal compatible subsystems of an incompatible finite system of linear inequalities, which consists in general of inequalities of the form (3) and (4), particularly of inequalities of the form (1) and (2). This makes it possible to use it in one of the approaches to the solution of problems on pattern recognition (see [8]).

Among infinite systems of linear inequalities a particular class has been distinguished and studied, namely the polyhedrally-closed systems (see [1]). In the case of the real vector space $ \mathbf R ^ {n} $, polyhedrally-closed systems are defined as infinite systems of the form $ a _ {\alpha 1 } x _ {1} + \dots + a _ {\alpha n } x _ {n} - a _ \alpha \leq 0 $, $ \alpha \in M $, with a topologically closed conjugate cone in $ \mathbf R ^ {n+} 1 $, that is, the cone generated by elements

$$ ( a _ {\alpha 1 } \dots a _ {\alpha n } , - a _ \alpha ) ,\ \alpha \in M ,\ \textrm{ and } \ \ ( \theta , - 1 ) , $$

where $ \theta $ is the zero element of $ \mathbf R ^ {n} $. For infinite polyhedrally-closed systems of linear inequalities a number of properties of finite systems of linear inequalities is preserved; in particular, the Minkowski–Farkas theorem holds for such systems. Polyhedrally-closed systems of linear inequalities are used in the theory of approximation of functions, in convex programming and in control theory (see [8]).

References

[1]	S.N. Chernikov, "Lineare Ungleichungen" , Deutsch. Verlag Wissenschaft. (1971) (Translated from Russian) Zbl 0169.04103 Zbl 0163.27701 Zbl 0192.13201 Zbl 0080.01301 Zbl 0050.01203
[2]	H.W. Kuhn (ed.) A.W. Tucker (ed.) , Linear inequalities and related systems , Princeton Univ. Press (1956) Zbl 0072.37502
[3]	H. Minkowski, "Geometrie der Zahlen" , Chelsea, reprint (1953) MR0249269 Zbl 0050.04807
[4]	S.N. Chernikov, "A generalization of the Kronecker–Capelli theorem on systems of linear equations" Mat. Sb. , 15 : 3 (1944) pp. 437–448 (In Russian)
[5]	S.N. Chernikov, "Systems of linear inequalities" Uspekhi Mat. Nauk , 8 : 2 (1953) pp. 7–73 (In Russian) Zbl 0128.01808
[6]	S.N. Chernikov, "Algebraic theory of linear inequalities" Ukrain Math. J. , 19 : 1 (1967) pp. 29–67 Ukrain. Mat. Zh. , 19 : 1 (1967) pp. 36–80 Zbl 0163.27702
[7]	S.N. Chernikov, "The convolution of finite systems of linear inequalities" Dopovidi Akad. Nauk URSR Ser. A , 1 (1969) pp. 32–35 (In Russian) Zbl 0149.36802
[8]	N.N. Krasovskii, I.I. Eremin, "Linear inequalities and some of their applications" Ukrain Math. J. , 25 : 4 (1973) pp. 384–395 Ukrain. Mat. Zh. , 25 : 4 (1973) pp. 465–478 MR0338026
[9]	J. Farkas, "Ueber die Theorie der einfachen Ungleichungen" J. Reine Angew. Math. , 124 (1901) pp. 1–24
[10]	L.L. Dines, N.H. McCoy, "On linear inequalities" Trans. Roy Soc. Canada Sect. 3 , 27 (1933) pp. 37–70 Zbl 0008.30401 Zbl 59.0956.01

Comments

For applications of linear inequalities in convex and combinatorial geometry see [a1], [a2]; for applications in the geometry of numbers see also [a3]; for applications in optimization see [a4]. See also Linear programming.

References

[a1]	B. Grünbaum, "Convex polytopes" , Interscience (1967) MR0226496 Zbl 0163.16603 Zbl 0152.20602
[a2]	G.C. Stephard, "Convex polytopes and the upper bound conjecture" , Cambridge Univ. Press (1971)
[a3]	P.M. Gruber, C.G. Lekkerkerker, "Geometry of numbers" , North-Holland (1987) pp. Sect. (iv) (Updated reprint) MR0893813 Zbl 0611.10017
[a4]	M. Grötschel, L. Lovasz, A. Schrijver, "Geometric algorithms and combinatorial optimization" , Springer (1988) MR0936633 Zbl 0634.05001