Combinatorial Matrix Classes — What the Book Actually Covers
Richard A. Brualdi's Combinatorial Matrix Classes is one of those reference texts that sits on your shelf and occasionally saves you from re-deriving something you should have remembered. It catalogues how different structural properties of matrices interact — nonnegativity, invertibility, sign patterns, eigenvalue constraints, and the combinatorial rules that govern them. If you work with graph-to-matrix translations, sign-solvable systems, or matrix completion problems, this book is the place to look first. The book organises matrix classes by the combinatorial conditions they satisfy rather than by numerical method. That means instead of grouping by eigenvalue computation technique, you find chapters on nonsingular M-matrices, DB-matrices, sign-nonsingular matrices, polyhedral cones generated by matrices, and classes defined by principal minor behaviour. Each class gets its definition, basic theorems, and references to the original literature. The treatment is theorem-driven. Proofs are present but not always spelled out step-by-step. You will see characterisations, equivalence statements, and counterexamples more often than algorithmic pseudocode.
How to Use This Book Without Losing Hours
Start with the class you care about, not the preface. The chapter on Sign Nonsingular Matrices is dense, but the preliminary sections define terms like strong signed-graph equivalence and bipartite graphs with perfect matchings in a way that lets you skip around once you know the vocabulary. The matrix class definitions rely on each other across chapters, so keep the index open. When you need a result, check the references at the end of each chapter. Brualdi's bibliography is thorough but broad. Narrow it by matching author names you recognise from your own citation trail, then verify the result appears in the chapter you need rather than chasing a paper that turns out to be tangentially related.
A Specific Problem I Ran Into and How I Fixed It
I was working on a sign-solvability question for a sparse system where the constraint matrix had a irregular nonzero pattern. The textbook characterisation for sign-nonsingularity assumes you can verify all allowable matrices share the same sign pattern of determinants, but my matrix had structural zeros that created ambiguous cycles in the associated digraph. Direct application of the standard bipartite-graph matching test gave a false positive because I was treating certain structural zeros as free variables instead of hard constraints. The workaround was to restrict the analysis to the fixed pattern using the concept of admissible matrices rather than the full combinatorial class, then rebuild the signed bipartite graph only on the positions allowed by the nonzero pattern. Once I did that, the Hall-type condition from the book applied cleanly and the sign-singularity was resolved in about twenty minutes instead of spending half a day chasing edge cases in an ad hoc construction.
Get the Full Details
Common Pitfalls That Beginners Miss
People often confuse combinatorial matrix classes with numerical matrix classes. Being an M-matrix in the combinatorial sense requires specific sign and inverse nonnegativity properties, not just eigenvalue location. The book makes this distinction, but readers new to the area tend to apply numerical bounds from standard linear algebra texts and get contradictions when the combinatorial definition does not align with their assumptions. Another frequent issue is treating structural results as computational algorithms. Characterisations involving perfect matchings, cycle covers, or principal minor sign patterns are decision tools. They tell you whether a matrix belongs to a class. They do not generally give you a fast way to compute representatives inside that class or to modify a matrix to enter it. If you need an algorithm, the book points to the literature, but the chapter itself is not an algorithm manual.
Which Sections Are Worth More Time Than Others
The chapters on M-matrices, H-matrices, and sign-nonsingular matrices carry the most practical weight if you deal with stability analysis, ecological models, or economic input-output systems. The sections on polyhedral cones and geometric matrix properties are heavier on theory and lighter on direct application, though they matter when you are proving closure properties or constructing counterexamples. If you only skim, skip the very long list of open problems unless you are looking for research directions. The problem lists are useful references for what is unresolved, but they are not pedagogical material.
Supplementary Reading That Actually Helps
Berman and Plemmons remains the standard companion for M-matrix theory, and many results in Brualdi's book cross-reference it. If your work involves applications to graph theory, coupling the matrix-class results with a modern spectral graph theory text reduces the translation overhead significantly. For sign solvability specifically, the original papers by Root are worth tracking down alongside the book's summary.
Bottom Line
By Richard A Brualdi Combinatorial Matrix Classes is a reliable reference for understanding how matrix properties group together under combinatorial constraints. It is not a tutorial for computation, and it does not replace primary papers when you need the latest extensions. Use it to pin down definitions, check equivalences, and locate the right theorem for a structural question. Treat it as a map, not a vehicle.
