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. (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 \(\mathcal{A}(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 \(\mathcal{A}(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 \(\mathcal{A}(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 \(\mathcal{A}(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.

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 \(\mathcal{A}(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 \(\mathcal{A}(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 \(\mathcal{A}(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.

Reviewer: Ian M. Wanless (Victoria)

##### MSC:

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

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

05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |

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

05C07 | Vertex degrees |

05C20 | Directed graphs (digraphs), tournaments |

05C85 | Graph algorithms (graph-theoretic aspects) |

05E10 | Combinatorial aspects of representation theory |

15A15 | Determinants, permanents, traces, other special matrix functions |

15B36 | Matrices of integers |

15B51 | Stochastic matrices |