The idea of a matrix goes back to Arthur Cayley (1821--1895) in nineteenth century England. He was proud of the fact that he had invented a mathematical object that was absolutely useless. Rarely has such a declaration proved more wrong.

Graph theory is the outgrowth of ideas that Leonhard Euler (1707--1783) used to study the configuration of bridges in Königsberg. In the hands of Paul Erdös (1913--1996) and many others, graphs saw an explosion both in theory and in applications in the twentieth century.

The purpose of the present workshop was to study problems that are on the interface of matrix theory and graph theory--often referred to as combinatorial matrix theory. The two fields can inform each other in a number of profound and surprising ways. Experts from both fields attended the workshop, and the goal was to form mixed working groups in which the two different points of view could interact productively.

How are matrices and graphs related? First, a graph is a collection of points in the plane and arcs connecting some of those points. See Figure 1.

Associated with a given graph is its adjacency matrix. The adjacency matrix for the graph in Figure 1 is shown in Figure 2. Observe, for instance, that the matrix has a "1" in the (2,5) (resp. the (5,2)) position because the vertices 2 and 5 in the graph are connected (i.e., they are "adjacent"). Likewise, there is a "0" in the (2,3) (resp. the (3,2)) position in the matrix because the vertices 2 and 3 are not connected (i.e., they are not adjacent). Obviously the adjacency matrix of a graph is symmetric. We may understand properties of the graph by analyzing the adjacency matrix, and vice versa.

Another matrix that may be associated with a graph is the Laplacian matrix. For this we need some terminology. Given a vertex i of a graph, the degree d_i of that vertex is the number of edges coming into the vertex. For example, in Figure 1, the vertex 5 has degree 4, vertices 3 and 4 have degree 2, and vertices 1 and 2 have degree 1. Now the Laplacian matrix associated to a graph is given by the diagonal matrix of degrees (i.e., the (1,1) position has the degree of vertex 1, the (2,2) position has the degree of vertex 2, etc.) less the adjacency matrix. Analytically, the Laplacian matrix of the graph G is described in two different points of view could interact productively. Display 3. Clearly the Laplacian matrix of a graph is also a symmetric matrix.

One of the focus problems for this workshop was the minimum rank problem. This question is to determine the minimum rank of the symmetric matrices whose zero/nonzero pattern agrees with the 0/1 pattern of the adjacency matrix of a graph for off-diagonal entries but where the diagonal entries can be arbitrary.

The graph Γ(A) of a symmetric n x n matrix A is the graph having vertices {1, 2, ..., n}, with edge {i, j} present if and only if i ≠ j and a_ij ≠ 0. Note that the diagonal of A is irrelevant in determining Γ(A). Also, if A_G is the adjacency matrix of G and L_G is the Laplacian of G then Γ(A_G) = Γ(L_G) = G. The family of symmetric matrices described by G is all symmetric matrices A such that Γ(A) = G.

A second focus problem was the "energy problem". We define the energy of a graph to be the sum of the absolute values of the eigenvalues of the adjacency matrix. The question then is to find the maximum energy of all graphs with a fixed number of vertices. Graphs with maximum energy have much symmetry.

The energy per vertex was considered and computed for some well-known graphs and families of graphs. For regular graphs, in particular cubic graphs, a conjecture was made for the maximum energy per vertex. In addition the Laplacian energy (i.e., the sum of absolute values of the eigenvalues of the Laplacian matrix) was investigated with several interesting directions considered.

A third focus problem for the workshop was the 2n-conjecture for spectrally arbitrary sign patterns. Namely, given an n x n array, let us specify in advance that a certain number of the entries will be 0. Let the remaining entries be specified to be postive or negative. The question is whether all possible characteristic polynomials arise. Such a configuration is called a spectrally arbitrary sign pattern. [Note that a similar question may be posed over finite fields with only the zero-nonzero pattern described---where it is easily solved with just a counting argument---or over the complex numbers.] Over the reals, one often restricts the sign of each entry to +, -, 0 rather than to zero vs. nonzero. It is conjectured that a spectrally arbitrary pattern matrix must have at least 2n nonzero entries. And in fact it is known that such a matrix must have at least 2n-1 nonzero entries. So the question is: Is the number 2n or 2n-1?

A better understanding of the underlying mathematics of the 2n-conjecture was obtained at this workshop and several related problems were posed. We hope that progress on these easier problems will lead to the development of the tools that will aid with the resolution of the 2n-conjecture. In addition, several new methods for constructing spectrally arbitrary patterns were created.

One approach taken to the minimum rank problem was to view minimum rank as a graph parameter. A graph parameter is an object--often numerical--that one can associate to a graph, and which is invariant under graph equivalence. Examples of useful graph parameters are: (i) For a graph G, determine the maximal number of vertices, no pair of which is joined by an edge. This is the vertex independence number. In Figure 1, the vertex independence number is 4. (ii) An assignment of a color to each vertex of a graph G so that no two adjacent vertices are the same color is a proper coloring of G. The chromatic number of G is the least number of colors that yields a proper coloring. The chromatic number of the graph G in Figure 1 is also 3. Minimum rank can be treated as a graph parameter and used to investigate graphs.

One interesting line of investigation has been to use computers to aid in these investigations. A computer package to calculate the minimum rank of a matrix of given size was developed at this workshop. It is expected that this package will facilitate investigation up to size 8. An OnLine catalog of minimum rank of certain families of graphs and of all graphs up to size 6 was also developed here. Certainly Mathematica, Maple, and MatLab are used routinely to perform calculations---especially for large matrices. The fact is that the computer calculations are computationally expensive even for small matrices; for matrices of size 6 x 6 and higher they rapidly can become infeasible (in the real case). So the use of computing machinery works hand-in-hand with the use of mathematical ideas.

At this workshop, minimum rank problems were also investigated from the perspective of graph operations and the minimum rank of special types of graphs was investigated. Certainly the minimum rank problem was the focus of much attention during the week.

Today matrices have applications in coding theory, signal processing, image analysis, and many other applied fields. Graph theory comes up in queueing theory, cryptography, probability, and many other branches of discrete science. This workshop represents a marriage, and a symbiosis, of the two fields. It brought together two groups of mathematician with two different points of view, and resulted in significant progress in the field.