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

arXiv1503.04486MaRDI QIDQ6259986FDOQ6259986

Amey Bhangale, Swastik Kopparty

Publication date: 15 March 2015

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 $leq3$. We complement this by giving a polynomial time algorithm for determining if a given sign pattern matrix has minimum rank $leq2$. Our result answers one of the open problems from Linial et al. [Combinatorica, 27(4):439--463, 2007].

This page was built for publication: The complexity of computing the minimum rank of a sign pattern matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6259986)