Affordable Access

The complexity of computing the minimum rank of a sign pattern matrix

Authors
  • Bhangale, Amey
  • Kopparty, Swastik
Type
Preprint
Publication Date
May 14, 2015
Submission Date
Mar 15, 2015
Identifiers
arXiv ID: 1503.04486
Source
arXiv
License
Yellow
External links

Abstract

We show that computing the minimum rank of a sign pattern matrix is NP hard. Our proof is based on a simple but useful connection between minimum ranks of sign pattern matrices and the stretchability problem for pseudolines arrangements. In fact, our hardness result shows that it is already hard to determine if the minimum rank of a sign pattern matrix is $\leq 3$. We complement this by giving a polynomial time algorithm for determining if a given sign pattern matrix has minimum rank $\leq 2$. Our result answers one of the open problems from Linial et al. [Combinatorica, 27(4):439--463, 2007].

Report this publication

Statistics

Seen <100 times