Birkhoff–von Neumann 定理
Birkhoff–von Neumann 定理是概率论和组合数学中的重要结论. 该定理说明了任意双随机矩阵总在置换矩阵的凸包中, 即, 一个任意行和是 , 任意列和也是 的非负方阵, 总是一些置换矩阵的非负系数线性组合. 因此, 也将所有 阶双随机矩阵构成的集合称 Birkhoff 多胞体, 记作 .
1叙述与证明
定理 1.1 (Birkhoff–von Neumann). 阶双随机矩阵集是 阶置换矩阵的凸包, 即
证明. 首先注意到 , 因为置换矩阵每行每列恰一个元素为 , 其余皆 . 而 显然在凸组合下封闭, 因此 的凸包含于 . 下面证明另一边, 对一个双随机矩阵 , 我们需要寻找一系列置换矩阵 , 使得 , 其中诸 皆为正实数且总和为 .
为此, 我们需证明这样一个引理, 对任意双随机矩阵 , 总存在置换矩阵 , 若矩阵元 则 . 该引理的证明只需使用 Hall 定理, 现在构造二部图 , 顶点集 两部分为 所有的行 和 所有的列 . 对于边集 , 如果 的行 和列 相交的矩阵元大于 , 则连边 , 否则不连边.
我们只需证明 符合 Hall 定理的条件, 这样 Hall 定理的结果, 中一个完美匹配存在, 翻译为矩阵语言就是说我们引理所需的那置换矩阵存在. 也就是说, 我们要检查, 任选 行 , 这 行中存在至少 列 , 每列与这 行相交的 个矩阵元中至少一个为正. 假若不是这样, 那么这 行中非零的列至多只有 列, 这导致这些列和的和, 至少是这些列与 行相交的元素和 , 由于双随机矩阵行和为 , 也就有 . 但是双随机矩阵列和为 , 不超过 列的列和总量也不会超过 , 不可能大于等于 , 至此推出矛盾, 从而 Hall 定理的条件得以验证, 引理得证.
2推论与推广
推论 2.1. 如果 矩阵 的系数都是非负整数, 而且任意行和, 任意列和都是某 . 则存在一系列置换矩阵 使得 .
推论 2.2. 对原定理, 可要求线性组合中只出现 个置换矩阵.
原定理证明过程中用完美匹配来寻找 Birkhoff 分解 (一个符合原定理条件的线性组合) 的算法, 称 Birkhoff 算法, 是标准的贪心算法. 实际上使用该算法就能保证得到一个 的线性组合 (当然 是平凡的上界因为只有这么多矩阵元), 这在 1960 年由 Joshnson, Dulmage and Mendelsohn 证明. 由维数限制, 这个界也是紧的, 就是说对处在一般位置的双随机矩阵, 确实需要如此多个置换矩阵. 由于完美匹配只需多项式时间 (例如使用 Ford–Fulkerson 算法计算最大流) 就能找到, 因此 Birkhoff 算法也只需要多项式时间, 然而找到最小线性组合, 也就是找一个置换矩阵数量最小的组合却是 NP-难的.