Sign patterns with minimum rank 2 and upper bounds on minimum ranks

Abstract

A sign pattern (matrix) is a matrix whose entries are from the set {+, −, 0}. The minimum rank (resp., rational minimum rank) of a sign pattern matrix 𝒜 is the minimum of the ranks of the real (resp., rational) matrices whose entries have signs equal to the corresponding entries of 𝒜. The notion of a condensed sign pattern is introduced. A new, insightful proof of the rational realizability of the minimum rank of a sign pattern with minimum rank 2 is obtained. Several characterizations of sign patterns with minimum rank 2 are established, along with linear upper bounds for the absolute values of an integer matrix achieving the minimum rank 2. A known upper bound for the minimum rank of a (+, −) sign pattern in terms of the maximum number of sign changes in the rows of the sign pattern is substantially extended to obtain upper bounds for the rational minimum ranks of general sign pattern matrices. The new concept of the number of polynomial sign changes of a sign vector is crucial for this extension. Another known upper bound for the minimum rank of a (+, −) sign pattern in terms of the smallest number of sign changes in the rows of the sign pattern is also extended to all sign patterns using the notion of the number of strict sign changes. Some examples and open problems are also presented.

Keywords:

• sign pattern matrix
• minimum rank
• maximum rank
• rational realization
• rational minimum rank
• condensed sign pattern
• number of polynomial sign changes
• number of strict sign changes

AMS Subject Classifications::

• 15B35
• 15B36
• 15B48
• 15A03
• 15A23

Acknowledgements

The authors thank Prof. Bryan Shader for sharing his notes containing proofs of Theorems 3.1 and 3.9. The research of Yubin Gao is supported in part by NNSF of China (No. 11071227).