Matrices of Sign-Solvable Linear Systems

In a sign-solvable linear system, the signs of at least some of the entries of the solution are determined solely on the basis of the signs of the coefficients. This is part of a larger study which seeks to understand whether properties of a matrix can be determined from combinatorial arrangements of its elements. This book presents the diffuse body of literature on sign-solvability as a coherent whole for the first time, giving many new results and proofs and establishing numerous new connections. Algorithms implicit in many of the proofs are explicitly described, and their complexity commented on. The book is self-contained, assuming familiarity only with elementary linear algebra and graph theory. Intended primarily for researchers in combinatorics and linear algebra, it will also be of interest to computer scientists, economists, physicists, chemists and engineers.