Minimum Rank Problems
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
Comments
This is a manuscript of an article from Linear Algebra and its Applications 432 (2010): 1961, doi:10.1016/j.laa.2009.05.003. Posted with permission.