Matrices of Sign Solvable Linear Systems
by Richard A. Brualdi and Bryan L. Shader
Expected publication date is June 1995.
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
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.
Go back to home page