通信复杂度的秩下界

形式陈述

域上的通信矩阵

设 $f:X\times Y\to\{0,1\}$ ，选定域 $\mathbb F$ ，并把 $0,1$ 视为 $\mathbb F$ 中的元素。通信矩阵

M_f=(f(x,y))_{x\in X,y\in Y}

因而成为 $\mathbb F$ 上的线性代数矩阵。记其秩为 $\operatorname{rank}_{\mathbb F}(M_f)$ 。域是定理数据的一部分；同一张 $0/1$ 数表在不同特征下可能有不同秩。

本页讨论确定性零误差通信。核心思路不是把一块矩形直接等同于秩一矩阵，而是观察 1-单色矩形的指示矩阵 是一个外积；协议的所有 1-叶指示矩阵之和恰好还原 $M_f$ 。

矩形指示矩阵引理

对 $R=A\times B$ ，定义列向量 $u_A\in\mathbb F^X$ 与 $v_B\in\mathbb F^Y$ ：属于集合的坐标取 $1$ ，其余取 $0$ 。 $R$ 的指示矩阵为

J_R=u_Av_B^{\mathsf T}.

若 $A,B$ 非空，则 $J_R$ 的列都为 $0$ 或同一向量 $u_A$ ，所以秩为 $1$ ；空矩形的秩为 $0$ 。由秩的次可加性，任意矩阵和满足

\operatorname{rank}\!\left(\sum_{j=1}^k J_{R_j}\right) \le\sum_{j=1}^k\operatorname{rank}(J_{R_j}) \le k.

这里无需假设各 $J_{R_j}$ 线性独立。秩上界只使用“每项最多贡献一维”，正适合把协议叶数转换为代数界。

定理与完整证明

定理。 对任意非零 Boolean function 通信矩阵和任意域 $\mathbb F$ ，

D^{\mathrm{cc}}(f) \ge \left\lceil \log_2\operatorname{rank}_{\mathbb F}(M_f) \right\rceil.

证明。 取一条最坏通信为 $c$ 的确定性正确协议。其可达叶给出互不相交的单色矩形划分，叶数至多 $2^c$ 。只收集输出标签为 $1$ 的叶矩形 $R_1,\ldots,R_k$ 。

对每个输入格 $(x,y)$ ，若 $f(x,y)=1$ ，它恰好属于一个 1-叶；若 $f(x,y)=0$ ，它不属于任何 1-叶。由于叶矩形互不相交，在任意域中都有逐项恒等式

M_f=\sum_{j=1}^k J_{R_j}.

矩形引理与秩次可加性给出

\operatorname{rank}_{\mathbb F}(M_f) \le k \le \#\{\text{全部叶}\} \le2^c.

取二进制对数并对协议最优化即得结论。 $\square$

若 $M_f=0$ ，函数恒为 $0$ 、秩为 $0$ ，而 $\log0$ 无定义；这只是零通信的退化情形，所以定理单独假设矩阵非零。

直觉

一个 1-单色叶只覆盖一块 $A\times B$ ，其指示矩阵的所有非零列都相同，所以只能贡献一个线性方向。协议若只有少量叶，就只能把通信矩阵写成少量秩一外积之和；高秩意味着函数的行列结构包含太多独立方向，无法被这些矩形拼出。

对数仍来自通信树的计数。线性代数先证明至少需要 $\operatorname{rank}(M_f)$ 个 1-叶，树深再通过最多 $2^c$ 个叶把这一数量转成 bit 下界。域决定哪些方向会相消，因此也是证据强度的一部分。

例子与边界

Equality 的满秩实例

对 $X=Y=\{0,1\}^n$ 的 Equality，通信矩阵在相同行列次序下是 $2^n\times2^n$ 单位矩阵。单位矩阵在任意域上都有秩 $2^n$ ，因此

D^{\mathrm{cc}}(\operatorname{EQ}_n)\ge\log_2 2^n=n.

这个推导与 fooling set 使用同一函数，却暴露不同结构：前者看对角点无法共同进入矩形，本页看单位矩阵的行线性独立。两个证据在 Equality 上同样紧，不意味着对所有函数都给相同强度。

域依赖的具体边界

取三元素定义域上的不等函数 $\operatorname{NEQ}(i,j)=\mathbf1[i\ne j]$ ，矩阵为

J-I= \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}.

它的行列式为 $2$ 。在 $\mathbb R$ 上秩为 $3$ ；在特征 $2$ 的域上行列式变为 $0$ ，三行之和也为零，而前两行独立，所以秩为 $2$ 。引用“秩下界”而不标域，会得到两个不同数值却无法判断哪一个是所声称的结论。

不等于 log-rank 猜想

秩定理只给单向蕴含： $\log_2\operatorname{rank}(M_f)$ 是 $D^{\mathrm{cc}}(f)$ 的下界。它没有给出从小秩构造低通信协议的方法。

Log-rank 猜想讨论实数域上确定性通信复杂度能否由 $\log\operatorname{rank}_{\mathbb R}(M_f)$ 的多项式控制。那是一项关于上界的深层主张，而不是本页下界证明的重述。把“ $D\ge\log rank$ ”反向读成“ $D\le O(\log rank)$ ”，会把已证定理变成远强且一般未成立的断言。

允许错误的随机协议也不能直接沿用矩阵精确分解：错误叶使矩阵项不再逐格相等。要处理近似或符号秩，需要改变代数对象和误差规范，不能只把等号改成约等号。

推论与应用

秩下界适合通信矩阵具有清晰代数结构的问题：单位子矩阵、张量积、群矩阵或可直接证明行独立的函数，都能把结构计算迅速转成确定性通信下界。若不同域给出不同秩，可选择最强的合法域结论，但必须在陈述中保留该域。

它提供的是精确矩阵分解的必要条件，不是低秩协议构造器。随机、符号或近似计算需要 approximate rank、sign rank 等重新定义的对象；log-rank 猜想则研究实秩能否反向多项式控制确定性通信，不能由本页定理直接推出。

参考资料

Mehlhorn and Schmidt, “Las Vegas Is Better than Determinism in VLSI and Distributed Computing,” STOC, 1982, pp. 330–337.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Section 1.4.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 2.

形式陈述 ​

域上的通信矩阵 ​

矩形指示矩阵引理 ​

定理与完整证明 ​

Equality 的满秩实例 ​

域依赖的具体边界 ​

不等于 log-rank 猜想 ​