Sign-consistency and solvability of constrained linear systems
The main topic of the paper is the study of the behaviour of nonnegative solutions of a linear system when only the signs of the entries of the system are known. A constrained linear system is by definition a linear system \(Ax=b\) \((A\in \mathbb{R}^{m\times n}, b\in \mathbb{R}^m)\), together with the entrywise inequality \(x>0\). A constrained linear system is consistent if it has a nonzero nonnegative solution. The sign pattern of the matrix \(A=(a_{ij})\) is the matrix (sign \(a_{ij})\). A sign pattern \(B\) determines a qualitative class \(Q(B)\) consisting of all matrices with sign pattern \(B\). The notions of sign-consistency and sign-solvability of a constrained linear system are introduced. For instance, a constrained linear system \(Ax=b\), \(x>0\), is sign-consistent if the constrained systems \(\widetilde Ax=\widetilde b\), \(x>0\), is consistent for all \(\widetilde A\in Q(A)\) and \(\widetilde b\in Q (b)\). Four new classes of sign patterns are defined, which extend to the constrained framework of certain known classes used in the study of (unconstrained) sign-consistent and sign-solvable linear systems. By employing a qualitative version of Farkas' lemma, necessary and sufficient conditions for sign-consistency of constrained linear systems are given. In the last section of the paper necessary and sufficient conditions for a constrained linear system to be sign-solvable are obtained and a polynomial-time algorithm for recognizing such linear systems is presented.
- On sign inconsistent linear systems
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- A characterization of the nearly sign central matrices and its minimallity
- Linear systems with signed solutions
- On the digraphs of sign solvable linear systems
- Graphical criteria for positive solutions to linear systems
- Set-systems with signed solutions
- A NOTE ON PARTIAL SIGN-SOLVABILITY
- Computing maximal autarkies with few and simple oracle queries
- Sign consistent linear programming problems
- QUALITATIVE PROPERTIES OF SYSTEMS OF LINEAR CONSTRAINTS
- Sign-Solvable Cone-Systems
- Decomposition Theorems for Conditional Sign-Solvability and Sign-Solvability of General Systems
- Sign properties of Metzler matrices with applications
- Strict sign-central matrices
- scientific article; zbMATH DE number 2219152 (Why is no real title available?)
- Solving linear programs from sign patterns
This page was built for publication: Sign-consistency and solvability of constrained linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4211923)
