Technical Summary: Mathematical and Computational Perspectives on Boolean and Binary Rank

1. Problem Definition and Scope

This survey provides a comprehensive overview of the Boolean rank ($rank_B(M)$) and binary rank ($rank_{bin}(M)$) of 0,1 matrices, analyzing them from both mathematical and computational perspectives. The primary focus is their relationship to the real rank ($rank_R(M)$).

While the real rank is well-understood and efficiently computable via Gaussian elimination, the Boolean and binary ranks are defined over semi-rings (Boolean arithmetic and integer arithmetic, respectively) rather than fields. This distinction leads to significant differences in behavior:

• Definitions:
  • Real Rank: Minimal $d$ such that $M = A \cdot B$ over $\mathbb{R}$.
  • Binary Rank: Minimal $d$ such that $M = A \cdot B$ over $\mathbb{Z}$ (integers) with 0,1 entries.
  • Boolean Rank: Minimal $d$ such that $M = A \cdot B$ over Boolean arithmetic ($1+1=1$).
• Relationships: It always holds that $rank_R(M) \leq rank_{bin}(M)$ and $rank_B(M) \leq rank_{bin}(M)$. However, the relationship between $rank_B(M)$ and $rank_R(M)$ is complex; $rank_B(M)$ can be exponentially smaller or quasi-polynomially larger than $rank_R(M)$.
• Computational Hardness: Unlike real rank, computing both Boolean and binary ranks is NP-complete. Furthermore, approximating the Boolean rank within a factor of $n^{1-\epsilon}$ is also NP-hard.

2. Methodology and Alternative Formulations

The paper synthesizes techniques from linear algebra, combinatorics, graph theory, and communication complexity. A central theme is the equivalence of rank functions to various combinatorial problems:

• Monochromatic Rectangles:
  • $rank_{bin}(M)$ equals the minimum number of monochromatic rectangles required to partition the 1s of $M$ ($Partition_1(M)$).
  • $rank_B(M)$ equals the minimum number of monochromatic rectangles required to cover the 1s of $M$ ($Cover_1(M)$).
• Graph Theory: These ranks correspond to the minimum number of bicliques needed to partition or cover the edges of a bipartite graph whose adjacency matrix is $M$.
• Set Basis Problems: The ranks relate to finding minimal set bases (normal set bases for binary rank) for families of sets derived from matrix columns.
• Communication Complexity: The ranks are tightly linked to communication complexity measures:
  • $rank_B(M)$ determines the non-deterministic communication complexity ($N_1(M) = \lceil \log_2 rank_B(M) \rceil$).
  • $rank_{bin}(M)$ determines the unambiguous non-deterministic communication complexity ($U(M) = \lceil \log_2 rank_{bin}(M) \rceil$).
  • The deterministic communication complexity ($D(M)$) is bounded by $O(\log_2 rank_{bin}(M))$.

3. Key Contributions and Results

A. Lower and Upper Bound Techniques

The survey details diverse methods for establishing bounds on these ranks:

• Linear Algebra: Using eigenvalues (Graham-Pollak theorem) and real rank as a lower bound. For specific families like circulant matrices $D_{n,k}$, linear algebra proves $rank_{bin}(D_{n,k}) \geq rank_R(D_{n,k}) + 1$ in certain cases.
• Isolation (Fooling) Sets: Finding a set of 1s where no two share a row, column, or 2x2 sub-matrix of 1s. The size of the maximum isolation set $i(M)$ provides a lower bound for both ranks.
• Combinatorics: Utilizing Sperner's theorem to bound the Boolean rank of matrices with anti-chain rows (e.g., $rank_B(C_n) = \Theta(\log n)$ for the complement of the identity matrix).
• Probabilistic Method: Proving upper bounds for matrices with bounded zeros (e.g., $rank_B(M) \leq O(k \log n)$ for matrices with $k$ zeros per column).
• Kernelization: Reducing matrix size by removing duplicate rows/columns and all-zero rows/columns. The kernel size is bounded by $2^{rank}$, enabling fixed-parameter tractable algorithms.
• Lifting Technique: A powerful method from communication complexity used to lift query complexity lower bounds to communication complexity, resulting in quasi-polynomial gaps between $rank_{bin}(M)$ and $rank_B(M)$ (and their complements).

B. Mathematical Properties

The paper highlights fundamental differences between these ranks and the real rank:

• Spanning Sets and Augmentation: While the real rank satisfies the augmentation property (adding a vector that doesn't increase rank preserves dependencies), this fails for Boolean and binary ranks. A necessary and sufficient condition for augmentation is the existence of a unique base spanning all others.
• Full Rank Sub-matrices: Real rank guarantees a $d \times d$ sub-matrix of rank $d$. This does not hold for Boolean or binary ranks. Examples exist where a matrix has rank $d$, but all proper sub-matrices have rank strictly less than $d$.
• Kronecker Products: Real rank is multiplicative ($rank(A \otimes B) = rank(A)rank(B)$). Boolean rank is sub-multiplicative, and strict inequality ($rank_B(A \otimes B) < rank_B(A)rank_B(B)$) has been proven for specific matrices (e.g., $C_n \otimes C_n$). The multiplicativity of binary rank under Kronecker products remains an open question.
• Matrix vs. Complement: The gap between $rank(M)$ and $rank(\bar{M})$ is at most 1 for real rank. For Boolean and binary ranks, the gap can be exponential or quasi-polynomial. Recent results using lifting techniques show $rank_B(M)$ can be $d^{e^{\Omega(\log d)}}$ while $rank_{bin}(M) = d$.

C. Algorithmic Results

Given the NP-hardness, the survey reviews relaxation strategies:

• Parameterized Algorithms: Both ranks are Fixed-Parameter Tractable (FPT) with respect to the rank parameter $d$. Algorithms exist with complexity roughly $O(2^{2^d} \cdot poly(n))$, utilizing kernelization to reduce the problem size.
• Approximation Algorithms:
  • Simple greedy approaches achieve ratios of $O(n/\log n)$ for binary rank and $O(n/\log^2 n)$ under specific conditions.
  • Hardness results preclude approximation within $n^{1-\epsilon}$.
  • Reductions to vertex coloring and set cover provide alternative approximation bounds for specific matrix classes.
• Property Testing: Non-adaptive and adaptive testing algorithms exist with query complexity independent of matrix size but exponential in $d$ (e.g., $O(2^{2d}/\epsilon^2)$ for binary rank). A key challenge is the existence of matrices where every small sub-matrix has low rank, yet the full matrix has high rank (though such matrices are close to low-rank matrices).
• Boolean Matrix Factorization (BMF): The survey briefly notes practical algorithms for approximate factorization, though theoretical guarantees are limited.

4. Significance and Open Problems

The survey argues that the Boolean and binary ranks serve as a unifying language connecting algebra, combinatorics, graph theory, and communication complexity. The interplay between these fields has resolved long-standing open problems (e.g., disproving the Alon-Saks-Seymour conjecture via communication complexity lifting) while revealing deep structural differences from real rank.

The paper concludes by outlining several critical open problems:

1. Sub-matrix Property: Finding a 0,1 matrix where the binary rank is $d < n$, yet every $d \times d$ sub-matrix has a significantly smaller binary rank.
2. Kronecker Multiplicativity: Determining if there exist matrices $A, B$ such that $rank_{bin}(A \otimes B) < rank_{bin}(A) \cdot rank_{bin}(B)$.
3. Gap Optimization: Investigating whether the quasi-polynomial gap between real rank and binary/Boolean rank is optimal or if larger gaps exist.
4. Simpler Proofs: Finding combinatorial or algebraic proofs for the quasi-polynomial gap results currently relying on complex lifting techniques.
5. Approximation: Developing better approximation algorithms for specific matrix families.
6. Property Testing: Finding a property testing algorithm for binary rank with query complexity polynomial in $d$ and $\epsilon$, or proving such an algorithm does not exist.

The survey emphasizes that while significant progress has been made, the structural understanding of these ranks remains less complete than that of the real rank, offering rich directions for future research in both mathematics and theoretical computer science.