ELA, Volume 4, pp. 1-18, August 1998, abstract.

Sign-consistency and Solvability of Constrained Linear Systems

Gwang-Yeon Lee and Bryan L. Shader


Sign-solvable linear systems were introduced in modeling 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 sign-consistency and sign-solvability of a constrained  
linear system Ax=b, x nonnegative and nonzero, are introduced.
These notions give rise to  new classes of sign patterns.  
The structure and 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 nonnegative and nonzero, to
be sign-consistent.  Also, necessary and sufficient conditions for the 
constrained linear system Ax=b, x nonnegative and nonzero, to be 
sign-solvable are determined, and these are used to establish a 
polynomial-time recognition algorithm.  It is worth noting that the 
recognition problem for (unconstrained) sign-solvable linear systems is 
known to be NP-complete.