On the minimum rank of not necessarily symmetric matrices : a preliminary study

By Francesco Barioli, Shaun M. Fallat, H. Tracy Hall, D. Hershkowitz, Leslie Hogben, H. Holst, Bryan L. Shader. 2009

55 citations recorded by the source corpus.

The minimum rank of a directed graph Γ is defined to be the smallest possible rank over all real matrices whose ijth entry is nonzero whenever (i,j) is an arc in Γ and is zero otherwise. The symmetric minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for ij) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity is equal to the difference between the order of the graph and minimum rank in either case. Definitions of various graph parameters used to bound symmetric maximum nullity, including path cover number and zero forcing number, are extended to digraphs, and additional parameters related to minimum rank are introduced. It is shown that for directed trees, maximum nullity, path cover number, and zero forcing number are equal, providing a method to compute minimum rank for directed trees. It is shown that the minimum rank problem for any given digraph or zero-nonzero pattern may be converted into a symmetric minimum rank problem.

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/b02f41b3a58f918a0180e9bb21c31b7be239552b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

Citations in the corpus

Minimum Rank Problems (2010, unknown): “AMS Classification 05C05, 15A03, 15A18”
Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph (2012, background): “The zero forcing number was introduced in [1] and the associated terminology was extended in [2, 3, 11].”