Geodesic
Sign-consistency and solvability of constrained linear systems
The electronic journal of linear algebra, Tome 4 (1998), pp. 1-18.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Sign-solvable linear systems were introduced in modelling economic and physical systems where only qualitative information is known. Often economic and physical constraints require the entries of a solution to be nonnegative. Yet, to date the assumption of nonnegativity has been omitted in the study of sign-solvable linear systems. In this paper, the notions of signconsistency and sign-solvability of a constrained linear system Ax = b; x * 0 0, are introduced. These notions give rise to new classes of sign patterns. The structure and the complexity of the recognition problem for each of these classes are studied. A qualitative analog of Farkas' Lemma is proven, and it is used to establish necessary and sufficient conditions for the constrained linear system Ax = b; x * 0 0 to be sign-consistent. Also, necessary and sufficient conditions for the constrained linear system Ax = b; x * 0 0 to be sign-solvable are determined, and these are used to establish a polynomialtime recognition algorithm. It is worth noting that the recognition problem for (unconstrained) sign-solvable linear systems is known to be NP-complete.
Classification : 15A06, 90C08
Keywords: linear systems, qualitative matrix theory, sign-solvable 
@article{ELA_1998__4__a4,
     author = {Lee, Gwang-Yeon and Shader, Bryan L.},
     title = {Sign-consistency and solvability of constrained linear systems},
     journal = {The electronic journal of linear algebra},
     pages = {1--18},
     publisher = {mathdoc},
     volume = {4},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_1998__4__a4/}
}
TY  - JOUR
AU  - Lee, Gwang-Yeon
AU  - Shader, Bryan L.
TI  - Sign-consistency and solvability of constrained linear systems
JO  - The electronic journal of linear algebra
PY  - 1998
SP  - 1
EP  - 18
VL  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_1998__4__a4/
LA  - en
ID  - ELA_1998__4__a4
ER  - 
%0 Journal Article
%A Lee, Gwang-Yeon
%A Shader, Bryan L.
%T Sign-consistency and solvability of constrained linear systems
%J The electronic journal of linear algebra
%D 1998
%P 1-18
%V 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_1998__4__a4/
%G en
%F ELA_1998__4__a4
Lee, Gwang-Yeon; Shader, Bryan L. Sign-consistency and solvability of constrained linear systems. The electronic journal of linear algebra, Tome 4 (1998), pp. 1-18. http://geodesic.mathdoc.fr/item/ELA_1998__4__a4/