Geodesic
On the minimum rank of not necessarily symmetric matrices: a preliminary study
The electronic journal of linear algebra, Tome 18 (2009), pp. 126-145.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: The minimum rank of a directed graph $\Gamma $is defined to be the smallest possible rank over all real matrices whose ijth entry is nonzero whenever (i, j) is an arc in $\Gamma $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 i = j) 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.
Classification : 05C50, 05C05, 15A03, 15A18
Keywords: minimum rank, maximum nullity, symmetric minimum rank, asymmetric minimum rank, path cover number, zero forcing set, zero forcing number, edit distance, triangle number, minimum degree, ditree, directed tree, inverse eigenvalue problem, rank, graph, symmetric matrix 
@article{ELA_2009__18__a46,
     author = {Barioli, Francesco and Fallat, Shaun M. and Hall, H.Tracy and Hershkowitz, Daniel and Hogben, Leslie and Van Der Holst, Hein and Shader, Bryan},
     title = {On the minimum rank of not necessarily symmetric matrices: a preliminary study},
     journal = {The electronic journal of linear algebra},
     pages = {126--145},
     publisher = {mathdoc},
     volume = {18},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2009__18__a46/}
}
TY  - JOUR
AU  - Barioli, Francesco
AU  - Fallat, Shaun M.
AU  - Hall, H.Tracy
AU  - Hershkowitz, Daniel
AU  - Hogben, Leslie
AU  - Van Der Holst, Hein
AU  - Shader, Bryan
TI  - On the minimum rank of not necessarily symmetric matrices: a preliminary study
JO  - The electronic journal of linear algebra
PY  - 2009
SP  - 126
EP  - 145
VL  - 18
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2009__18__a46/
LA  - en
ID  - ELA_2009__18__a46
ER  - 
%0 Journal Article
%A Barioli, Francesco
%A Fallat, Shaun M.
%A Hall, H.Tracy
%A Hershkowitz, Daniel
%A Hogben, Leslie
%A Van Der Holst, Hein
%A Shader, Bryan
%T On the minimum rank of not necessarily symmetric matrices: a preliminary study
%J The electronic journal of linear algebra
%D 2009
%P 126-145
%V 18
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2009__18__a46/
%G en
%F ELA_2009__18__a46
Barioli, Francesco; Fallat, Shaun M.; Hall, H.Tracy; Hershkowitz, Daniel; Hogben, Leslie; Van Der Holst, Hein; Shader, Bryan. On the minimum rank of not necessarily symmetric matrices: a preliminary study. The electronic journal of linear algebra, Tome 18 (2009), pp. 126-145. http://geodesic.mathdoc.fr/item/ELA_2009__18__a46/