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

Updated  November 23, 2008

Minimum Rank   2n-conjecture for SAP   Graph Energy   
People   Worshop Materials   Open problems

Minimum Rank

Graph Catalogs and Software for Minimum Rank

Papers based on work done at the Workshop

Papers stimulated by the Workshop


The minimum rank problem (for a simple graph) asks us to determine the minimum rank among all real symmetric matrices whose zero-nonzero pattern of off-diagonal entries is described by  a given simple graph G; this problem  has received considerable attention.  Since the maximum rank is always the order of G (e.g., use a diagonally dominant matrix), there is no interest in an analogous maximum rank problem.  Furthermore, it is straightforward (by considering rank one diagonal perturbations) that any rank between the minimum and full rank can be achieved.  Minimum rank of symmetric matrices described by a graph is also studied over other fields.

The zero-nonzero pattern described by the graph has tremendous influence on minimum rank; for example, a matrix associated with a path on n vertices is a symmetric tridiagonal matrix (up to labeling) with nonzero sub- and super-diagonal and thus has minimum rank n-1, whereas the complete graph on $n$ vertices has minimum rank 1.

The solution (over the real numbers) to the minimum rank problem is equivalent to the determination of the maximum multiplicity of an eigenvalue among the same family of matrices.  The inverse eigenvalue problem of a graph has been an important motivation  for the study of minimum rank.  Given a collection of real numbers,  λ_1, ...,  λ_n, the problem of finding a {symmetric} matrix A that satisfies certain properties and has λ_1, ...,  λ_n as its eigenvalues is called an Inverse Eigenvalue Problem. The Inverse Eigenvalue Problem of a Graph (IEPG) asks us to determine, for a given graph G, what eigenvalues  are possible for a real symmetric matrix A having nonzero off-diagonal entries determined by the adjacency of G.   
 

2n-conjecture for SAP

Notes/Slides from the Workshop

Sign pattern matrices (matrices having entries in {+,-, 0}), are used to describe the family of real matrices where only the signs of the entries are known.  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 (irreducible) n-by-n spectrally arbitrary sign pattern has at least 2n nonzero entries. It is known that an irreducible 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.

Graph Energy

Notes/Slides from the Workshop

Papers arising from the Workshop

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.  Recently the Laplacian energy (the sum of the absolute values of (the eigenvalues of the Laplacian matrix - the average degree of a vertex)) has also been studied.

Workshop Materials

Page of photos from the workshop:  Pix

The following material was generated prior to and immediately after the workshop; much of it is now out of date and there are some errors.  For mathematical content, the reader is advised to consult the more current information above related to each of the three topics, minimum rank, 2n-conjecture/SAP, graph energy.

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.

Glossaries

Leslie Hogben has prepared two glossaries related to the minimum rank problem, one on notation and the other on terminology.

Material from the workshop

The workshop schedule.

A report on the workshop activities (out of date)

A list of open problems (out of date)

A list of participants.