{"id":"arxiv/2609.30203","url":"https://arxiv.org/abs/2609.30203","tags":["math.CO","cs.DM"],"score":0,"title":"On the Binary Rank of Matrices with Constant Real Rank","domain":"math.CO","source":"arxiv","authors":["Michal Parnas"],"reviews":0,"subject":"math.CO","summary":"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 \\leq \\left\\lfloor \\sqrt{d2^d + 2d}\\right\\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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}