Theory and Applications of Matrices Described by Patterns (10w5024)

Objectives

A workshop on classes of matrices described by various patterns would provide a single forum in which recent important results and applications would be disseminated, and from which new collaborations could emerge. Such a workshop would enable researchers in combinatorial matrix theory to keep abreast of developments central to their own interests and expose them to the array of recent activity and new applications taking place in this important and emerging area. It would also enable research in applied areas to become familiar with theoretical results that have application.

Two objectives of the workshop are:

1) To bring together researchers with differing perspectives, including those in other areas of the mathematical and computational sciences that use the concepts of pattern matrices, but often with differing terminology.

For example, recently connections have been identified between minimum rank results and communication complexity. While researchers in this field have recognized the importance of linear algebra, many are unaware of recent results on the minimum rank problem; analogously, researchers working on minimum rank are often unaware of recent developments in communication complexity. Even the terminology differs – minimum rank (of a sign pattern) is called dimension complexity in the communication complexity literature. Bridging this gap is one goal of the workshop, which is particularly timely due to the large number of papers and talks related to these two different approaches over the past few years.

Within discrete mathematics itself, there are differing perspectives that this workshop will address. For example, spectral graph theorists study the eigenvalues of certain matrices associated with a graph, including the adjacency matrix and the Laplacian matrix, with an emphasis on obtaining combinatorial (e.g. connectivity) or geometric (e.g. planarity, embeddability) information. Recently Colin de Verdiere-type parameters have led to the study of patterns from a graph theoretical perspective; this approach to pattern problems needs further development.

2) To simultaneously examine several specific problems from the perspective of the three pattern types. From the combinatorial matrix point of view, we expect such a parallel attack on specific problems to be particularly effective.

For example, although many researchers on minimum rank (equivalently maximum eigenvalue multiplicity) problems are aware of the strategies used to attack the problem for each type of pattern, we hope a group discussion of the similarities and differences in the approaches to the minimum rank problem across the three types of patterns will lead to a more unified approach.

A BIRS workshop on matrices described by patterns in 2010 would be the first workshop devoted to this subject since the very successful "Spectra of families of matrices described by graphs, digraphs, and sign patterns," held at the American Institute of Mathematics (AIM) Oct. 23-27, 2006, which led to numerous publications. The titles of both this proposed workshop and the AIM workshop were inspired by the emergence of pattern matrices as a dominant theme in the successful 2-day workshop "Directions in Combinatorial Matrix Theory" held at BIRS May 6-8, 2004. This is an area of substantial and growing interest.

The proposed workshop would be an opportunity to build on these activities and bring together a larger and more scientifically diverse group. It is expected to be a significant catalyst for continued progress and development of the discipline. In addition, it may provide an impetus for the organization of future special sessions dedicated to this subject.

The workshop will welcome participation from junior researchers. In particular, graduate students and postdoctoral fellows will be invited to attend and participate. The organizers will facilitate the building of collaborations between junior and senior researchers by actively involving them in research together. Time will be allotted for this purpose, and the organizers have experience facilitating research groups that include both junior and senior researchers.

The organizers will promote an informal atmosphere to the proceedings, with time for casual discussions and research collaborations. The day plan is designed to promote the sharing of information, identification of open problems, and active research on a small number of such problems as identified by the group.