Matrices of sign-solvable linear systems.

*(English)*Zbl 0833.15002
Cambridge Tracts in Mathematics. 116. Cambridge: Cambridge Univ. Press. ix, 298 p. (1995).

The subject of sign-solvability of a linear system was begun in 1947 by the economist P. Samuelson and later developed from various perspectives in the linear algebra, combinatorics and economics literature. The present book organizes the subject and gives it a unified and self- contained presentation.

The sign-solvability of a linear system implies that the signs of the entries of the solution are determined solely on the basis of the signs of the coefficients of the system. Sign-solvability is part of a larger study which seeks to understand the special circumstances under which an algebraic, analytic or geometric property of a matrix can be determined from the combinatorial arrangement of the positive, negative, and zero elements of the matrix. Thus these are properties shared by all members of a qualitative class of matrices.

Several classes of matrices arise in this way, notably sign-nonsingular matrices, \(L\)-matrices, \(S\)-matrices, and sign-stable matrices. (The essential idea of a sign-nonsingular matrix arose in a different context in a 1963 paper by P. W. Kasteleyn.) The large and diffuse body of literature connected with sign-solvability is presented as a coherent whole for the first time in this book displaying it as a beautiful interplay between linear algebra, combinatorics (especially graph theory) and theoretical computer science (combinatorial algorithms).

The book should be of interest not only to researchers in combinatorics and linear algebra, but also to economists, theoretical computer scientists, physicists, chemists and engineers.

The sign-solvability of a linear system implies that the signs of the entries of the solution are determined solely on the basis of the signs of the coefficients of the system. Sign-solvability is part of a larger study which seeks to understand the special circumstances under which an algebraic, analytic or geometric property of a matrix can be determined from the combinatorial arrangement of the positive, negative, and zero elements of the matrix. Thus these are properties shared by all members of a qualitative class of matrices.

Several classes of matrices arise in this way, notably sign-nonsingular matrices, \(L\)-matrices, \(S\)-matrices, and sign-stable matrices. (The essential idea of a sign-nonsingular matrix arose in a different context in a 1963 paper by P. W. Kasteleyn.) The large and diffuse body of literature connected with sign-solvability is presented as a coherent whole for the first time in this book displaying it as a beautiful interplay between linear algebra, combinatorics (especially graph theory) and theoretical computer science (combinatorial algorithms).

The book should be of interest not only to researchers in combinatorics and linear algebra, but also to economists, theoretical computer scientists, physicists, chemists and engineers.

Reviewer: G.Bonanno (Davis)

##### MSC:

15A06 | Linear equations (linear algebraic aspects) |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

15-02 | Research exposition (monographs, survey articles) pertaining to linear algebra |

68R05 | Combinatorics in computer science |