Birkhoff–von Neumann 定理

Birkhoff–von Neumann 定理是概率论和组合数学中的重要结论. 该定理说明了任意双随机矩阵总在置换矩阵的凸包中, 即, 一个任意行和是 $1$, 任意列和也是 $1$ 的非负方阵, 总是一些置换矩阵的非负系数线性组合. 因此, 也将所有 $n$ 阶双随机矩阵构成的集合称 Birkhoff 多胞体, 记作 $B_n$.

1叙述与证明

定理 1.1 (Birkhoff–von Neumann). $n$ 阶双随机矩阵集是 $n$ 阶置换矩阵的凸包, 即$$B_n=\mathrm{conv}(S_n)$$

证明. 首先注意到 $S_n\subset B_n$, 因为置换矩阵每行每列恰一个元素为 $1$, 其余皆 $0$. 而 $B_n$ 显然在凸组合下封闭, 因此 $S_n$ 的凸包含于 $B_n$. 下面证明另一边, 对一个双随机矩阵 $X$, 我们需要寻找一系列置换矩阵 $\{P_i{\}}_{i=1}^k$, 使得 $X={\sum }_i{\theta }_i{P}_i$, 其中诸 ${\theta }_i$ 皆为正实数且总和为 $1$.

为此, 我们需证明这样一个引理, 对任意双随机矩阵 $X$, 总存在置换矩阵 $P$, 若矩阵元 $P_{ij}=1$ 则 $X_{ij}>0$. 该引理的证明只需使用 Hall 定理, 现在构造二部图 $G$, 顶点集 $V\bigsqcup W$ 两部分为 $X$ 所有的行 $V$ 和 $X$ 所有的列 $W$. 对于边集 $E$, 如果 $X$ 的行 $v$ 和列 $w$ 相交的矩阵元大于 $0$, 则连边 $vw$, 否则不连边.

我们只需证明 $G$ 符合 Hall 定理的条件, 这样 Hall 定理的结果, $G$ 中一个完美匹配存在, 翻译为矩阵语言就是说我们引理所需的那置换矩阵存在. 也就是说, 我们要检查, 任选 $r$ 行 $v_1,\cdots ,v_r$, 这 $r$ 行中存在至少 $r$ 列 $w_1,\cdots ,w_r$, 每列与这 $r$ 行相交的 $r$ 个矩阵元中至少一个为正. 假若不是这样, 那么这 $r$ 行中非零的列至多只有 $r-1$ 列, 这导致这些列和的和, 至少是这些列与 $r$ 行相交的元素和 $S$, 由于双随机矩阵行和为 $1$, 也就有 $S=r$. 但是双随机矩阵列和为 $1$, 不超过 $r-1$ 列的列和总量也不会超过 $r-1$, 不可能大于等于 $r$, 至此推出矛盾, 从而 Hall 定理的条件得以验证, 引理得证.

回到原定理的证明, 现在从 $X_0:=X$ 出发, 构造 $P_1$ 为符合引理条件的置换矩阵, 考虑 $P_1$ 对应的 $n$ 个正矩阵元 $(X_0{)}_{ij}$ 中的最小值记作 ${\alpha }_1$, 显然 $0<{\alpha }_1\le 1$, 那么 $X_0-{\alpha }_1{P}_1$ 的所有矩阵元仍然非负, 而且行和与列和都是 $1-{\alpha }_1$, 所以 $X_0-{\alpha }_1{P}_1=(1-{\alpha }_1)X_1$ 对某 $X_1\in B_n$. 注意到这样产生的 $X_1$ 非零矩阵元数量严格少于 $X_0$ 者, 因此我们只需对 $X_i$ 归纳地构造出 ${\alpha }_{i+1},P_{i+1},X_{i+1}$, 这样下去总有某 $X_{k+1}=0$, 从而$$X=X_0={\alpha }_1{P}_1+(1-{\alpha }_1)X_1={\alpha }_1{P}_1+(1-{\alpha }_1){\alpha }_2{P}_2+(1-{\alpha }_1)(1-{\alpha }_2)X_2=\cdots .$$于是令 ${\theta }_1={\alpha }_1,{\theta }_2=(1-{\alpha }_1){\alpha }_2,\cdots$ 直到 ${\theta }_k$, 原定理所需的构造完成.

$\square$

2推论与推广

推论 2.1. 如果 $n\times n$ 矩阵 $X$ 的系数都是非负整数, 而且任意行和, 任意列和都是某 $m\ge 0$. 则存在一系列置换矩阵 $P_1,\cdots ,P_m$ 使得 $X=P_1+\cdots +P_m$.

证明. 该推论的证明可以直接调用上述 Birkhoff–von Neumann 定理证明过程中的引理 (只需对 $X/m$ 使用) 得到: 从 $X$ 出发, 可构造 $P$ 使 $X-P$ 非负而且行和列和都是 $m-1$, 即可归纳.

$\square$

推论 2.2. 对原定理, 可要求线性组合中只出现 $k\le (n-1{)}^2+1$ 个置换矩阵.

证明. 注意到 $B_n$ 活在 $n\times n$ 实矩阵 $M_n(\mathbb{R})$ 的一个 $(n-1{)}^2$ 维的仿射子空间中, 容易验证 $n$ 个行和条件以及 $n$ 个列和条件, 其中任意 $2n-1$ 条是线性无关的 (实际上所有行和条件加起来, 等于所有列和条件加起来, 就是说所有矩阵元和为 $n$), 所以仿射空间维数为 $d=n^2-(2n-1)=(n-1{)}^2$. 现在对一个 $d$ 维仿射空间中的凸集, 它对应一个原点出发的 $d+1$ 维凸锥, 如果其中某元素 $X$ 是超过 $d+2$ 个向量 $P_1,\cdots ,P_k$ 的非负线性组合, 那么其中必然存在 $d+2$ 个 $P_i$ 线性相关, 那么可利用它们的线性相关表达式和 $X$ 写成的线性组合, 消去组合中的一个系数的同时保护其他系数非负. 由此下去 $k$ 不断变小, 最后至多只剩下 $d+1$ 个 $P_i$ 出现在 $X$ 的表达式中.

$\square$

原定理证明过程中用完美匹配来寻找 Birkhoff 分解 (一个符合原定理条件的线性组合) 的算法, 称 Birkhoff 算法, 是标准的贪心算法. 实际上使用该算法就能保证得到一个 $k\le (n-1{)}^2+1$ 的线性组合 (当然 $k\le n^2$ 是平凡的上界因为只有这么多矩阵元), 这在 1960 年由 Joshnson, Dulmage and Mendelsohn 证明. 由维数限制, 这个界也是紧的, 就是说对处在一般位置的双随机矩阵, 确实需要如此多个置换矩阵. 由于完美匹配只需多项式时间 (例如使用 Ford–Fulkerson 算法计算最大流) 就能找到, 因此 Birkhoff 算法也只需要多项式时间, 然而找到最小线性组合, 也就是找一个置换矩阵数量最小的组合却是 NP-难的.