Combinatorial matrix theory

Cover......Page 1
List of Encyclopdedia of Mathematics & its Applications......Page 2
Title......Page 3
ISBN 0-521-32265-0......Page 4
Contents......Page 5
Preface......Page 7
1.1 Fundamental Concept s......Page 11
1 .2 A Minimax Theorem......Page 16
1.3 Set Intersect ions......Page 21
1.4 Applicat ions......Page 27
2 1 Basic Concepts......Page 33
2.2 The Adjacency Matrix of a Graph......Page 34
2.3 The Incidence Matrix of a Graph......Page 39
2.4 Line Graphs......Page 45
2.5 The Laplacian Matrix of a Graph......Page 48
2.6 Matchings......Page 54
3.1 Basic Concept s......Page 63
3.2 Irreducible Matrices......Page 65
3.3 Nearly Reducible Matrices......Page 71
3.4 Index of Imprimitivity and MatrixPowers......Page 78
3.5 Exponents of Primitive Matrices......Page 88
3.6 Eigenvalues of Digraphs......Page 98
3.7 Computational Considerations......Page 106
4.1 Basic Facts......Page 117
4.2 Fully Indecomposable Matrices......Page 120
4.3 Nearly Decomposable Matrices......Page 128
4.4 Decomposition Theorems......Page 135
4.5  Diagonal Structure of a Matrix......Page 146
5 1 Regular Graphs......Page 155
5.2 Strongly Regular Graphs......Page 158
5.3 Polynomial Digraphs......Page 167
6 1 Network Flows......Page 174
6.2 Existence Theorems for Matrices......Page 182
6.3 Existence Theorems for SymmetricMatrices......Page 189
6.4 More Decomposition Theorems......Page 194
6.5 A Combinatorial Duality Theorem......Page 198
7.1 Basic Properties......Page 208
7.2 Permutations with Restricted Positions......Page 211
7.3 Matrix Factorization of the Permanent and the Determinant......Page 219
7 . 4 Inequalit ies......Page 224
7.5 Evaluat ion of Permanent s......Page 245
8.1 Latin Rectangles......Page 260
8.2 Partial Transversals......Page 264
8.3 Partial Latin Squares......Page 269
8.4 Orthogonal Latin Squares......Page 279
8.5 Enumeration and Self-Orthogonality......Page 294
9.1 The Determinant......Page 301
9.2 The Formal Incidence Mat rix......Page 303
9.3 The Formal Intersection Matrix......Page 314
9.4 MacMahon\'s Master Theorem......Page 320
9.5 The Formal Adj acency Matrix......Page 327
9.6 The Formal Laplacian Matrix......Page 334
9.7 Polynomial Identit ies......Page 337
9.8 Generic Nilpotent Mat rices......Page 345
MASTER REFERENCE LIST......Page 355
INDEX......Page 373
Back Cover......Page 378