Birkhoff–von Neumann 定理

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

1叙述与证明

定理 1.1 (Birkhoff–von Neumann). 阶双随机矩阵集是 阶置换矩阵的凸包, 即

证明. 首先注意到 , 因为置换矩阵每行每列恰一个元素为 , 其余皆 . 而 显然在凸组合下封闭, 因此 的凸包含于 . 下面证明另一边, 对一个双随机矩阵 , 我们需要寻找一系列置换矩阵 , 使得 , 其中诸 皆为正实数且总和为 .

为此, 我们需证明这样一个引理, 对任意双随机矩阵 , 总存在置换矩阵 , 若矩阵元 . 该引理的证明只需使用 Hall 定理, 现在构造二部图 , 顶点集 两部分为 所有的行 所有的列 . 对于边集 , 如果 的行 和列 相交的矩阵元大于 , 则连边 , 否则不连边.

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

回到原定理的证明, 现在从 出发, 构造 为符合引理条件的置换矩阵, 考虑 对应的 个正矩阵元 中的最小值记作 , 显然 , 那么 的所有矩阵元仍然非负, 而且行和与列和都是 , 所以 对某 . 注意到这样产生的 非零矩阵元数量严格少于 者, 因此我们只需对 归纳地构造出 , 这样下去总有某 , 从而于是令 直到 , 原定理所需的构造完成.

2推论与推广

推论 2.1. 如果 矩阵 的系数都是非负整数, 而且任意行和, 任意列和都是某 . 则存在一系列置换矩阵 使得 .

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

推论 2.2. 对原定理, 可要求线性组合中只出现 个置换矩阵.

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

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