Combinatorial and Graph-Theoretical Problems in Linear Algebra

1. Front Matter

   Pages i-xv

   PDF

2. Symbolic Dynamics and Matrices

   • Mike Boyle

   Pages 1-38

3. Mixed Matrices: Irreducibility and Decomposition

   • Kazuo Murota

   Pages 39-71

4. A Geometric Approach to the Laplacian Matrix of a Graph

   • Miroslav Fiedler

   Pages 73-98

5. Qualitative Semipositivity

   • Charles R. Johnson, David P. Stanford

   Pages 99-105

6. Eigenvalues in Combinatorial Optimization

   • Bojan Mohar, Svatopluk Poljak

   Pages 107-151

7. Eutactic Stars and Graph Spectra

   • Peter Rowlinson

   Pages 153-164

8. Some Matrix Patterns Arising in Queuing Theory

   • Clark Jeffries

   Pages 165-174

9. Laplacian Unimodular Equivalence of Graphs

   • Robert Grone, Russell Merris, William Watkins

   Pages 175-180

10. Rank Incrementation via Diagonal Perturbations

    • Wayne Barrett, Charles R. Johnson, Raphael Loewy, Tamir Shalom

    Pages 181-187

11. Eigenvalues of Almost Skew Symmetric Matrices and Tournament Matrices

    • Shmuel Friedland

    Pages 189-206

12. Combinatorial Orthogonality

    • Leroy B. Beasley, Richard A. Brualdi, Bryan L. Shader

    Pages 207-218

13. The Symmetric Group as a Polynomial Space

    • Marston Conder, Chris D. Godsil

    Pages 219-227

14. Completely Positive Graphs

    • Abraham Berman

    Pages 229-233

15. Hadamard Matrices

    • W. D. Wallis

    Pages 235-243

16. Self-Inverse Sign Patterns

    • Carolyn A. Eschenbach, Frank J. Hall, Charles R. Johnson

    Pages 245-256

17. Open Problems

    • Richard A. Brualdi, Shmuel Friedland, Victor Klee

    Pages 257-260

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.

• Eigenvalue
• Matrix
• algebra
• field
• linear algebra
• matrices
• matrix theory

• Department of Mathematics, University of Wisconsin, Madison, USA

  Richard A. Brualdi

• Department of Mathematical Statistics and Computer Science, University of Illinois at Chicago, Chicago, USA

  Shmuel Friedland

• Department of Mathematics, University of Washington, Seattle, USA

  Victor Klee

Policies and ethics