Sign-consistency and solvability of constrained linear systems (Q4211923)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1209073
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Sign-consistency and solvability of constrained linear systems |
scientific article; zbMATH DE number 1209073 |
Statements
Sign-consistency and solvability of constrained linear systems (English)
0 references
8 October 1998
0 references
sign-consistency
0 references
nonnegative solutions
0 references
constrained linear system
0 references
sign-solvability
0 references
sign patterns
0 references
Farkas' lemma
0 references
polynomial-time algorithm
0 references
0.8404252529144287
0 references
0.8292063474655151
0 references
0.8260630369186401
0 references
0.8206392526626587
0 references
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.
0 references