Hoffman–Wielandt谱匹配平方和界

两份正规矩阵各有一组正交谱坐标。旧方向与新方向的重叠平方形成一张表，每行和每列都为一。矩阵的总平方差恰好等于这张表对所有可能谱距离的加权平均。

双随机权重可以拆成若干完整的一一对应。平均值既然等于已知的矩阵误差，其中至少一份完整对应的费用不能比平均值更大。这一步把“每个点附近都有点”升级为“所有点能同时无冲突地配好”。

Bauer–Fike定理理路Bauer–Fike 谱扰动定理Bauer–Fike theorem · Bauer-Fike theorem在可对角化假设下，以特征向量基的条件数控制全部新谱点，分清谱包围、配对和缺陷矩阵的边界。对可对角化矩阵给单向谱包围，并允许另一个矩阵不正规；本页则用两边的正规性控制完整匹配的总平方误差。输入条件、范数和配对量词都不同。

两个谱基不一致时，平方和界可以严格 ​

令

两组升序谱是 $(0,2)$、$(1,3)$，所以按序误差平方和为 $1^2+1^2=2$。而

$B$ 的正交特征基是 $(1,1{)}^T/\sqrt{2}$ 与 $(1,-1{)}^T/\sqrt{2}$，相对于 $A$ 的坐标基，重叠平方表为

谱距离成本矩阵是 $C=\left(\begin{array}{cc}1& 9\\ 1& 1\end{array}\right)$。两份置换的费用分别为 $2$ 与 $10$，加权平均恰为 $6$；因此挑出费用 $2$ 的配对。谱值接近并不要求两矩阵拥有相同谱方向，方向变化消耗了右边的一部分预算。

若改成 $B_0=\mathrm{diag}(1,3)$，与 $A$ 共用同序谱基，则两边都等于 $2$，说明常数一不可统一缩小。

复谱按实部排序会破坏一个本来很近的配对 ​

取

两者都是正规对角矩阵。沿矩阵原对角位置配对，每项只水平移动 $1/5$，故总平方差为 $2/25=\Vert A-B{\Vert }_F^2$。若把两组谱各自按实部升序排，第一对变成 $-1/10+i$ 与 $-1/10-i$，第二对也上下相距 $2$；费用变为 $8$。错误来自配对规则，不是正规性或定理常数。

本例只有两个置换，直接比较 $2/25$ 和 $8$ 就找到了最优匹配。一般可令 $c_{ij}=|{\lambda }_i-{\mu }_j{|}^2$，使用匈牙利算法理路匈牙利算法Hungarian algorithm通过对偶标号和增广结构求解赋权二分图完美匹配的算法。求最小费用指派；不能逐行贪心选最近点，因为两行可能抢同一列。

只保证一边正规仍然不够 ​

取

$A$ 实对称，谱为 $-1,1$；$B$ 的谱为 $0,0$，且 $B{B}^{\ast }=\mathrm{diag}(1,0)\ne \mathrm{diag}(0,1)=B^{\ast }B$。任何配对的谱平方和都是 $2$，矩阵平方差却只有 $1$。所以仅检查参考矩阵正规，不能使用本页常数一的结论。即使近似特征值都能落进某些范数圆盘，也不能据此补出这个平方和界。

从谱展开到双随机分解的完整证明 ​

由正规矩阵谱定理理路有限维谱定理Finite-dimensional spectral theorem有限维复正规算子存在正交规范特征基；实数情形对应自伴算子。，写

其中 $U,V,W$ 都酉，$\mathrm{\Lambda }=\mathrm{diag}({\lambda }_i)$、$M=\mathrm{diag}({\mu }_j)$。Frobenius范数对左右酉变换不变，所以

$W$ 的每行、每列都是单位向量，故 $P_{ij}=|w_{ij}{|}^2$ 非负且行列和均为一。由Birkhoff–von Neumann分解理路双随机矩阵的 Birkhoff–von Neumann 分解Birkhoff–von Neumann theorem · Doubly stochastic matrix decomposition在正支撑图中反复寻找完美匹配并扣除最小边权，把任意双随机矩阵精确拆成置换矩阵的凸组合。，$P=\sum _s{t}_s{P}_{{\pi }_s}$，其中 $t_s\ge 0$、$\sum _s{t}_s=1$。代回得

至少有一个正权重项不超过这个平均值，证明正规情形。双随机分解的实际构造是反复从正支撑找完美匹配并扣去最小权重；其存在性和终止证明由所链接的条目提供，不需要在谱问题里另造一种匹配算法。

还需证明实谱的升序配对最便宜。若 $a\le b$、$c\le d$，交叉配对与同序配对之差为

逐一消去任意置换中的逆序对，成本不增加，最终得到同序配对。重值只会使某些交换费用为零，不影响结论。这完成了Hermitian版本，不能仅凭“实数能排序”省去最优性这一步。

一个总预算能排除什么 ​

设已认证 $\Vert A-B{\Vert }_F\le \eta$，并采用定理保证的匹配。对任何 $t>0$，若有 $k$ 项谱误差至少为 $t$，就有 $k{t}^2\le {\eta }^2$，因而 $k\le \lfloor {\eta }^2/t^2\rfloor$。例如 $\eta =1/5$，不可能有三项误差都至少为 $3/25$，因为 $3(3/25{)}^2=27/625>1/25$。这个排除使用总误差预算，逐项套相同的上界得不到同样信息。

对于Hermitian输入，Weyl界理路Hermitian 特征值的有序扰动界Weyl eigenvalue perturbation bound · Weyl monotonicity theorem从变分原理证明 Hermitian 特征值按序配对的绝对误差界，并在同一三阶扰动中核验尺度与谱隙。已给每项至多 $\Vert A-B{\Vert }_2$。将它们平方相加只得到 $n\Vert A-B{\Vert }_2^2$，而本页给 $\Vert A-B{\Vert }_F^2$，可能明显更小。两者可同时报告：前者针对最大单项，后者针对总能量，不能擅自把正规复谱结论的右边换成二范数平方。

计算误差也必须进入同一范数预算 ​

若 $A$ Hermitian，算法交付经过核验的酉矩阵 $\hat{Q}$、实对角矩阵 $\hat{\mathrm{\Lambda }}$，令 $\tilde{A}=\hat{Q}\hat{\mathrm{\Lambda }}{\hat{Q}}^{\ast }$。对准确重构残差的上界 $\Vert A-\tilde{A}{\Vert }_F\le \eta$，本页就给按序谱误差的Euclidean范数不超过 $\eta$。

如果只知道浮点算出的残差 $\hat{R}$ 与真残差相差至多 ${\eta }_R$，可用 $\eta =\Vert \hat{R}{\Vert }_F+{\eta }_R$。若 $\hat{Q}$ 仅近似酉，则应先认证正交化及其对重构的改动，或直接认证 $\tilde{A}$ 的真实谱；未经证明，打印的对角数不一定是重构矩阵的特征值。输入本身还有误差时，应把已认证的输入Frobenius误差加到这个预算中。