nach oben

1993 | Buch

Kapitel lesen Erstes Kapitel lesen

Combinatorial and Graph-Theoretical Problems in Linear Algebra

herausgegeben von: Richard A. Brualdi, Shmuel Friedland, Victor Klee

Verlag: Springer New York

Buchreihe : The IMA Volumes in Mathematics and its Applications

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Symbolic Dynamics and Matrices

Abstract

The main purpose of this article is to give some overview of matrix problems and results in symbolic dynamics. The basic connection is that a nonnegative integral matrix A defines a topological dynamical system known as a shift of finite type. Questions about these systems are often equivalent to questions about “persistent” or “asymptotic” aspects of nonnegative matrices. Conversely, tools of symbolic dynamics can be used to address some of these questions. At the very least, the ideas of conjugacy, shift equivalence and strong shift equivalence give viewpoints on nonnegative matrices and directed graphs which are at some point inevitable and basic (although accessible, and even elementary).

Mike Boyle

Mixed Matrices: Irreducibility and Decomposition

Abstract

This paper surveys mathematical properties of (layered-) mixed matrices with emphasis on irreducibility and block-triangular decomposition. A matrix A is a mixed matrix if A = Q + T, where Q is a “constant” matrix and T is a “generic” matrix (or formal incidence matrix) in the sense that the nonzero entries of T are algebraically independent parameters. A layered mixed (or LM-) matrix is a mixed matrix such that Q and T have disjoint nonzero rows, i.e., no row of A = Q + T has both a nonzero entry from Q and a nonzero entry from T. The irreducibility for an LM-matrix is defined with respect to a natural admissible transformation as an extension of the well-known concept of full indecomposability for a generic matrix. Major results for fully indecomposable generic matrices such as Frobenius’ characterization in terms of the irreducibility of determinant are generalized. As for block-triangularization, the Dulmage-Mendelsohn decomposition is generalized to the combinatorial canonical form (CCF) of an LM-matrix along with the uniqueness and the algorithm. Matroid-theoretic methods are useful for investigating a mixed matrix.

Kazuo Murota

A Geometric Approach to the Laplacian Matrix of a Graph

Abstract

Let G be a finite undirected connected graph with n vertices. We assign to G an (n - 1)-simplex ∑(G) in the point Euclidean (n - 1)-space in such a way that the Laplacian L(G) of G is the Gram matrix of the outward normals of ∑(G). It is shown that the spectral properties of L(G) are reflected by the geometric shape of the Steiner circumscribed ellipsoid S of ∑(G) in a simple manner. In particular, the squares of the half-axes of S are proportional to the reciprocals of the eigenvalues of L(G). Also, a previously discovered relationship to resistive electrical circuits is mentioned.

Miroslav Fiedler

Qualitative Semipositivity

Abstract

A real m-by-n matrix A is called semipositive (SP) provided there is a real -nvector x ≥ 0 such that Ax > 0. Vector and matrix inequalities here and throughout the paper denote entrywise inequalities.

Charles R. Johnson, David P. Stanford

Eigenvalues in Combinatorial Optimization

Abstract

In the last decade many important applications of eigenvalues and eigenvectors of graphs in combinatorial optimization were discovered. The number and importance of these results is so fascinating that it makes sense to present this survey.

Bojan Mohar, Svatopluk Poljak

Eutactic Stars and Graph Spectra

Abstract

The eutactic stars to be considered arise naturally from the spectral decomposition of an adjacency matrix of a graph. The role of these stars is discussed in relation to (i) local modifications of graphs, (ii) the construction of star partitions of a graph. Some exploratory results relate these star partitions to the structure of the underlying graph.

Peter Rowlinson

Some Matrix Patterns Arising in Queuing Theory

Abstract

A remarkably versatile dynamical system is given by

$$ d{p_i}/dt = \sum\limits_{{\begin{array}{*{20}{c}} {j = 1} \\ {j \ne i} \\ \end{array} }}^n {{a_{{ij}}}{p_j} - (\sum\limits_{{\begin{array}{*{20}{c}} {j = 1} \\ {j \ne i} \\ \end{array} }}^n {{a_{{ji}}}} )} {p_i} $$

where n ≥ 2, {p ₁, p ₂,..., p _n} are system variables, and {a _ij} is a matrix of nonnegative real numbers. Diagonal entries in {a{ do not occur in the model in the sense that they are both added and subtracted in the given sum; for secretarial purposes we set a _ii = 0. The system variables themselves arise from probabilities, so we also assume throughout that at time t = 0, all p _i are nonnegative and the component sum p ₁ + p ₂ +... + p _n is equal to 1.

The goal of this paper is to describe the trajectories of the model in terms of a Lyapunov-like function. Doing so involves the use of theorems of Brualdi and Gersgorin, the graph-theoretic notion of balanced cycles, and the qualitative solvability of an equation involving a Hadamard product.

Clark Jeffries

Laplacian Unimodular Equivalence of Graphs

Abstract

Let G be a graph. Let L(G) be the difference of the diagonal matrix of vertex degrees and the adjacency matrix. This note addresses the number of ones in the Smith Normal Form of the integer matrix L(G).

Robert Grone, Russell Merris, William Watkins

Rank Incrementation via Diagonal Perturbations

Abstract

Let M _n (F) denote the set of n-by-n matrices over the field F. We consider the following question: Among matrices A ∈ M _n (F) with rank A = k < n, how many diagonal entries of A must be changed, at worst, in order to guarantee that the rank of A is increased. Our initial motivation arose from an error pointed out in [BOvdD], but we also view this problem as intrinsically important. The simplest example that shows that one entry does not suffice is the familiar Jordan block $ \left[ \begin{gathered} 0 1 \hfill \\ 0 0 \hfill \\ \end{gathered} \right]. $

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

Eigenvalues of Almost Skew Symmetric Matrices and Tournament Matrices

Abstract

A real square matrix C is called almost skew symmetric if C = S + A where S is a rank one real symmetric matrix and A is a real skew symmetric matrix. We shall show that the real eigenvalues of almost skew symmetric matrices satisfy remarkable inequalities. We shall apply these and other inequalities to estimate the spectral radii of the tournament matrices.

Shmuel Friedland

Combinatorial Orthogonality

Abstract

By considering a combinatorial property of orthogonality we determine the minimum number of nonzero entries in an orthogonal matrix of order n which cannot be decomposed into two smaller orthogonal matrices.

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

The Symmetric Group as a Polynomial Space

Abstract

A design in a polynomial space is a natural generalisation of the concepts of design and orthogonal array in design theory. In this paper we further develop the second author’s theory of polynomial spaces. As a consequence we prove that a subgroup of the symmetric group is a t-design if and only it is t-transitive.

Marston Conder, Chris D. Godsil

Completely Positive Graphs

Abstract

The paper describes a qualitative study of completely positive matrices. The main result is

Theorem. A graph is completely positive if and only if it does not contain an odd cycle of length greater than 4.

This theorem is a result of works with Danny Hershkowitz, Bob Grone and Nataly Kogan. The paper is divided into three parts: definitions, a sketch of the proof, and questions.

Abraham Berman

Hadamard Matrices

Abstract

In this survey the ideas of Hadamard matrices are briefly outlined. We mention the existence problem and constructions, relations to block designs, and special types of Hadamard matrices.

W. D. Wallis

Self-Inverse Sign Patterns

Abstract

We first show that if A is a self-inverse sign pattern matrix, then every principal submatrix of A that is not combinatorially singular (does not require singularity) is also a self-inverse sign pattern. Next we characterize the class of all n-by-n irreducible self-inverse sign pattern matrices. We then discuss reducible self-inverse patterns, assumed to be in Frobenius normal form, in which each irreducible diagonal block is a self-inverse sign pattern matrix. Finally we present an implicit form for determining the sign patterns of the off-diagonal blocks (unspecified block matrices) so that a reducible matrix is self-inverse.

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

Open Problems

Abstract

The following problems were presented at an open problems session at the workshop.

Richard A. Brualdi, Shmuel Friedland, Victor Klee

Titel: Combinatorial and Graph-Theoretical Problems in Linear Algebra
herausgegeben von: Richard A. Brualdi
Shmuel Friedland
Victor Klee
Verlag: Springer New York
Electronic ISBN: 978-1-4613-8354-3
Print ISBN: 978-1-4613-8356-7
DOI: https://doi.org/10.1007/978-1-4613-8354-3

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

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