排序不等式及其推广

排序不等式是一个经典的不等式，本身不难理解，很多读者可能在中学阶段就已经了解过它，尤其是准备过数学竞赛的同学。但排序不等式也远不止表面上那么简单：它在矩阵世界中有一个深刻的对应物——冯·诺伊曼迹不等式；它还可以沿着“多序列”、“多矩阵”的方向继续推广。

本文就沿着这条线索，将这些内容串联起来介绍一下。

基本形式[#](https://spaces.ac.cn/archives/11910#%E5%9F%BA%E6%9C%AC%E5%BD%A2%E5%BC%8F)

设有两个从大到小排好序的实数列 a 1≥a 2≥⋯≥a n a 1≥a 2≥⋯≥a n 和 b 1≥b 2≥⋯≥b n b 1≥b 2≥⋯≥b n，注意这里不需要非负约束，τ(1),τ(2),⋯,τ(n)τ(1),τ(2),⋯,τ(n)表示 1,2,⋯,n 1,2,⋯,n 的任意排列，那么成立排序不等式

n∑i=1 a i b n+1−i≤n∑i=1 a i b τ(i)≤n∑i=1 a i b i

∑i=1 n a i b n+1−i≤∑i=1 n a i b τ(i)≤∑i=1 n a i b i(1)

即“倒序积 ≤ 乱序积 ≤ 同序积”。排序不等式的标准证明方式是局部调整法：设 a i≥a j a i≥a j 和 b i≥b j b i≥b j，那么

(a i b i+a j b j)−(a i b j+a j b i)=(a i−a j)(b i−b j)≥0 (a i b i+a j b j)−(a i b j+a j b i)=(a i−a j)(b i−b j)≥0(2)

也就是说，如果序列中有一对不同序的位置，那么将某一边交换后将它变得同序，相应的内积至少不会变差，于是最大值必然在完全同序时取到。对 a 1,a 2,⋯,a n a 1,a 2,⋯,a n 和−b 1,−b 2,⋯,−b n−b 1,−b 2,⋯,−b n 重复相同的流程，便可得到最小值端。 注意排序不等式本身不要求序列非负，但后面我们推广它时，会加上非负约束。值得指出的是，加非负约束并不改变当前的排序不等式的覆盖面，因为任意有限的实数列，都可以通过加一个足够大的常数来变成非负列，并且不改变排序，而两端展开后，就恢复无非负约束的排序不等式。

迹不等式[#](https://spaces.ac.cn/archives/11910#%E8%BF%B9%E4%B8%8D%E7%AD%89%E5%BC%8F)

排序不等式在矩阵中有一个非常重要的对应物：设 A,B A,B 是两个 n×n n×n 的实对称矩阵，λ i(⋅)λ i(⋅)表示从大到小排序的第 i i 个特征值，那么成立不等式

n∑i=1 λ i(A)λ n+1−i(B)≤tr(A B)≤n∑i=1 λ i(A)λ i(B)

∑i=1 n λ i(A)λ n+1−i(B)≤tr(A B)≤∑i=1 n λ i(A)λ i(B)(3)

很显然，A,B A,B 取对角矩阵时，等价于上一节的排序不等式，所以这是它的矩阵推广，称为“冯·诺伊曼迹不等式（Von Neumann's Trace Inequality）”，又称“Fan迹不等式（Ky Fan's Trace Inequality）”，本文统一简称“迹不等式”。 当 A,B A,B 是一般的 n×m n×m 实矩阵时，则成立不等式

|tr(A⊤B)|≤min(n,m)∑i=1 σ i(A)σ i(B)

|tr(A⊤B)|≤∑i=1 min(n,m)σ i(A)σ i(B)(4)

σ i(⋅)σ i(⋅)表示从大到小排序的第 i i 个奇异值。迹不等式在数学、物理中都有很广泛的应用，比如推导Muon优化器，如果我们已知该不等式，可以显著降低证明难度。一般版的不等式，可以通过Jordan–Wielandt对称化技巧构造

˜A=(0 A A⊤0),˜B=(0 B B⊤0)

来转化为对称版，所以我们只需要关注对称版的证明。

正交优化[#](https://spaces.ac.cn/archives/11910#%E6%AD%A3%E4%BA%A4%E4%BC%98%E5%8C%96)

这一节我们证明对称版(3)。不失一般性，可设 A 是对角阵，若否，可将它特征值分解为 U A Λ A U⊤A，然后利用 tr(A B)=tr(U A Λ A U⊤A B U A U⊤A)=tr(Λ A U⊤A B U A)，其中 Λ A 是对角阵，U⊤A B U A 的特征值跟 B 一致。

冯·诺伊曼迹不等式的证明方式有很多，这里我们考虑一个比较别致、更接近冯·诺伊曼原始思想的证明。引入 n×n 的正交矩阵 O，显然我们有

min O tr(A O⊤B O)≤tr(A B)≤max O tr(A O⊤B O)

接下来我们要证明，tr(A O⊤B O)的最大值和最小值，正是我们期望的上下界。先考虑最大值，假设最大值为 tr(A O⊤∗B O∗)，注意对于任意反对称矩阵 S，矩阵指数 e t S 都是正交的，考虑扰动 O∗→O∗e t S，根据 O∗最优的假设，t=0 处导数应当为 0。直接计算得

d d t tr(A(O∗e t S)⊤B(O∗e t S))=tr([A,(O∗e t S)⊤B(O∗e t S)]S)

其中[X,Y]≜X Y−Y X 通常称为对易子，化简过程中还利用了 S 的反对称性。代入 t=0，令它为零，并由 S 的任意性知[A,O⊤∗B O∗]=0，即 A 与 O⊤∗B O∗可交换。相同的论述过程对最小值也成立。

注意 A 是对角阵，进一步假设对角线元素两两不同（若否，总可以将它表示成满足条件的矩阵序列的极限），那么与 A 可交换的矩阵也只有对角阵，所以 O∗必然是 B 的特征矩阵，或者说 O⊤∗B O∗必然是 B 的对角化。于是问题变成了两个矩阵的特征值向量内积的上下界，由排序不等式即可得出。

多个序列[#](https://spaces.ac.cn/archives/11910#%E5%A4%9A%E4%B8%AA%E5%BA%8F%E5%88%97)

一个很自然的问题是：排序不等式可以推广到多个序列吗？我们以三序列为例，设有非负的序列 a 1≥⋯≥a n≥0、b 1≥⋯≥b n≥0 和 c 1≥⋯≥c n≥0，τ(1),⋯,τ(n)和 π(1),⋯,π(n)表示 1,⋯,n 的任意两个排列，那么最大值依然是在同序时取到

n∑i=1 a i b τ(i)c π(i)≤n∑i=1 a i b i c i

证明并不复杂，一行就可以写出来：

n∑i=1 a i b τ(i)c π(i)=n∑k=1(a k−a k+1)k∑i=1 b τ(i)c π(i)≤n∑k=1(a k−a k+1)k∑i=1 b i c i=n∑i=1 a i b i c i

第一个等号是利用分部求和法做恒等变换（设 a n+1=0）；第二个等号是利用分部求和法重新变换回来；关键是不等号≤，它是在 a k≥a k+1 条件下，对∑k i=1 b τ(i)c π(i)用排序不等式，注意到 b i,c i 已经从大到小排序过，所以∑k i=1 b i c i 必然最大，∑k i=1 b τ(i)c π(i)不管怎么重新配对都不可能超过它，从而有这个不等号。

这个证明和结果可以递归地推广到任意多个非负序列。注意非负是必要的，因为“∑k i=1 b τ(i)c π(i)不管怎么重新配对都不可能超过∑k i=1 b i c i”只对非负序列保证成立。

自动均衡[#](https://spaces.ac.cn/archives/11910#%E8%87%AA%E5%8A%A8%E5%9D%87%E8%A1%A1)

然而，最小值侧并无法像最大值侧那样简单推广。

理由也很直观，“同序”是满足传递性的，两个单调递减的非负序列，其Hadamard积依然是单调递减的，这样我们就可以多次复用二元的排序不等式来得到最大值。然而，“倒序”本就是针对两个序列来说的，多个序列我们很难定义什么是“倒序”，一个递增和一个递减的非负序列的Hadamard积，也没有固定的单调性。

不过，我们依然可以从均值不等式来获得一些关于最小值的信号：

n∑i=1 a i b τ(i)c π(i)≥n(n∏i=1 a i b τ(i)c π(i))1/n=n(n∏i=1 a i b i c i)1/n

等号成立的条件是全体 a i b τ(i)c π(i)相等。当然，由于我们只改变了 b,c 的序，所以很难实现全体 a i b τ(i)c π(i)这一条件，但这可以告诉我们一个定性的方向：最小值对应的排序，会尽量使得所有 a i b τ(i)c π(i)均衡。

有经验的同学可能敏锐地意识到，这种离散情形的均衡配对问题求解通常是比较困难的。事实也确实如此，它本质上可以抽象为一个三维轴向指派问题，已知它是NP-Hard的。也就是说，多序列排序不等式的最小值侧不存在一般的解析解，这是问题的本质困难。

多个矩阵[#](https://spaces.ac.cn/archives/11910#%E5%A4%9A%E4%B8%AA%E7%9F%A9%E9%98%B5)

类似地，迹不等式可以推广到多个矩阵吗？考虑三个 n×n 矩阵 A,B,C，我们有

|tr(A B C)|≤n∑i=1 σ i(A)σ i(B)σ i(C)

证明也是类似的

|tr(A B C)|≤n∑i=1 σ i(A)σ i(B C)=n∑k=1(σ k(A)−σ k+1(A))k∑i=1 σ i(B C)≤n∑k=1(σ k(A)−σ k+1(A))k∑i=1 σ i(B)σ i(C)=n∑i=1 σ i(A)σ i(B)σ i(C)

即先用二元的迹不等式放缩一次，然后还是分部求和、放缩、分部求和，其中第二个≤用到了如下不等式

k∑i=1 σ i(B C)≤k∑i=1 σ i(B)σ i(C),k=1,2,⋯,n

这也可以看成是式(4)的一个推广，证明思路就是先将左端转化为迹，然后再用式(4)。具体来说，设 B C 的SVD为 U Σ V⊤，那么

k∑i=1 σ i(B C)=tr(U⊤[:,:k]B C V[:,:k])≤k∑i=1 σ i(U⊤[:,:k]B)σ i(C V[:,:k])≤k∑i=1 σ i(B)σ i(C)

最后一个不等号用了 σ i(X Y)≤σ i(X)σ 1(Y)以及 U[:,:k],V[:,:k]的正交性。同样的归纳可以继续下去，得到任意多个矩阵的版本。

另一推广[#](https://spaces.ac.cn/archives/11910#%E5%8F%A6%E4%B8%80%E6%8E%A8%E5%B9%BF)

式(11)推广了式(4)，那式(3)如何推广呢？设有 n×n 的半正定矩阵 A,B,C，考虑 tr(A B C)，最大值侧是平凡的，即式(11)，最小值侧是否可以类似地写成∑n i=1 λ i(A)λ τ(i)(B)λ π(i)(C)的形式呢？

答案是否定的。半正定矩阵的特征值一定非负，所以∑n i=1 λ i(A)λ τ(i)(B)λ π(i)(C)也一定非负，但是三个半正定矩阵之积的迹却可以是负的！因此这种形式的最小值必不成立。问题出在哪呢？注意到对于半正定矩阵 A,B，成立

tr(A B)=tr((A 1/2 B 1/2)⊤(A 1/2 B 1/2))=‖A 1/2 B 1/2‖2 F≥0

这就保证了非负性。由此可以猜测，三矩阵的合理推广也许是‖A 1/2 B 1/2 C 1/2‖2 F，而非更简单的 tr(A B C)。但很遗憾，这个式子虽然看起来更加“正确”，但可以举例证明它的最小值并不一定等于某个∑n i=1 λ i(A)λ τ(i)(B)λ π(i)(C)，所以它也无法作为式(3)的最小值侧的推广。

不过，‖A 1/2 B 1/2 C 1/2‖2 F 确实也有一些与多序列排序不等式最小值端类似的性质，比如成立

‖A 1/2 B 1/2 C 1/2‖2 F=n∑i=1 σ 2 i(A 1/2 B 1/2 C 1/2)≥n(n∏i=1 σ i(A 1/2 B 1/2 C 1/2))2/n=n[det(A 1/2 B 1/2 C 1/2)]2/n=n[det(A)det(B)det(C)]1/n

等号在 A 1/2 B 1/2 C 1/2 全体奇异值相等时成立。这也就意味着，‖A 1/2 B 1/2 C 1/2‖2 F 取最小值时，A 1/2 B 1/2 C 1/2 的全体奇异值会趋于均匀分布，“自动均衡”再次出现！

文章小结[#](https://spaces.ac.cn/archives/11910#%E6%96%87%E7%AB%A0%E5%B0%8F%E7%BB%93)

本文从排序不等式出发，沿着“矩阵化”和“多序列化”两条线索，梳理了它的主要推广。

_转载到请包括本文地址：[https://spaces.ac.cn/archives/11910](https://spaces.ac.cn/archives/11910 "排序不等式及其推广")_

_更详细的转载事宜请参考：_[《科学空间FAQ》](https://spaces.ac.cn/archives/6508#%E6%96%87%E7%AB%A0%E5%A6%82%E4%BD%95%E8%BD%AC%E8%BD%BD/%E5%BC%95%E7%94%A8 "《科学空间FAQ》")