Minimum Rank Problems

Hogben, Leslie
Hogben, Leslie
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Journal Issue

A graph describes the zero–nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303–316, C.R. Johnson, A. Leal Duarte, The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra 46 (1999) 139–144], trees allowing loops [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness. Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl. 418 (2006) 389–415], and directed trees allowing loops [F. Barioli, S. Fallat, D. Hershkowitz, H.T. Hall, L. Hogben, H. van der Holst, B. Shader, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra 18 (2000) 126–145]. We survey these results from a unified perspective and solve the minimum rank problem for simple directed trees.

<p>This is a manuscript of an article from <em>Linear Algebra and its Applications </em>432 (2010): 1961, doi:<a href="" target="_blank">10.1016/j.laa.2009.05.003</a>. Posted with permission.</p>
Minimum rank, Maximum nullity, Symmetric minimum rank, Asymmetric minimum rank, Rank, Symmetric matrix, Matrix, Path cover, Path cover number, Zero forcing set, Zero forcing number, Tree, Ditree, Directed tree, Graph