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
      0 references
      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
      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

      Identifiers