×
Ben-Israel, A.

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

J. Math. Anal. Appl. 27, 367-389 (1969).
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)].
Reviewer: Adi Ben-Israel (Evanston)
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0174.31502

Cited in 65 Documents

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

Keywords:

linear equations; linear inequalities; consistent system; asymptotically consistent system

Citations:

Zbl 0136.13802
PDF BibTeX XML Cite
\textit{A. Ben-Israel}, J. Math. Anal. Appl. 27, 367--389 (1969; Zbl 0174.31502)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Beckenbach, E.F; Bellman, R, Inequalities, (1965), Springer-Verlag New York · Zbl 0128.27401
[2] 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
[3] Ben-Israel, A; Charnes, A, Contributions to the theory of generalized inverses, J. soc. indust. appl. math., 11, 667-699, (1963) · Zbl 0116.32202
[4] Ben-Israel, A; Charnes, A, On the intersections of cones and subspaces, Bull. amer. math. soc., 74, 541-544, (1968) · Zbl 0159.41501
[5] 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
[6] Braunschweiger, C.C; Clark, H.E, An extension of the farkas theorem, Amer. math. monthly, 69, 272-276, (1962) · Zbl 0116.08302
[7] Braunschweiger, C.C, An extension of the nonhomogeneous farkas theorem, Amer. math. monthly, 69, 969-975, (1962) · Zbl 0108.10702
[8] Č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:
[9] 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
[10] Charnes, A; Cooper, W.W, The strong Minkowski-farkas-Weyl theorem for vector spaces over ordered fields, (), 914-916 · Zbl 0202.03501
[11] Desoer, C.A; Whalen, B.H, A note on pseudoinverses, J. soc. indust. appl. math., 11, 442-447, (1963) · Zbl 0123.09603
[12] Deutsch, F.R; Maserick, P.H, Applications of the Hahn-Banach theorem in approximation theory, SIAM review, 9, 516-530, (1967) · Zbl 0166.10501
[13] Duffin, R.J; Peterson, E.L; Zener, C, Geometric programming—theory and application, (1967), Wiley New York · Zbl 0171.17601
[14] Fan, K, On systems of linear inequalities, (), 99-156, No. 38 · Zbl 0072.37602
[15] Fan, K, Convex sets and their applications, Argonne national laboratory lecture notes, (summer 1959), Argonne, Ill.
[16] Farkas, J, Uber die theorie der einfachen ungleichungen, J. reine angew. math., 124, 1-24, (1902) · JFM 32.0169.02
[17] Gale, D, Convex polyhedral cones and linear inequalities. chapt. 17, ()
[18] Gale, D, The theory of linear economic models, (1960), McGraw-Hill New York · Zbl 0114.12203
[19] Gerstenhaber, M, Theory of convex polyhedral cones, (), chapt. 18 · Zbl 0045.09708
[20] Goldman, A.J; Tucker, A.W, Polyhedral convex cones, (), 19-40, No. 38 · Zbl 0072.37504
[21] Goldstein, A.A, Constructive real analysis, (1967), Harper and Row New York · Zbl 0189.49703
[22] Good, R.A, Systems of linear relations, SIAM review, 1, 1-31, (1959) · Zbl 0231.15006
[23] Hanson, M.A; Mond, B, Quadratic programming in complex space, J. math. anal. appl., 20, 507-514, (1967) · Zbl 0157.50001
[24] Hoffman, A.J, Mathematical programming, () · Zbl 0407.05002
[25] Hoffman, A.J; McAndrew, M.S, Linear inequalities and analysis, () · Zbl 0178.35403
[26] Hurwicz, L, Programming in linear spaces, (), Chapt. 4 · Zbl 0133.12805
[27] ()
[28] Kuhn, H.W, Solvability and consistency for linear equations and inequalities, Amer. math. monthly, 63, 217-232, (1956) · Zbl 0070.25001
[29] ()
[30] Levinson, N, Linear programming in complex space, J. math. anal. appl., 14, 44-62, (1966) · Zbl 0136.13802
[31] Mirkil, H, New characterizations of polyhedral cones, Canad. J. math., 9, 1-4, (1957) · Zbl 0083.38302
[32] 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
[33] Nirenberg, L, Functional analysis, ()
[34] Pearl, M.H, A matrix proof of Farkas’s theorem, Quart. J. math. Oxford, 18, 193-197, (1967), (2) · Zbl 0259.15015
[35] Penrose, R, A generalized inverse for matrices, (), 406-413 · Zbl 0065.24603
[36] {\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
[37] Uzawa, H, A theorem on convex polyhedral cones, (), chapt. 2 · Zbl 0989.91539
[38] Weyl, H, The elementary theory of convex polyhedra, (), 3-18 · Zbl 0041.25401
[39] 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.