Combinatorial Matrix Theory (Encyclopedia of Mathematics and its Applications, Series Number 39)

✍ Scribed by Richard A. Brualdi, Herbert J. Ryser

• Publisher: Cambridge University Press
• Year: 1991
• Tongue: English
• Leaves: 378
• Edition: 1
• Category: Library

✦ Synopsis

The book deals with the many connections between matrices, graphs, diagraphs and bipartite graphs. The basic theory of network flows is developed in order to obtain existence theorems for matrices with prescribed combinatorical properties and to obtain various matrix decomposition theorems. Other chapters cover the permanent of a matrix and Latin squares. The book ends by considering algebraic characterizations of combinatorical properties and the use of combinatorial arguments in proving classical algebraic theorems, including the Cayley-Hamilton Theorem and the Jorda Canonical Form.

✦ Table of Contents

Cover
List of Encyclopdedia of Mathematics & its Applications
Title
Copyright
© Cambridge University Press 1991
ISBN 0-521-32265-0
Contents
Preface
1 Incidence Matrices
1.1 Fundamental Concept s
1 .2 A Minimax Theorem
1.3 Set Intersect ions
1.4 Applicat ions
2 Matrices and Graphs
2 1 Basic Concepts
2.2 The Adjacency Matrix of a Graph
2.3 The Incidence Matrix of a Graph
2.4 Line Graphs
2.5 The Laplacian Matrix of a Graph
2.6 Matchings
3 Matrices and Digraphs
3.1 Basic Concept s
3.2 Irreducible Matrices
3.3 Nearly Reducible Matrices
3.4 Index of Imprimitivity and MatrixPowers
3.5 Exponents of Primitive Matrices
3.6 Eigenvalues of Digraphs
3.7 Computational Considerations
4 Matrices and Bipartite Graphs
4.1 Basic Facts
4.2 Fully Indecomposable Matrices
4.3 Nearly Decomposable Matrices
4.4 Decomposition Theorems
4.5 Diagonal Structure of a Matrix
5 Some Special Graphs
5 1 Regular Graphs
5.2 Strongly Regular Graphs
5.3 Polynomial Digraphs
6 Existence Theorems
6 1 Network Flows
6.2 Existence Theorems for Matrices
6.3 Existence Theorems for SymmetricMatrices
6.4 More Decomposition Theorems
6.5 A Combinatorial Duality Theorem
7 The Permanent
7.1 Basic Properties
7.2 Permutations with Restricted Positions
7.3 Matrix Factorization of the Permanent and the Determinant
7 . 4 Inequalit ies
7.5 Evaluat ion of Permanent s
8 Latin Squares
8.1 Latin Rectangles
8.2 Partial Transversals
8.3 Partial Latin Squares
8.4 Orthogonal Latin Squares
8.5 Enumeration and Self-Orthogonality
9 Combinatorial Matrix Algebra
9.1 The Determinant
9.2 The Formal Incidence Mat rix
9.3 The Formal Intersection Matrix
9.4 MacMahon's Master Theorem
9.5 The Formal Adj acency Matrix
9.6 The Formal Laplacian Matrix
9.7 Polynomial Identit ies
9.8 Generic Nilpotent Mat rices
MASTER REFERENCE LIST
INDEX
Back Cover