On the Binary Rank of Matrices with Constant Real Rank

Abstract

We study the problem of determining upper bounds on the maximal binary rank, $b_d$, of a $0,1$ matrix with real rank $d$, for small constant $d$. We prove a general upper bound of $b_d\le \lfloor \sqrt{d{2}^d+2d}\rfloor -1$. We also develop a general dimension reduction technique of bounding $b_d$ using known upper bounds on $b_{d-1}$ and $b_{d-2}$, as well as prove interesting general structural results on extremal matrices with binary rank $b_d$. This allows us to get improved non-trivial upper bounds on $b_d$ for constant values of $d$, which imply tight bounds on $b_d$ for $3\le d\le 5$. Our results also imply bounds on the equivalent problem of finding the minimum number of bicliques needed to partition the edges of a bipartite graph whose reduced adjacency matrix has real rank at most $d$.