Binary rank limits found for matrices with fixed real rank
On the Binary Rank of Matrices with Constant Real Rank
Discrete Mathematics
Summary
Some math researchers studied a special kind of matrix that contains only zeros and ones but also has a fixed rank when using normal real numbers. They found new ways to show upper limits on the ‘binary rank’, which measures how complex the matrix is in a different way. They solved an open problem for matrices with real rank 5 and created general methods that work for other fixed ranks too. Their work also relates to how we can break down connections in certain graphs efficiently.
What this means in practice
- •For network designers: Determine efficient ways to partition network connections modeled as bipartite graphs with limited-ranked adjacency matrices.
- •For database system engineers: Optimize query plans by using upper bounds on binary rank for sparse query matrices with controlled real rank.
A theory result. No direct application yet.
Authors
Michal Parnas
Abstract
We continue the study initiated by Parnas and Shraibman~\cite{PARNAS2026264} who gave upper bounds on the binary rank of $0,1$ matrices which have a small rank over the reals. We give alternative completely mathematical proofs of results proved in~\cite{PARNAS2026264} with the assistance of a computer program, and also solve one of the open problems presented there regarding the maximal binary rank of a matrix with real rank $5$. Moreover, our techniques provide a general method for giving non-trivial upper bounds on the maximal binary rank of a matrix with constant real rank. 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$.