Spectra of families of matrices described by graphs, digraphs, and sign patterns

October 23 to October 27, 2006

at the

American Institute of Mathematics, Palo Alto, California

organized by

Richard Brualdi, Leslie Hogben, and Bryan Shader

Original Announcement

This workshop will bring together people interested in combinatorial matrix theory and spectral graph theory for investigation of the following problems:
  1. The 2n-conjecture for spectrally arbitrary sign patterns.
  2. Determination of the minimum rank of symmetric matrices described by a graph.
  3. The energy of graphs.
During the workshop we hope to resolve the 2n-conjecture and develop new approaches to the minimum rank problem that will lead to significant progress in the future. We hope to get a clearer picture of how energy depends on graph structure, and in particular, to understand the structure of graphs with maximal or minimal energy.

The spectrum (i.e., the set of eigenvalues) of a matrix of data plays a vital role in many applications, and sometimes the entries of a data matrix are not known exactly. This has led to several areas of qualitative matrix theory, including the study of sign pattern matrices (matrices having entries in {+,-, 0}), used to describe the family of real matrices where only the signs of the entries are known), and the study of the set of real symmetric n-by-n matrices whose pattern of nonzero off-diagonal entries is described by a graph. The spectrum of various matrices associated with a graph, such as the adjacency matrix and the Laplacian matrix, can also give information about the graph, or about an application that is modelled by a graph.

Spectrally arbitrary sign patterns allow any possible spectrum of a real matrix, or, equivalently, allow any monic real polynomial as the characteristic polynomial, among the matrices described by the sign pattern. The 2n-conjecture asserts that an n-by-n spectrally arbitrary sign pattern has at least 2n nonzero entries. It is known that a spectrally arbitrary n-by-n sign pattern must contain at least 2n-1 nonzero entries, and numerous examples of spectrally arbitrary n-by-n sign patterns with 2n nonzero entries are known.

Recent work on determination of the spectra of real symmetric n-by-n matrices whose pattern of nonzero off-diagonal entries is described by a graph has focused on multiplicities of eigenvalues (or, equivalently, the minimum rank) among such matrices. The minimum rank of a tree is easily determined, but progress on other graphs has been slow. Techniques from spectral graph theory show promise for this problem.

The energy of a graph (the sum of the absolute values of the eigenvalues of the adjacency matrix) has applications to chemistry. Certain quantities of importance to chemists, such as the heat of formation of a hydrocarbon, are related to pi-electron energy that can be calculated as the energy of an appropriate "molecular'' graph. Although some results on graphs having maximal energy have been obtained, the general question of which graphs have maximal and minimal energy remains open.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

A catalog of spectral data for families of graphs. And the paper containing many of the new results.

The minimum rank of symmetric matrices described by a graph: a survey by Fallat and Hogben.