内积的界与配对的序

柯西不等式与排序不等式

老教材「不等式选讲」里有两条不必画图象的不等式。一条管住内积：两列数逐位相乘再求和，所得的平方压不过两列各自平方和之积。另一条管住配对方式：两列数配对相乘再求和，同序配对给出最大值，反序配对给出最小值。它们与本系列前几页的路数不同，既不求分界点也不读区间，用到的全部工具是「平方非负」与「交换两项」。

1 · 内积与模长之积

柯西不等式（Cauchy–Schwarz inequality）比较的是两个数量：两列数的内积的平方，与两列数各自平方和之积。

定理 1.1 对任意实数 $a_1, \dots, a_n$ 与 $b_1, \dots, b_n$ ，

\left(\sum_{i=1}^{n} a_i b_i\right)^2 \le \left(\sum_{i=1}^{n} a_i^2\right)\left(\sum_{i=1}^{n} b_i^2\right)

等号成立当且仅当两列数成比例：存在实数 $\lambda$ 使 $b_i = \lambda a_i$ 对每个 $i$ 成立，或者 $a_i$ 全为零。

两侧之差有闭式，称拉格朗日恒等式（Lagrange's identity）：

\left(\sum_{i=1}^{n} a_i^2\right)\left(\sum_{i=1}^{n} b_i^2\right) - \left(\sum_{i=1}^{n} a_i b_i\right)^2 = \sum_{1 \le i < j \le n} (a_i b_j - a_j b_i)^2

右端是若干平方之和，非负，定理由此成立；它为零当且仅当每个二阶行列式 $a_i b_j - a_j b_i$ 都为零，也就是两列数成比例。这条恒等式把定理与取等条件一并给出，代价是要先把它写对——右端的求和跑遍全部下标对，共 $n(n-1)/2$ 项。以下两节各给一条不必先知道这条恒等式的证明。

2 · 判别式给出的证明

平方和的抛物线

把两列数搭成一个关于实变量 $t$ 的函数：

f(t) = \sum_{i=1}^{n} (a_i t + b_i)^2 = \left(\sum a_i^2\right) t^2 + 2\left(\sum a_i b_i\right) t + \sum b_i^2

证明 $f$ 是若干实数的平方之和，对每个实数 $t$ 都满足 $f(t) \ge 0$ 。设 $\sum a_i^2 > 0$ （否则 $a_i$ 全为零，原不等式两侧同为零）。此时 $f$ 是开口向上的二次函数且没有取到负值，抛物线至多与 $t$ 轴相切，判别式非正：

\Delta = 4\left(\sum a_i b_i\right)^2 - 4\left(\sum a_i^2\right)\left(\sum b_i^2\right) \le 0

两端除以 $4$ 并移项即得定理 1.1。等号成立要求 $\Delta = 0$ ，即存在 $t_0$ 使 $f(t_0) = 0$ ；平方和为零迫使每一项为零， $a_i t_0 + b_i = 0$ 对每个 $i$ 成立，两列数成比例。∎

判别式在本节的用法与解一元二次不等式时相反：那页用 $\Delta$ 数抛物线与 x 轴的交点个数，此处用它断言抛物线穿不过 $t$ 轴。两种用法背后是同一个量。抛物线的顶点值 $\sum b_i^2 - (\sum a_i b_i)^2 / \sum a_i^2$ 也有几何含义，见 §3。

浮点下这条判别式并不可靠。取 $b_i = k a_i$ （三个分量在 $-1$ 到 $1$ 之间随机、 $k$ 在 $-2$ 到 $2$ 之间随机），共线在数学上是精确的， $\Delta$ 应当恰为零；实测一百万组里只有 335231 组的 $\Delta$ 双精度下真的等于零，331932 组为正、332837 组为负，正的一侧最大到 $4.3 \times 10^{-14}$ 。判别式为正意味着 $f$ 有两个不同实根，也就是某处的平方和为负。core/cauchy.ts 判「是否取等」因而不看这个量，改看拉格朗日恒等式的右端：它是平方和，浮点下也永不为负，同一批数据里它有 69.9% 不为零，但相对于 $(\sum a_i^2)(\sum b_i^2)$ 最大只有 $3.2 \times 10^{-32}$ ，按相对阈值判共线在二十万组里零漏判。

3 · 余弦的绝对值与取等条件

$n$ 取 $2$ 或 $3$ 时，两列数就是平面或空间里的两个向量 $\vec a$ 与 $\vec b$ 。内积另有一个与坐标无关的表达式：

\vec a \cdot \vec b = |\vec a| \, |\vec b| \cos\theta

这条路是否循环论证，取决于 $\cos\theta$ 从哪里来。在平面与空间里余弦定理独立于内积成立， $\vec a \cdot \vec b = |\vec a| |\vec b| \cos\theta$ 是余弦定理的改写，论证不循环。到了一般的 $n$ 维空间，情形恰恰反过来：那里的「夹角」根本是被定义出来的，定义 $\cos\theta = \frac{\vec a \cdot \vec b}{|\vec a| |\vec b|}$ 之所以合法，靠的就是柯西不等式保证这个比值落在 $-1$ 与 $1$ 之间。§2 的判别式法不依赖任何几何，在这个意义上比向量法更基本。

图 3-1 · 两个向量的夹角、内积的界，以及判别式法里那条关于

t

的抛物线。可调两向量的长度与夹角，观察比值

|\vec a \cdot \vec b| / (|\vec a| |\vec b|)

与

|\cos\theta|

同步变化；切到第二栏可看夹角归零时抛物线如何与

t

轴相切。

抛物线的顶点值在向量语言里另有一个说法。 $f(t)$ 是向量 $t\vec a + \vec b$ 的长度平方，最小值在 $\vec b$ 到 $\vec a$ 所在直线的垂足处取到，等于该距离的平方。共线时距离为零，顶点落在 $t$ 轴上，这与 §2 的相切说的是同一件事。

4 · 三角不等式与柯西的关系

(|\vec a| + |\vec b|)^2 - |\vec a + \vec b|^2 = 2\left(|\vec a| \, |\vec b| - \vec a \cdot \vec b\right)

右端非负这件事，就是柯西不等式。三角不等式在 $n$ 维、乃至把平方换成 $p$ 次幂之后仍然成立，一般形式称闵可夫斯基不等式（Minkowski inequality）， $p = 2$ 的情形即上式。

5 · 顺序和与逆序和

大配大与小配小

设两列实数都已按升序排好： $a_1 \le a_2 \le \dots \le a_n$ 与 $b_1 \le b_2 \le \dots \le b_n$ 。把 $b$ 重排后与 $a$ 逐位相乘再求和，得到的值随重排方式变化。排序不等式（rearrangement inequality）给出这族值的两端。

定理 5.1 对下标的任一排列 $\sigma$ ，

\sum_{i=1}^{n} a_i b_{n+1-i} \le \sum_{i=1}^{n} a_i b_{\sigma(i)} \le \sum_{i=1}^{n} a_i b_i

左端称逆序和，右端称顺序和，中间称乱序和。

证明设 $\sigma$ 不是恒等排列，则存在一对下标 $i < j$ 使 $\sigma(i) > \sigma(j)$ ，于是 $a_i \le a_j$ 而 $b_{\sigma(i)} \ge b_{\sigma(j)}$ 。把 $\sigma$ 在这两个位置上的取值互换，配对和的增量是

(a_i - a_j)\left(b_{\sigma(j)} - b_{\sigma(i)}\right) \ge 0

两个因子同为非正，乘积非负，故这次互换不减小配对和。互换消掉了这一对逆序，逆序对总数严格下降，至多 $n(n-1)/2$ 步后到达恒等排列，其间配对和从未减少，所以顺序和是最大值。把两处不等号方向反过来，同样的论证给出逆序和是最小值。∎

这套「假设最优解与目标解不同，找出一处分歧，做一次局部交换，证明交换后不变差」的模式叫交换论证（exchange argument），它是贪心算法正确性证明的通用骨架：区间调度、最小生成树、哈夫曼编码的正确性都按这个模板写。排序不等式是它在纯数学里最短的一个实例，交换的对象只是两个下标。

图 5-1 · 两列数的配对方式与配对和，直方图给出全部排列的和值分布。交叉的连线即逆序对，可反复点「换回一个逆序对」观察配对和单调上升，直至连线不再交叉。

交换论证担保的只是「每消掉一个逆序对，配对和不减」，它并不担保「逆序对更少的配对，和一定更大」。把 $a = (1, 2, \dots, 8)$ 与 $b = (2, 3, 5, 7, 11, 13, 17, 19)$ 的全部 40320 个配对枚举一遍，按逆序对个数分成 29 档：各档和值的最大值确实随逆序对数单调不增，从 455 一路降到 238；但相邻两档的取值区间在 28 对里有 26 对重叠，逆序对数为 $2$ 的一档取到过 452，而逆序对数为 $1$ 的一档最低只有 451。40320 个和里互不相同的只有 218 个，两端各只由唯一一个排列取到。这轮枚举在 node v26 上耗时 15 ms， $n$ 增到 $9$ 就是 215 ms，core/cauchy.ts 的 permutations 只用于 $n \le 8$ 的核对，页面里的直方图最多画到 $n = 6$ 。

6 · 切比雪夫和不等式

两列数同序时，逐位乘积的和与两列各自的和之间也有比较。

n \sum_{i=1}^{n} a_i b_i \ge \left(\sum_{i=1}^{n} a_i\right)\left(\sum_{i=1}^{n} b_i\right)

这条称切比雪夫和不等式（Chebyshev's sum inequality）。证明只需把右端拆开： $(\sum a_i)(\sum b_i)$ 等于 $n$ 个循环移位配对和之和，第 $k$ 个是 $\sum_i a_i b_{i+k}$ （下标按模 $n$ 取），每一个都是乱序和，都不超过顺序和 $\sum a_i b_i$ ， $n$ 项相加即得。两列反序时每个循环移位和都不小于逆序和，不等号翻转。

两边除以 $n^2$ 换一种读法：乘积的平均不小于平均的乘积。前提是两列同序，这一条不能省——反序时结论整个反过来，而两列毫无单调关系时两侧的大小不定。

同一条恒等式在 §5 的枚举里露过面：40320 个配对和的平均值恰为 346.5，等于 $(\sum a_i)(\sum b_i) / 8$ 。core/cauchy.test.ts 用这两条互相独立的路径互为参照量，一条走循环移位，一条走全排列的平均。

7 · 平均值不等式链

对正数 $x_1, \dots, x_n$ ，四个平均排成一条链：

\frac{n}{\sum 1/x_i} \le \sqrt[n]{\prod x_i} \le \frac{\sum x_i}{n} \le \sqrt{\frac{\sum x_i^2}{n}}

依次是调和平均（harmonic mean）、几何平均、算术平均与二次平均（quadratic mean，也叫均方根）。基本不等式：算术平均与几何平均只处理了 $n = 2$ 时中间那一段。

链条的两端由柯西不等式直接给出。取 $b_i = 1$ ，定理 1.1 成为 $(\sum x_i)^2 \le n \sum x_i^2$ ，除以 $n^2$ 开方即算术平均不超过二次平均。取 $a_i = \sqrt{x_i}$ 与 $b_i = 1/\sqrt{x_i}$ ，定理 1.1 成为 $n^2 \le (\sum x_i)(\sum 1/x_i)$ ，整理即调和平均不超过算术平均。中间那一段涉及几何平均，柯西不等式给不出，需要 $n$ 元的算术几何平均不等式。

四个平均都是幂平均 $M_p = \left(\frac{1}{n}\sum x_i^p\right)^{1/p}$ 在 $p = -1, 0, 1, 2$ 处的取值，其中 $p = 0$ 取的是极限，等于几何平均。幂平均关于 $p$ 单调不减，这条更强的命题把整条链收成一句话，也是 core/cauchy.test.ts 里检验四个平均的参照量：四个定义式各算各的，再与通用的 $M_p$ 逐一对照。

8 · 参考文献

Cauchy–Schwarz inequality. Wikipedia. 不等式的多种证明、取等条件与在各类内积空间中的推广。https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality
Lagrange's identity. Wikipedia. 两侧之差的闭式与它同叉积的关系。https://en.wikipedia.org/wiki/Lagrange%27s_identity
Rearrangement inequality. Wikipedia. 顺序和与逆序和的界，以及交换论证的标准写法。https://en.wikipedia.org/wiki/Rearrangement_inequality
Chebyshev's sum inequality. Wikipedia. 同序两列的和与积的比较，循环移位证明。https://en.wikipedia.org/wiki/Chebyshev%27s_sum_inequality
Minkowski inequality. Wikipedia. 三角不等式在 $p$ 次幂下的一般形式。https://en.wikipedia.org/wiki/Minkowski_inequality
Power mean inequality. Wikipedia. 幂平均关于指数的单调性，四个平均只是其中四点。https://en.wikipedia.org/wiki/Power_mean_inequality