## Linear equations and inequalities on finite dimensional, real or complex, vector spaces: a unified theory.(English)Zbl 0174.31502

This paper presents a unified theory of linear equations and inequalities, real or complex, on finite-dimensional vector spaces. Notations: Let $$S\subset \mathbb C^n$$ be a closed convex cone, $S^*= \{y\in\mathbb C^n : x\in S\Rightarrow \text{Re}(y^Hx)\ge 0\},\ A\in \mathbb C^{m\times m}, b\in \mathbb C^m.$ The system $$(*)$$ $$Ax = b$$, $$x\in S$$ is “consistent” [ “asymptotically consistent” ] if $$\exists\, x \in S \ni Ax = b$$ [ $$\exists\, \{x_k\}\subset S \ni \lim Ax_k = b$$ ]. Sample results:
Theorem: The following are equivalent (where $$A^T, A^H, A^+$$ denote the transpose, the conjugate transpose, the generalized inverse of $$A$$)::
(a) $$(*)$$ is asymptotically consistent,
(b) $$A^H y\in S^* \Rightarrow \text{Re}(b^H y)\ge 0$$,
(c) $$b\in R(A)$$ and $$A^+ b\in \text{cl}(N(A) + S)$$.
Corollary: Let $$N(A)+S$$ be closed. Then $$(*)$$ is consistent if, and only if, $$A^H y\in S^* \Rightarrow \text{Re}(b^H y) = 0$$.
Corollary (Solvability of linear equations): $$Ax = b$$ is consistent if, and only if, $$A^H y = 0 \Rightarrow b^H y = 0$$.
Corollary (Farkas): Let $$A\in \mathbb R^{n\times n}$$, $$b\in\mathbb R^n$$. Then $$Ax =b$$, $$x \ge 0$$ is consistent if, and only if, $$A^T y\ge 0 \Rightarrow b^T y\ge 0$$.
These results are used to prove a duality theorem for complex linear programming, following and slightly extending N. Levinson [J. Math Anal. Appl. 14, 44–62 (1966; Zbl 0136.13802)].
Show Scanned Page ### MSC:

 15A06 Linear equations (linear algebraic aspects) 15A03 Vector spaces, linear dependence, rank, lineability 90C46 Optimality conditions and duality in mathematical programming 90C05 Linear programming

Zbl 0136.13802
Full Text:

### References:

  Beckenbach, E.F; Bellman, R, Inequalities, (1965), Springer-Verlag New York · Zbl 0128.27401  Ben-Israel, A, Notes on linear inequalities, I: the intersection of the nonnegative orthant with complementary orthogonal subspaces, J. math. anal. appl., 10, 303-314, (1964) · Zbl 0141.17401  Ben-Israel, A; Charnes, A, Contributions to the theory of generalized inverses, J. soc. indust. appl. math., 11, 667-699, (1963) · Zbl 0116.32202  Ben-Israel, A; Charnes, A, On the intersections of cones and subspaces, Bull. amer. math. soc., 74, 541-544, (1968) · Zbl 0159.41501  Ben-Israel, A; Charnes, A; Kortanek, K.O, Duality and asymptotic solvability over cones, Bull. amer. math. soc., 75, 318-324, (1969) · Zbl 0187.17504  Braunschweiger, C.C; Clark, H.E, An extension of the farkas theorem, Amer. math. monthly, 69, 272-276, (1962) · Zbl 0116.08302  Braunschweiger, C.C, An extension of the nonhomogeneous farkas theorem, Amer. math. monthly, 69, 969-975, (1962) · Zbl 0108.10702  Černikov, S.N; Černikov, S.N, Systems of linear inequalities, Uspehi mat. nauk, Amer. math. soc. transl. ser. 2, 26, 11-86, (1963), English translation:  C̆ernikov, S.N; C̆ernikov, S.N, Algebraic theory of linear inequalities, Doklady akad. nauk SSSR, Soviet math. doklady, 7, 1019-1023, (1966), English translation: · Zbl 0196.30001  Charnes, A; Cooper, W.W, The strong Minkowski-farkas-Weyl theorem for vector spaces over ordered fields, (), 914-916 · Zbl 0202.03501  Desoer, C.A; Whalen, B.H, A note on pseudoinverses, J. soc. indust. appl. math., 11, 442-447, (1963) · Zbl 0123.09603  Deutsch, F.R; Maserick, P.H, Applications of the Hahn-Banach theorem in approximation theory, SIAM review, 9, 516-530, (1967) · Zbl 0166.10501  Duffin, R.J; Peterson, E.L; Zener, C, Geometric programming—theory and application, (1967), Wiley New York · Zbl 0171.17601  Fan, K, On systems of linear inequalities, (), 99-156, No. 38 · Zbl 0072.37602  Fan, K, Convex sets and their applications, Argonne national laboratory lecture notes, (summer 1959), Argonne, Ill.  Farkas, J, Uber die theorie der einfachen ungleichungen, J. reine angew. math., 124, 1-24, (1902) · JFM 32.0169.02  Gale, D, Convex polyhedral cones and linear inequalities. chapt. 17, ()  Gale, D, The theory of linear economic models, (1960), McGraw-Hill New York · Zbl 0114.12203  Gerstenhaber, M, Theory of convex polyhedral cones, (), chapt. 18 · Zbl 0045.09708  Goldman, A.J; Tucker, A.W, Polyhedral convex cones, (), 19-40, No. 38 · Zbl 0072.37504  Goldstein, A.A, Constructive real analysis, (1967), Harper and Row New York · Zbl 0189.49703  Good, R.A, Systems of linear relations, SIAM review, 1, 1-31, (1959) · Zbl 0231.15006  Hanson, M.A; Mond, B, Quadratic programming in complex space, J. math. anal. appl., 20, 507-514, (1967) · Zbl 0157.50001  Hoffman, A.J, Mathematical programming, () · Zbl 0407.05002  Hoffman, A.J; McAndrew, M.S, Linear inequalities and analysis, () · Zbl 0178.35403  Hurwicz, L, Programming in linear spaces, (), Chapt. 4 · Zbl 0133.12805  ()  Kuhn, H.W, Solvability and consistency for linear equations and inequalities, Amer. math. monthly, 63, 217-232, (1956) · Zbl 0070.25001  ()  Levinson, N, Linear programming in complex space, J. math. anal. appl., 14, 44-62, (1966) · Zbl 0136.13802  Mirkil, H, New characterizations of polyhedral cones, Canad. J. math., 9, 1-4, (1957) · Zbl 0083.38302  Motzkin, T.S; Motzkin, T.S; Motzkin, T.S, Beiträge zur theorie der linearen ungleichungen, Inaugural dissertation, Inaugural dissertation, U. S. air force, project rand, report T-22, (1952), English translation: · JFM 62.0054.01  Nirenberg, L, Functional analysis, ()  Pearl, M.H, A matrix proof of Farkas’s theorem, Quart. J. math. Oxford, 18, 193-197, (1967), (2) · Zbl 0259.15015  Penrose, R, A generalized inverse for matrices, (), 406-413 · Zbl 0065.24603  {\scA. W. Tucker}. Dual systems of homogeneous linear relations. In Ann. Math. Studies (H. W. Kuhn and A. W. Tucker, eds.), No. 38, pp. 3-18. Princeton Univ. Press, Princeton, New Jersey. · Zbl 0072.37503  Uzawa, H, A theorem on convex polyhedral cones, (), chapt. 2 · Zbl 0989.91539  Weyl, H, The elementary theory of convex polyhedra, (), 3-18 · Zbl 0041.25401  Klee, V, Some characterizations of convex polyhedra, Acta Mathematica, 102, 79-107, (1959) · Zbl 0094.16802
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.