通信复杂度的秩下界

域上的通信矩阵 ​

设 $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}$ 上的线性代数矩阵。记其秩公理库线性映射的秩Rank of a linear map · Matrix rank线性映射像空间的维数，表示其保留下来的独立输出方向数。为 ${\mathrm{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_A{v}_B^{\mathsf{T}}.$$

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

$$\mathrm{rank}\left(\sum _{j=1}^k{J}_{R_j}\right)\le \sum _{j=1}^k\mathrm{rank}(J_{R_j})\le k.$$

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

定理与完整证明 ​

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

$$D^{\mathrm{cc}}(f)\ge \lceil {\log }_2{\mathrm{rank}}_{\mathbb{F}}(M_f)\rceil .$$

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

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

$$M_f=\sum _{j=1}^k{J}_{R_j}.$$

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

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

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

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

Equality 的满秩实例 ​

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

$$D^{\mathrm{cc}}({\mathrm{EQ}}_n)\ge {\log }_2{2}^n=n.$$

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

域依赖的具体边界 ​

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

$$J-I=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right).$$

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

不等于 log-rank 猜想 ​

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

Log-rank 猜想讨论实数域上确定性通信复杂度能否由 $\log {\mathrm{rank}}_{\mathbb{R}}(M_f)$ 的多项式控制。那是一项关于上界的深层主张，而不是本页下界证明的重述。把“$D\ge \log rank$”反向读成“$D\le O(\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.