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

This workshop, sponsored by AIM and the NSF, 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.

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.

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email workshops@aimath.org

Plain text announcement or brief announcement.

Go to the American Institute of Mathematics.
Return to the AIM Research Conference Center.