A linear system Ax = b, A ∈ ޒ m,n , b ∈ ޒ m is called sign-solvable if the signs of x are determined only by the signs of the entries of A and b.
It was the economist P. A. Samuelson who first recognized that it is worthwhile to consider such kind of problems or linear systems. His book, Foundations of Economic Analysis, first published in 1947, became a classic one on this topic. Since then a number of publications on sign-solvability appeared written from different point of views.
The question of whether or not a linear system is sign solvable leads to different classes of matrices, namely L-matrices, sign-nonsingular matrices (SNS-matrices), S * -matrices, and S-matrices. Recognizing a sign-solvable linear system is then equivalent to the problems of recognizing S-matrices, L-matrices, and so forth.
Sign solvability can be seen as part of a larger qualitative problem: when does an arrangement of the positive, negative and zero entries of a matrix imply a certain algebraic, analytic or geometric property of the matrix? Thus, it is not surprising that many characterizations of L-matrices and other relevant classes of matrices are combinatorically and graph theoretically. But this leads to a beautiful connection between these topics on one hand and matrix theory or linear algebra on the other.
Brualdi and Shader have done an excellent job in collecting and presenting a number of results obtained from different areas as well as giving new proofs and interesting new results.
This 298 page book is divided into eleven chapters. Chapter 1 begins with a signsolvability problem in economics, one of the only two applications mentioned in this book. Then basic properties of sign-solvable linear system are given which lead to the classes of L-matrices, SNS-matrices, strong SNS-matrices (S 2 NS-matrices) and S * -matrices. It is shown that the problem of recognizing sign-solvable linear systems is equivalent to the problem of recognizing these classes of matrices.
In Chapter 2, L-matrices are discussed. L-matrices can be characterized combinatorically with so-called signings, i.e. nonzero (0,1,-1)-diagonal matrices. However, for rectangular matrices the L-matrix recognition problem is NP-complete.
In Chapter 3 sign-solvability of a linear system of equations as well as certain classes of matrices are characterized by graph theoretically properties. At the end of this chapter a list of possible tests is given whether or not a system with a square matrix is sign solvable.