Ebook: Combinatorial and Graph-Theoretical Problems in Linear Algebra

This IMA Volume in Mathematics and its Applications COMBINATORIAL AND GRAPH-THEORETICAL PROBLEMS IN LINEAR ALGEBRA is based on the proceedings of a workshop that was an integral part of the 1991-92 IMA program on "Applied Linear Algebra." We are grateful to Richard Brualdi, George Cybenko, Alan George, Gene Golub, Mitchell Luskin, and Paul Van Dooren for planning and implementing the year-long program. We especially thank Richard Brualdi, Shmuel Friedland, and Victor Klee for organizing this workshop and editing the proceedings. The financial support of the National Science Foundation made the workshop possible. A vner Friedman Willard Miller, Jr. PREFACE The 1991-1992 program of the Institute for Mathematics and its Applications (IMA) was Applied Linear Algebra. As part of this program, a workshop on Com­ binatorial and Graph-theoretical Problems in Linear Algebra was held on November 11-15, 1991. The purpose of the workshop was to bring together in an informal setting the diverse group of people who work on problems in linear algebra and matrix theory in which combinatorial or graph~theoretic analysis is a major com­ ponent. Many of the participants of the workshop enjoyed the hospitality of the IMA for the entire fall quarter, in which the emphasis was discrete matrix analysis.

---

This volume aims to gather information from both those who work on linear algebra problems in which combinatorial or graph-theoretical analysis is a major component and those that work on combinatorial or graph-theoretical problems for which linear algebra is a major tool. The fifteen papers in this volume span a wide cross-section of past and current research in the field. Specific topics covered in the papers include matrix problems and results in symbolic dynamics, block-triangular decompositions of mixed matrices, algebraic and geometric properties of Laplacian matrices of graphs, the use of eigenvalues in combinatorial optimization, perturbation effects on rank and eigenvalues, and polynomial spaces. This book should be of interest to researchers in linear algebra, combinatorics and graph theory, and to anyone who wishes to get a glimpse of this fascinating area.

---

This volume aims to gather information from both those who work on linear algebra problems in which combinatorial or graph-theoretical analysis is a major component and those that work on combinatorial or graph-theoretical problems for which linear algebra is a major tool. The fifteen papers in this volume span a wide cross-section of past and current research in the field. Specific topics covered in the papers include matrix problems and results in symbolic dynamics, block-triangular decompositions of mixed matrices, algebraic and geometric properties of Laplacian matrices of graphs, the use of eigenvalues in combinatorial optimization, perturbation effects on rank and eigenvalues, and polynomial spaces. This book should be of interest to researchers in linear algebra, combinatorics and graph theory, and to anyone who wishes to get a glimpse of this fascinating area.
Content:
Front Matter....Pages i-xv
Symbolic Dynamics and Matrices....Pages 1-38
Mixed Matrices: Irreducibility and Decomposition....Pages 39-71
A Geometric Approach to the Laplacian Matrix of a Graph....Pages 73-98
Qualitative Semipositivity....Pages 99-105
Eigenvalues in Combinatorial Optimization....Pages 107-151
Eutactic Stars and Graph Spectra....Pages 153-164
Some Matrix Patterns Arising in Queuing Theory....Pages 165-174
Laplacian Unimodular Equivalence of Graphs....Pages 175-180
Rank Incrementation via Diagonal Perturbations....Pages 181-187
Eigenvalues of Almost Skew Symmetric Matrices and Tournament Matrices....Pages 189-206
Combinatorial Orthogonality....Pages 207-218
The Symmetric Group as a Polynomial Space....Pages 219-227
Completely Positive Graphs....Pages 229-233
Hadamard Matrices....Pages 235-243
Self-Inverse Sign Patterns....Pages 245-256
Open Problems....Pages 257-260

---

This volume aims to gather information from both those who work on linear algebra problems in which combinatorial or graph-theoretical analysis is a major component and those that work on combinatorial or graph-theoretical problems for which linear algebra is a major tool. The fifteen papers in this volume span a wide cross-section of past and current research in the field. Specific topics covered in the papers include matrix problems and results in symbolic dynamics, block-triangular decompositions of mixed matrices, algebraic and geometric properties of Laplacian matrices of graphs, the use of eigenvalues in combinatorial optimization, perturbation effects on rank and eigenvalues, and polynomial spaces. This book should be of interest to researchers in linear algebra, combinatorics and graph theory, and to anyone who wishes to get a glimpse of this fascinating area.
Content:
Front Matter....Pages i-xv
Symbolic Dynamics and Matrices....Pages 1-38
Mixed Matrices: Irreducibility and Decomposition....Pages 39-71
A Geometric Approach to the Laplacian Matrix of a Graph....Pages 73-98
Qualitative Semipositivity....Pages 99-105
Eigenvalues in Combinatorial Optimization....Pages 107-151
Eutactic Stars and Graph Spectra....Pages 153-164
Some Matrix Patterns Arising in Queuing Theory....Pages 165-174
Laplacian Unimodular Equivalence of Graphs....Pages 175-180
Rank Incrementation via Diagonal Perturbations....Pages 181-187
Eigenvalues of Almost Skew Symmetric Matrices and Tournament Matrices....Pages 189-206
Combinatorial Orthogonality....Pages 207-218
The Symmetric Group as a Polynomial Space....Pages 219-227
Completely Positive Graphs....Pages 229-233
Hadamard Matrices....Pages 235-243
Self-Inverse Sign Patterns....Pages 245-256
Open Problems....Pages 257-260
....