Given a square matrix
, replacing each of its nonzero entries with the symbol * gives its
. Such a pattern is said to be
when it carries essentially no information about the eigenvalues of
. A ...longstanding open question concerns the smallest possible number of nonzero entries in an
×
spectrally arbitrary pattern. The Generalized 2
Conjecture states that, for a pattern that meets an appropriate irreducibility condition, this number is 2
. An example of Shitov shows that this irreducibility is essential; following his technique, we construct a smaller such example. We then develop an appropriate algebraic condition and apply it computationally to show that, for
≤ 7, the conjecture does hold for ℝ, and that there are essentially only two possible counterexamples over ℂ. Examining these two patterns, we highlight the problem of determining whether or not either is in fact spectrally arbitrary over ℂ. A general method for making this determination for a pattern remains a major goal; we introduce an algebraic tool that may be helpful.
Suppose the only thing we know about a matrix is which of its entries are zero. What can we say about its rank? We develop a framework for applying matroid theory to this question. One consequence is ...a generalization of the question to the setting of matroids; over an infinite field, we recover the original question by considering only matroids representable over that field. This framework also lets us revisit prior work on the problem for matrices and clarify how previous results rest on facts about matroids. In the process, we unify and simplify the proofs of these results, and sometimes improve on them a bit. We also derive a few new results, and consider further directions for exploration.
We employ a result of Moshe Rosenfeld to show that the minimum semidefinite rank of a triangle-free graph with no isolated vertex must be at least half the number of its vertices. We define a ...Rosenfeld graph to be such a graph that achieves equality in this bound, and we explore the structure of these special graphs. Their structure turns out to be intimately connected with the zero–nonzero patterns of the unitary matrices. Finally, we suggest an exploration of the connection between the girth of a graph and its minimum semidefinite rank, and provide a conjecture in this direction.
The minimum rank problem is to determine for a graph G the smallest rank of a Hermitian (or real symmetric) matrix whose off-diagonal zero-nonzero pattern is that of the adjacency matrix of G. Here G ...is taken to be a circulant graph, and only circulant matrices are considered. The resulting graph parameter is termed the minimum circulant rank of the graph. This value is determined for every circulant graph in which a vertex neighborhood forms a consecutive set, and in this case is shown to coincide with the usual minimum rank. Under the additional restriction to positive semidefinite matrices, the resulting parameter is shown to be equal to the smallest number of dimensions in which the graph has an orthogonal representation with a certain symmetry property, and also to the smallest number of terms appearing among a certain family of polynomials determined by the graph. This value is then determined when the number of vertices is prime. The analogous parameter over R is also investigated.
The unique Steiner triple system of order 7 has a point-block incidence graph known as the Heawood graph. Motivated by questions in combinatorial matrix theory, we consider the problem of ...constructing a faithful orthogonal representation of this graph, i.e., an assignment of a vector in Cd to each vertex such that two vertices are adjacent precisely when assigned nonorthogonal vectors. We show that d=10 is the smallest number of dimensions in which such a representation exists, a value known as the minimum semidefinite rank of the graph, and give such a representation in 10 real dimensions. We then show how the same approach gives a lower bound on this parameter for the incidence graph of any Steiner triple system, and highlight some questions concerning the general upper bound.
Given a bipartite graph G with bipartition (U,W), we denote by Q(G) the set of all real U×W matrices B=bu,w with bu,w=0 if u and w are non-adjacent, bu,w≠0 if u and w are connected by a single edge, ...and bu,w∈R if u and w are connected by multiple edges. We denote by N(G) the set of all U×W matrices X=xu,w with xu,w=0 if u and w are adjacent. We say that a matrix B∈Q(G) has the Asymmetric Strong Arnold Property (ASAP) if for all X∈N(G), if XTB=0 and BXT=0, then X=0.
If G is a bipartite graph for which there exists a matrix B∈Q(G) that has the Asymmetric Strong Arnold Property, we define the stable minimum bipartite rank mbrS(G) as the smallest rank of any matrix B∈Q(G) having the ASAP. We show that if H is a matching minor of G, then mbrS(G)≤mbrS(H)+1/2(|V(G)|−|V(H)|). If G has a bipartition with parts of the same size, we define the stable maximum bipartite nullity MbS(G) as the largest nullity of any matrix B∈Q(G) having the ASAP. Then MbS(H)≤MbS(G). We give a characterization in terms of forbidden matching minors of the classes of graphs G with MbS(G)=0 and with MbS(G)≤1.
The spark of a matrix is the smallest number of nonzero coordinates of any nonzero null vector. For real symmetric matrices, the sparsity of null vectors is shown to be associated with the structure ...of the graph obtained from the off-diagonal pattern of zero and nonzero entries. The smallest possible spark of a matrix corresponding to a graph is defined as the spark of the graph. Connections are established between graph spark and well-known concepts including minimum rank, forts, orthogonal representations, Parter and Fiedler vertices, and vertex connectivity.
The notion of communication complexity seeks to capture the amount of communication between different parties that is required to find the output of a Boolean function when each party is provided ...with only part of the input. Different variants of the model governing the rules of this communication lead to different connections with problems in combinatorial linear algebra. In particular, problems arise in this context that concern the rank of a (0,1)-matrix and the minimum rank of a matrix meeting a given combinatorial description. This paper surveys these connections.
PDF
