Signsolvability revisited |
| |
Authors: | Victor Klee Richard Ladner Rachel Manber |
| |
Institution: | Department of Mathematics University of Washington Seattle, Washington 98195 U.S.A.;Department of Computer Science University of Washington Seattle, Washington 98195 U.S.A.;Department of Mathematics University of Wisconsin Madison, Wisconsin 53706 U.S.A. |
| |
Abstract: | For a real matrix A, Q(A) denotes the set of all matrices with the same sign pattern as A. A linear system Ax=b is signsolvable if solvability and Q(x) depend only on Q(A) and Q(b). The study of signsolvability can be decomposed into the study of L-matrices and of S-matrices, where A is an L-matrix S-matrix] if the nullspace of each member of Q(A) is {0} is a line intersecting the open positive orthant]. The problem of recognizing L-matrices is shown to be NP-complete, even in the almost square] case. Recognition of square L-matrices was transformed into a graph-theoretic problem by Bassett, Maybee, and Quirk in 1968. The complexity of this problem remains open, but that of some related graph-theoretic problems is determined. The relation between S-matrices and L-matrices is studied, and it is shown that a certain recursive construction yields all S-matrices, thus proving a 1964 conjecture of Gorman. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|