Minimum ranks of sign patterns via sign vectors and duality

Original · EN

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 n× m 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. Bru10), along with a more general description of sign patterns with minimum rank r, in terms of sign vectors of certain subspaces. A number of results on the maximum and minimum numbers of sign vectors of k-dimensional subspaces of Rⁿ are obtained. In particular, it is shown that the maximum number of sign vectors of 2-dimensional subspaces of Rⁿ is 4n+1. Several related open problems are stated along the way.