技术摘要：关于布尔秩与二进制秩的数学与计算视角

1. 问题定义与范围

本综述对 0,1 矩阵的布尔秩 ($rank_B(M)$) 和二进制秩 ($rank_{bin}(M)$) 进行了全面的概述，从数学和计算两个视角对其进行了分析。其核心关注点在于它们与实秩 ($rank_R(M)$) 之间的关系。

虽然实秩已被深入理解，且可以通过高斯消元法高效计算，但布尔秩和二进制秩是定义在半环（分别为布尔算术和整数算术）而非域之上的。这种区别导致了显著的行为差异：

• 定义：
  • 实秩： 在 $\mathbb{R}$ 上满足 $M = A \cdot B$ 的最小 $d$。
  • 二进制秩： 在 $\mathbb{Z}$（整数）上满足 $M = A \cdot B$ 且条目为 0,1 的最小 $d$。
  • 布尔秩： 在布尔算术（$1+1=1$）上满足 $M = A \cdot B$ 的最小 $d$。
• 关系： 始终成立的关系有 $rank_R(M) \leq rank_{bin}(M)$ 以及 $rank_B(M) \leq rank_{bin}(M)$。然而，$rank_B(M)$ 与 $rank_R(M)$ 之间的关系非常复杂；$rank_B(M)$ 可能比 $rank_R(M)$ 指数级地小，也可能呈拟多项式级地大。
• 计算复杂度： 与实秩不同，计算布尔秩和二进制秩都是 NP-完全 的。此外，在 $n^{1-\epsilon}$ 因子内近似布尔秩也是 NP-难的。

2. 方法论与替代表述

本文综合了来自线性代数、组合数学、图论和通信复杂性的技术。一个核心主题是将秩函数等价于各种组合问题：

• 单色矩形：
  • $rank_{bin}(M)$ 等于将 $M$ 中的 1 进行划分（partition）所需的最小单色矩形数量（$Partition_1(M)$）。
  • $rank_B(M)$ 等于将 $M$ 中的 1 进行覆盖（cover）所需的最小单色矩形数量（$Cover_1(M)$）。
• 图论： 这些秩对应于对以 $M$ 为邻接矩阵的二分图的边进行划分或覆盖所需的最小**双部图（bicliques）**数量。
• 集合基问题： 这些秩涉及为源自矩阵列的集合族寻找最小集合基（对于二进制秩为正规集合基）。
• 通信复杂度： 这些秩与通信复杂度度量紧密相关：
  • $rank_B(M)$ 决定了非确定性通信复杂度 ($N_1(M) = \lceil \log_2 rank_B(M) \rceil$)。
  • $rank_{bin}(M)$ 决定了无歧义非确定性通信复杂度 ($U(M) = \lceil \log_2 rank_{bin}(M) \rceil$)。
  • 确定性通信复杂度 ($D(M)$) 被限制在 $O(\log_2 rank_{bin}(M))$ 之内。

3. 核心贡献与结果

A. 下界与上界技术

本综述详细介绍了建立这些秩的界限的多种方法：

• 线性代数： 使用特征值（Graham-Pollak 定理）以及将实秩作为下界。对于特定的循环矩阵族 $D_{n,k}$，线性代数证明在某些情况下 $rank_{bin}(D_{n,k}) \geq rank_R(D_{n,k}) + 1$。
• 隔离（Fooling）集： 寻找一组 1，其中任意两个 1 不共享行、列或 2x2 的 1 子矩阵。最大隔离集 $i(M)$ 的大小为两个秩提供了下界。
• 组合数学： 利用 Sperner 定理来限制具有反链行的矩阵的布尔秩（例如，$rank_B(C_n) = \Theta(\log n)$ 对于单位矩阵的补矩阵）。
• 概率方法： 为具有受限零元素的矩阵证明上界（例如，对于每列有 $k$ 个零的矩阵，$rank_B(M) \leq O(k \log n)$）。
• 核化（Kernelization）： 通过移除重复行/列以及全零行/列来减小矩阵规模。核的大小由 $2^{rank}$ 限制，从而实现参数化可解算法。
• 提升技术（Lifting Technique）： 一种来自通信复杂性的强大方法，用于将查询复杂度下界提升到通信复杂度，从而导致 $rank_{bin}(M)$ 与 $rank_B(M)$（及其补矩阵）之间存在拟多项式间隙。

B. 数学性质

本文强调了这些秩与实秩之间的根本区别：

• 生成集与增广： 虽然实秩满足增广性质（添加一个不增加秩的向量会保持依赖关系），但这在布尔秩和二进制秩中失效了。增广存在的充分必要条件是存在一个生成所有其他基的唯一基。
• 满秩子矩阵： 实秩保证存在一个 $d \times d$ 且秩为 $d$ 的子矩阵。这在布尔秩或二进制秩中并不成立。存在这样的例子：矩阵的秩为 $d$，但其所有真子矩阵的秩都严格小于 $d$。
• Kronecker 积： 实秩是乘性的（$rank(A \otimes B) = rank(A)rank(B)$）。布尔秩是亚乘性的，并且已证明对于特定矩阵存在严格不等式（$rank_B(A \otimes B) < rank_B(A)rank_B(B)$，例如 $C_n \otimes C_n$）。二进制秩在 Kronecker 积下的乘性仍是一个开放问题。
• 矩阵与其补矩阵： 对于实秩，$rank(M)$与$rank(\bar{M})$之间的差距最多为 1。对于布尔秩和二进制秩，差距可以是指数级或拟多项式级的。利用提升技术的最新结果表明，$rank_B(M)$可以达到$d^{e^{\Omega(\log d)}}$，而$rank_{bin}(M) = d$。

C. 算法结果

鉴于 NP-难性，综述回顾了松弛策略：

• 参数化算法： 这两种秩相对于秩参数 $d$ 都是参数化可解的（FPT）。存在复杂度约为 $O(2^{2^d} \cdot poly(n))$ 的算法，利用核化来减小问题规模。
• 近似算法：
  • 简单的贪心方法对于二进制秩可以实现 $O(n/\log n)$ 的比例，在特定条件下对于布尔秩可以实现 $O(n/\log^2 n)$。
  • 硬度结果排除了在 $n^{1-\epsilon}$ 因子内的近似。
  • 将问题归约为顶点着色和集合覆盖，为特定矩阵类提供了替代的近似界限。
• 属性测试： 存在非自适应和自适应测试算法，其查询复杂度与矩阵规模无关，但与 $d$ 指数相关（例如，对于二进制秩为 $O(2^{2d}/\epsilon^2)$）。一个关键挑战在于是否存在这样的矩阵：每个小规模子矩阵的秩都很低，但整个矩阵的秩却很高（尽管此类矩阵接近低秩矩阵）。
• 布尔矩阵分解 (BMF)： 综述简要提到了用于近似分解的实际算法，尽管其理论保证有限。

4. 重要性与开放问题

本综述认为，布尔秩和二进制秩作为一种统一的语言，连接了代数、组合数学、图论和通信复杂度。这些领域之间的相互作用解决了一些长期悬而未决的开放问题（例如，通过通信复杂度提升技术推翻了 Alon-Saks-Seymour 猜想），同时也揭示了它们与实秩之间深刻的结构性差异。

文章最后概述了几个关键的开放问题：

1. 子矩阵性质： 寻找一个 0,1 矩阵，其二进制秩为 $d < n$，但每一个 $d \times d$ 的子矩阵的二进制秩都显著较小。
2. Kronecker 乘性： 确定是否存在矩阵 $A, B$ 使得 $rank_{bin}(A \otimes B) < rank_{bin}(A) \cdot rank_{bin}(B)$。
3. 间隙优化： 研究实秩与二进制/布尔秩之间的拟多项式间隙是否是最优的，或者是否存在更大的间隙。
4. 更简单的证明： 为目前依赖复杂提升技术的拟多项式间隙结果寻找组合或代数证明。
5. 近似： 为特定矩阵族开发更好的近似算法。
6. 属性测试： 寻找一个查询复杂度在 $d$ 和 $\epsilon$ 的多项式范围内的二进制秩属性测试算法，或者证明此类算法不存在。

综述强调，尽管已经取得了显著进展，但对这些秩的结构性理解仍不如实秩那样完整，这为数学和理论计算机科学研究提供了丰富的方向。