Spectral Properties of Families of Matrices described by Patterns or Graphs

Mini-symposium at 12th ILAS Conference, Regina, June 26-29, 2005

Francesco Barioli, Carleton University, Canada e-mail: fbarioli at math.carleton.ca
Title: Minimum Rank Problem for unicyclic graphs and decomposable graphs
Abstract: Given a certain class of matrices, the Minimum Rank Problem consists on determining the minimum rank of matrices within that class. In particular we will consider classes of symmetric matrices with a prescribed zero-pattern. Since a zero-pattern defines in a natural way an undirected graph, an interesting problem is to investigate the relation between minimum rank and some quantities strictly related to the graph. For instance, for acyclic graphs, the minimum rank is determined by the path cover number of the graph. In this talk we will present a complete characterization of minimum rank for unicyclic graphs and decomposable graphs.

Leslie Hogben, Iowa State University, U.S.A. e-mail: lhogben at iastate.edu slides
Title: A variant on the graph parameters of Colin de Verdiere:
Implications to the minimum rank of graphs
Abstract: For a given undirected graph G, the set of all real symmetric matrices having nonzero off-diagonal entries exactly where the graph G has edges is denoted by S(G). The minimum rank of G is defined to be the smallest possible rank over all matrices in S(G). There has been considerable interest recently in the minimal rank problem and its equivalent formulation, the question of maximal multiplicity of an eigenvalue of a graph. Building upon work in graph theory involving maximal nullity of a subclass of S(G), we introduce a new parameter xi which is based on the maximal nullity of a larger subclass of S(G). For this new parameter we verify some properties analogous to the ones possessed by the existing parameters mu, nu. In addition, we apply these properties associated with xi to learn more about the minimum rank of graphs.

Hein van der Holst, Eindhoven University of Technology, Netherlands  e-mail: H.v.d.Holst at tue.nl  slides
Title: Graphs whose positive semi-definite matrices have nullity at most three.
Abstract: For any graph G=(V, E) with n vertices, let M_G be the set of all real valued symmetric n x n matrices M=[m_i,j] with m_ij = 0 if i not equal to j and i and j are not connected, m_ij not 0 if i not j and i and j are connected by exactly one edge, m_ij in R if i not j and i and j are connected by parallel edges, and m_ii in R for i=1, 2, ..., n. So we allow G to have parallel edges but no loops. Define mnull+(G) as the maximum nullity attained by any positive semi-definite matrix in M_G. The problem is to characterize for a fixed nonnegative integer k the class of graphs G with mnull+(G) <= k. This has been done for k=1, 2. We present some results for the case k=3.

Wayne Barrett, Brigham Young University, U.S.A.  e-mail: wayne at math.byu.edu slides
Title: The Minimal Rank Problem for Finite Fields
Abstract: Given a finite field F and an undirected graph G on n vertices, let S(F, G) be the set of all symmetric n ¥n matrices over F whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(F, G) be the minimum rank of all matrices in S(F, G). The graphs for which mr(F, G) <= 2 have been characterized in two ways and the description depends on whether or not char F = 2. There are important similarities and differences between the results for finite fields and an earlier classification for infinite fields. Prospects for a description of graphs for which mr(F, G) <= 3 for any field F will also be discussed.

Dale Olesky, University of Victoria, Canada e-mail: dolesky at cs.uvic.ca slides
Title Inertially and Spectrally Arbitrary Sign Patterns
Abstract: Recent results about inertially and spectrally arbitrary signs patterns are surveyed, and several examples are given. Techniques that have been used to identify such sign patterns are discussed and some conjectures are considered.

Pauline van den Driessche, University of Victoria, Canada e-mail: pvdd at math.uvic.ca
Title: Spectrally arbitrary star sign patterns
Abstract: An n x n sign pattern S_n is spectrally arbitrary if, for any given real monic polynomial g_n(x) of degree n, there is a real matrix having sign pattern S_n and characteristic polynomial g_n(x). All n x n star sign patterns that are spectrally arbitrary, and all minimal such patterns, are characterized. This subsequently leads to an explicit characterization of all n x n star sign patterns that are potentially nilpotent. It is shown that any super-pattern of a spectrally arbitrary star sign pattern is also spectrally arbitrary.

Zhongshan Li, Georgia State University, U.S.A.  e-mail: matzli at langate.gsu.edu preprint
Title: Can the minimum rank of a sign pattern be achieved by a rational matrix?
Abstract: A sign pattern matrix is a matrix whose entries are from the set {+, -, 0}. The minimum rank of a sign pattern matrix A is the minimum of the ranks of the real matrices whose entries have signs equal to the corresponding entries of A. It is conjectured that the minimum rank of every sign pattern matrix can be realized by a rational matrix. The equivalence of this conjecture to several seemingly unrelated statements are established. For some special cases, such as when A is entrywise nonzero, or the minimum rank of A is at most 2, or the minimum rank of A is at least n-1 (where A is m x n), the conjecture is shown to hold. Connections between this conjecture and the existence of positive rational solutions of certain systems of homogeneous quadratic polynomial equations with all coefficients equal to ±1 are investigated.

Daniel Hershkowitz, Technion, Israel e-mail: hershkow at techunix.technion.ac.il  slides
Title: The relationship between the height characteristic of a matrix and its digraph
Leslie Hogben's Homepage
Leslie Hogben's Research