Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 23 min ago
PreprintCC BY 4.0arXiv

On the Binary Rank of Matrices with Constant Real Rank

  • Michal Parnas
Open at sourcePDFDOICite

Abstract

We study the problem of determining upper bounds on the maximal binary rank, bd, of a $0,1$ matrix with real rank d, for small constant d. We prove a general upper bound of bd ≤ ⌊ √(d2d + 2d)⌋ −1. We also develop a general dimension reduction technique of bounding bd using known upper bounds on bd−1 and bd−2, as well as prove interesting general structural results on extremal matrices with binary rank bd. This allows us to get improved non-trivial upper bounds on bd for constant values of d, which imply tight bounds on bd for 3 ≤ d ≤ 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.

Related

  1. Exponential Rank Bounds for Random Matrices
    Achintya Raya Polavarapu
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  2. Finite-rank multiplicative perturbations of rotationally invariant non-Hermitian random matrices
    Pierre Bousseyroux, Marc Potters
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv
  3. Low-rank perturbation of symplectic matrices
    Christian Mehl
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Graded Kronecker Modules of Constant Rank
    Jie Liu
    arXivPreprintCC BY-SA 4.0Full textAlgebra & number theoryarXiv
  5. Constant Rank Theorems under Intermediate Ricci Curvature
    Mijia Lai, Guoqiang Wu
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{parnas2026binary,
  title = {{On the Binary Rank of Matrices with Constant Real Rank}},
  author = {Michal Parnas},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.30203},
  eprint = {2609.30203},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.30203},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Binary Rank of Matrices with Constant Real Rank
AU  - Michal Parnas
PY  - 2026
DA  - 2026/10/10
PB  - arXiv
DO  - 10.48550/arxiv.2609.30203
UR  - https://arxiv.org/abs/2609.30203
AB  - 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 ≤ ⌊ √(d2^d + 2d)⌋ −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 ≤ d ≤ 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.
ER  -