Minimum ranks of sign patterns via sign vectors and duality

Abstract

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.