双随机矩阵的 Birkhoff–von Neumann 分解

把行当作工作人员、列当作任务，一条正边说明某人仍欠该任务一段服务时间。匹配让每个人和每项任务恰出现一次；沿匹配找最小剩余时间，就知道这一整份排班可以连续运行多久。最先用完的边归零，下一轮换一份匹配继续安排。

为什么每轮总能找到完美匹配？不变量是残余矩阵非负，且每行、每列和都等于同一个 $\rho >0$。对任意行集合 $S$，其全部质量为 $\rho |S|$，只能流向正支撑邻居 $N(S)$；这些列的总容纳量至多为 $\rho |N(S)|$。所以 $|S|\le |N(S)|$，满足Hall 条件公理库Hall 婚配定理Hall's marriage theorem有限二分图存在饱和一侧的匹配，当且仅当每个该侧顶点子集的邻集至少同样大。。

扣除一份匹配时，每行每列都恰减去 $\alpha$，因此共同边缘和变成 $\rho -\alpha$，不变量保留。至少一条匹配边恰好归零，正支撑严格缩小；有限次之后质量用尽。这个证明同时解释存在性、进度与终止，不需要先枚举所有 $n!$ 个置换。

一份四人四任务计划 ​

取

行、列和均为一。第一次选对角匹配 ${\pi }_0=(0,1,2,3)$，最小边权为 $1/2$。扣除后，四个对角元同时归零，每行每列剩余质量为 $1/2$。

第二次选循环移位匹配 ${\pi }_1=(1,2,3,0)$，沿这些位置的值均为 $1/3$，所以输出权重 $1/3$。余下矩阵为

最后选 ${\pi }_2=(2,3,0,1)$，扣去 $1/6$，残余归零。于是

例如第三行第一列只在最后一份匹配中出现，所以重构为 $1/6$；第四行第一列只在第二份中出现，所以为 $1/3$。逐项检查比只看权重和等于一更强，能发现置换下标方向写反的问题。

若一天分为六个等长时段，就安排三段对角匹配、两段移位一格匹配、一段移位两格匹配。每个时段都是真正的一对一分配，而长期比例恰好等于原分数表。

不要混淆绝对权重与归一化权重 ​

第一轮后也可以把残余除以 $1/2$，得到另一张双随机矩阵。但此时第二轮的相对权重为 $(1/3)/(1/2)=2/3$；回到原时间轴还要乘上剩余质量 $1/2$，绝对权重才是 $1/3$。如果把每轮归一化后得到的权重直接相加，可能超过一。

本页采用不归一化残余的版本，始终显示当前 $\rho$，正是为了让“这一轮从原计划拿走多少”保持同一种单位。

输入条件各自负责什么 ​

只有行和一而列和不等于一的随机矩阵不一定能这样分解。例子 $\left(\begin{array}{cc}1& 0\\ 1& 0\end{array}\right)$ 两行都占用第一列，正支撑没有完美匹配；任何置换矩阵凸组合的列和仍为一，已足以证明不可能。

若有禁止配对，用零元表达即可，算法永远只走正支撑，不会引入原来为零的位置。矩阵条目为有理数时，可以用精确分数表示权重；浮点输入则要说明何时把一个接近零的数当作零，并检查剩余行列和，不宜随意截断后仍声称逐项精确重构。

若初始有 $s$ 个正元，每个非最终步骤至少消去一个正元，而最后一份正质量残余至少需要 $n$ 个正元，所以扣减次数至多 $s-n+1\le n^2-n+1$。这是一份容易从执行过程验证的界，不声称输出的置换数最少。

每轮可以用Hopcroft–Karp公理库Hopcroft–Karp 算法Hopcroft-Karp algorithm按阶段同时增广一族顶点不交的最短增广路，以包含孤立点读取成本的 O(V+E√V) 时间求二分图最大匹配。在正支撑上求完美匹配，成本 $O(E\sqrt{n})$，其中 $E$ 为本轮正边数。因 $\rho >0$ 时每行都有正元，$E\ge n$，故顶点初始化的 $O(n)$ 项已被这个界吸收。再扫描匹配上的 $n$ 条边求最小值并扣减。以最多 $r$ 轮、初始 $s$ 条正边作粗略上界，算术操作量为 $O(n^2+rs\sqrt{n})$，稠密最坏可写成 $O(n^{9/2})$；有理数的位成本和输出存储另计。核验脚本实际实现分层增广匹配，没有用枚举全部置换来冒充这个复杂度。

分解不重新优化一项费用。若原分数矩阵已经是某个线性指派目标的最优解，任何正权重分量也必须同优：否则它们的加权平均不可能等于最优值。匈牙利算法公理库匈牙利算法Hungarian algorithm通过对偶标号和增广结构求解赋权二分图完美匹配的算法。则从费用矩阵直接寻找一份最优指派，目标与“把给定计划实现成排班”不同。

该分解还可用于交换机调度：每个时间片选择一份输入端口到输出端口的一对一连接，权重决定运行比例。实际系统若另有限制切换次数、连续时段长度或时延，便增加了新的优化目标，不能由凸分解的存在性直接保证。