by Richard A. Brualdi and Bryan L. Shader

Publisher is Cambridge University Press.

Series is Cambridge Tracts

The possibility of writing this book occurred to us in the late fall of 1991 when we were both participating in the program on Applied Linear Algebra at the Institute for Mathematics and its Applications (IMA) in Minnesota. A few years earlier we had been attracted to the subject of sign-solvability because of the beautiful interplay it afforded between linear algebra, combinatorics, and theoretical computer science (combinatorial algorithms). The subject, begun in 1947 by the economist P. Samuelson, was developed from various perspectives in the linear algebra, combinatorics and economics literature . We thought that it would be a worthwhile project to organize the subject and to give a unified and self-contained presentation. Because there were no previous books or even survey papers on the subject, the tasks of deciding what was fundamental and how the material should be ordered for exposition had to be thought out very carefully. Our organization of the material has resulted in new connections between various results in the literature. In addition, many new results and many new and simpler proofs of previously established results are given throughout the book. We began the book in earnest in early 1992 and completed approximately three quarters of it while in residence at the IMA. Returning to our home institutions with the other duties that that entails, it was difficult to find the time for completing the book. One of the features of this book is that we have explicitly described algorithms that are implicit in many of the proofs and have commented on their complexity. Throughout we have given credit for results that have previously occurred in the literature. There is a bibliography given at the end of each chapter as well as a complete bibliography (including some papers not cited in the text) at the end of the book. That it might be worthwhile to investigate systems of linear equations for which the signs of the solution could be determined knowing only the signs of its coefficients was recognized by Samuelson in his book "Foundations of Economic Analysis". The mathematical study of sign-solvability, in particular of sign-nonsingular matrices, was begun by L. Bassett, J. Maybee and J. Quirk in their paper "Qualitative economics and the scope of the correspondence principle"} in 1968. Since the appearance in 1984 of the paper "Signsolvability revisited" by V. Klee, R. Ladner and R. Manber, there has been renewed interest in the subject. Indeed we were first attracted to sign-solvability and related topics by this paper. The essential idea of a sign-nonsingular matrix arose in a different context in the 1963 paper "Dimer statistics and place transitions" by P.W. Kastelyn. A key paper in the development that proceeded from Kastelyn's work is the 1975 paper "A characterization of convertible (0,1)-matrices" by C.H.C. Little. The connection between the two different points of view was made in RAB's 1988 paper "Counting permutations with restricted positions: Permanents of (0,1)-matrices. A tale in four parts." We wish to thank the IMA for providing a stimulating environment in which to work during 1991-1992, the financial support given to RAB and the postdoctoral fellowship awarded to BLS. We are grateful to Victor Klee for the encouragement he has given us in completing this project. During the period this book was written, RAB was also partially supported by NSF Grant No. DMS-9123318.