Minimum ranks of sign patterns via sign vectors and duality
Marina Arav, Frank J. Hall, Zhongshan Li, Hein van der Holst, John Sinkovic, Lihua Zhang · Electronic Journal of Linear Algebra · 2015
A sign pattern matrix is a matrix whose entries are from the set {+,−,0}. The minimum rank of a sign pattern matrix A is the minimum of the ranks of the real matrices whose entries have signs equal to the corresponding entries of A. It is shown in this paper that for any m×n sign pattern A with minimum rank n − 2, rational realization of the minimum rank is possible. This is done using a new approach involving sign vectors and duality. It is shown that for each integer n ≥ 9, there exists a nonnegative integer m such that there exists an m × n sign pattern matrix with minimum rank n − 3 for which rational realization is not possible. A characterization of m × n sign patterns A with minimum rank n − 1 is given (which solves an open problem in Brualdi et al. [R. Brualdi, S. Fallat, L. Hogben, B. Shader, and P. van den Driessche. Final report: Workshop on Theory and Applications of Matrices Described by Patterns. Banff International Research Station, Jan. 31 – Feb. 5, 2010.]), along with a more general description of sign patterns with minimum rank r, in terms of sign vectors of certain subspaces. Several related open problems are stated along the way.