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.