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 book presents past and current research on combinatorial and graph-theoretical problems in linear algebra. It offers a glimpse of the increasing role of combinatorial structure in matrix analysis and conversely, of the powerful tool that linear algebra provides in combinatorics and graph theory. The material covered will be of interest to researchers in linear algebra, combinatorics and graph theory.

Symbolic dynamics and matrices.- Mixed matrices: Irreducibility and decomposition.- A geometric approach to the Laplacian matrix of a graph.- Qualitative semipositivity.- Eigenvalues in combinatorial optimization.- Eutactic stars and graph spectra.- Some matrix patterns arising in queuing theory.- Laplacian unimodular equivalence of graphs.- Rank incrementation via diagonal perturbations.- Eigenvalues of almost skew symmetric matrices and tournament matrices.- Combinatorial orthogonality.- The symmetric group as a polynomial space.- Completely positive graphs.- Hadamard matrices.- Self-inverse sign patterns.- Open problems.