zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Combinatorial matrix classes. (English) Zbl 1106.05001
Encyclopedia of Mathematics and Its Applications 108. Cambridge: Cambridge University Press (ISBN 0-521-86565-4/hbk). x, 544 p. £ 60.00; $ 110.00 (2006).

This excellent book is a sequel to R. A. Brualdi and H. J. Ryser’s classic [Combinatorial matrix theory. Encyclopedia of Mathematics and Its Applications. 39 (Cambridge etc.: Cambridge University Press) (1991; Zbl 0746.05002)], although it functions well as a stand alone volume. It looks in depth at classes of non-negative matrices which have combinatorial significance. A prominent example is 𝒜(R,S), the set of all (0,1) matrices with row sums given by the vector R and column sums given by the vector S. To a graph theorist, this is just the set of bipartite graphs with specified degree sequence. Similarly, the author considers (the adjacency matrices of) graphs and multigraphs with a specified degree sequence and tournaments with a specified score sequence. For these and other combinatorial classes the author systematically develops theory to answer questions such as “When is the class non-empty?”, “How do I construct examples in the class?”, “Can I move between arbitrary examples by a sequence of simple interchanges?” and “How many members does the class have?” The treatment is clearly explained, methodical and accurate and includes details of many important algorithms as well as proofs of many important theorems, although some proofs are necessarily omitted.

Chapter 1 is a basic introduction to the terminology of combinatorial matrix theory including adjacency matrices, term rank, decomposability, majorization, etc. Chapter 2 deals with basic existence results for graphs, flows and tournaments, including theorems by Gale-Ryser, Ford-Fulkerson and Landau. Chapter 3 is devoted to the class 𝒜(R,S) introduced above. It examines many properties of matrices in this class including rank, term rank, permanent, determinant, width, trace, discrepancy, etc. Much of the theory investigates extremal values of these parameters. Chapter 4 looks at more advanced properties of 𝒜(R,S) including the structure of irreducible and fully indecomposable members of the class, the RSK correspondence between matrices and pairs of Young tableaux, Bruhat order on 𝒜(R,S), and so on. Chapter 5 deals with tournament matrices and their generalisations. Chapter 6 is devoted to interchange graphs, that is to graphs formed by taking the matrices in a class as your vertices and joining two matrices by an edge if they differ by an (appropriately defined) simple interchange. Properties such as the diameter and connectivity of this graph are studied, and then applied to the problem of random generation of matrices within a class. Chapter 7 covers much of the earlier ground but with the extra assumption that all matrices are symmetric (both with and without the assumption of zero trace). This case is clearly important in the study of undirected graphs. The final two chapters cover continuous analogues of the discrete objects treated in the first seven chapters. Specifically, they deal with non-negative real matrices with prescribed row and column sums. The set of such matrices form a convex polytope (called a transportation polytope) in Euclidean space. The geometry (extremal points, faces, etc.) of this polytope is studied. The final chapter, Chapter 9, gives a thorough treatment of doubly stochastic matrices (the special case of the matrices from Chapter 8, in which all row and column sums are one). The polytope of all doubly stochastic matrices is studied, as are several interesting subpolytopes. A wealth of results are given for doubly stochastic, substochastic and superstochastic matrices, including a proof of the famous van der Waerden conjecture.

Inevitably, in a text this long, there are some errors. The most important of these spotted by the reviewer were (a) The definition of a ‘log convex’ sequence on page 58 is actually the definition of a ‘convex’ sequence and (b) The case when equality is achieved in Theorem 3.11.3 should have been stated more generally to allow blocks of different sizes. However, the text is well cross-referenced and thoughtfully written, meaning that it is very accessible. All in all, a treasure trove of results written by an acknowledged master of combinatorial matrix theory.

MSC:
05-02Research monographs (combinatorics)
15-02Research monographs (linear algebra)
05B20Matrices (incidence, Hadamard, etc.)
05C50Graphs and linear algebra
05C07Vertex degrees
05C20Directed graphs (digraphs), tournaments
05C85Graph algorithms (graph theory)
05E10Combinatorial aspects of representation theory
15A15Determinants, permanents, other special matrix functions
15A36Matrices of integers (MSC2000)
15A51Stochastic matrices (MSC2000)