部分主元法下随机矩阵的增长因子有多大？

增长因子衡量消元过程中的元素膨胀

高斯消元把矩阵 A 分解为下三角矩阵 L 和上三角矩阵 U。在有限精度下，累积的舍入误差由增长因子 growth(A) = max(‖L‖_max, ‖U‖_max)/‖A‖_max 控制，其中 ‖·‖_max 是元素绝对值的最大值。如果 growth(A) 不太大，LU 分解就是稳定的；大致需要 log(n·growth(A)) 位精度。

部分主元法是 Python 中 numpy.linalg.solve 以及 Matlab 和 Julia 中反斜杠命令所用的贪心行交换规则。在每一步消元中，当前第一列中绝对值最大的元素被移到第一行。该规则下的最坏情况增长因子可以是指数级的：一个加倍论证给出上界 2^{n−1}，而 Wilkinson 在 1961 年构造出在每个维度都达到该值的矩阵。令人困惑的是，这种膨胀在实践中很少被观察到。

Trefethen 猜想确立了 √n 这一目标

Trefethen 和 Schreiber 对高斯消元做了经验性的平均情况分析，Edelman 的数值实验表明，部分主元法下高斯矩阵的增长因子按 n^{1/2} 增长。Edelman 评论说，证明这样的结果可能非常困难。Trefethen 在 1995 年国际工业与应用数学大会上以及 1997 年的《Numerical Linear Algebra》一书中提出了该猜想，后来为解决问题悬赏 1000 美元。

在本论文之前，数学进展来自两个方面。Trefethen 声称有一个关于最后一个主元 |U_nn| 的未发表证明，该证明在 14 年后与本手稿同时发布。Huang 和 Tikhomirov 证明，部分主元法下的高斯矩阵以高概率增长至多 n^c，其中 c 是一个很大的未指定常数。Sankar 的光滑分析表明，任何矩阵加上小的高斯扰动 A+εG（其中 ‖A‖_2≤1）在部分主元法下的增长因子以高概率被 (n/ε)^{O(log n)} 界定。

部分主元法使高斯增长保持在 √n 附近

定理 1.4 指出，对每个 α>0，存在常数 C_α 和 n_α，使得当 n≥n_α 时，P[growth(Π(G)) > √n·e^{C_α√(log n)}] < n^{−α}，其中 G 是 n×n 高斯矩阵，Π(·) 是部分主元映射。由于对每个 c>0 都有 e^{√(log n)} = o(n^c)，这蕴含了 Trefethen 的猜想 1.1。

1/2 这个指数是正确的，而不仅仅是一个上界。论文指出 log‖G‖_max = o(log n)，并且根据所引结果，以概率 1−o(1) 有 log‖U‖_max ≥ log(|det(G)|^{1/n}) ≥ (1/2)log n − O(1)。把这个下界与定理 1.4 结合，得到推论 1.5：log growth(Π(G))/log n 依概率收敛到 1/2。因此增长因子确实在次多项式因子范围内是 n^{1/2} 量级，而不是更小。

正交预处理产生的增长大于部分主元法

论文还证明了左乘 Haar 正交矩阵且不使用主元法时矩阵增长因子的上界。定理 1.2 指出，对 A∈GL_n(R) 和 Q∼Haar(O(n))，对所有 δ∈(0,1) 有 P[growth(QA) > 14n^{3/2}√(log(en))/δ] < δ。对于任何非自适应正交预处理器，3/2 这个指数是紧的。

定理 1.3 刻画了不使用主元法时高斯矩阵增长因子的渐近分布：n^{−3/2}growth(G) 依分布收敛到 X∼InvExp(2/(3√π))，即对 x>0 有 Pr[X≤x] = e^{−2/(3√π x)}。在 n=64 时用一百万个样本做的数值实验给出经验分布与逆指数分布之间的 Kolmogorov–Smirnov 距离为 2.8×10^{−3}，表明即使 n 很小，实际收敛也很快。

这一比较之所以重要，是因为正交预处理是部分主元法的一个合理替代方案。论文指出，这种替代方案在应用于高斯矩阵时产生的增长因子比部分主元法预期看到的更大，而且其尾部界按逆多项式衰减，比部分主元法预期的衰减更慢。缩放后的增长因子 n^{−3/2}growth(G) 以概率 n^{−O(1)} 为 Θ(1)，而 n^{−1/2}growth(Π(G)) 以压倒性概率为 n^{o(1)}。

光滑分析把扰动界改进到 n^{O(log log n)}

定理 1.6 把论证扩展到光滑情形。对每个 α>0，存在常数 C_α 和 n_α，使得对所有 n≥n_α、每个满足 ‖A‖_2≤1 的矩阵 A∈R^{n×n} 以及每个 ε∈(0,1)，都有 P[growth(Π(A+εG)) > n^{C_α}ε^{−2/log 2·log log n}] < n^{−α}，其中 G 是高斯矩阵，Π(·) 是部分主元映射。

这表明多项式小的扰动产生 n^{O(log log n)} 的增长。论文指出正确行为很可能是 n^{O(1)}，因此这是对 Sankar 长期存在的 n^{O(log n)} 界的显著改进。证明通过把 A+εG 替换为 A/ε+G，将部分主元法论证推广到一般均值情形，这保持了单位方差但允许可能非常大的均值；额外的损失通过一个累积额外项的因子 f_K(r) 来追踪。

证明控制 Schur 补的截断逆

主要技术工具是关于 Haar 正交矩阵子矩阵逆的一个界。引理 2.1 指出，对 Q∼Haar(O(n))、大小为 m 的固定子集 S,T⊂[n] 以及满足 k≤m 的固定向量 x,y_1,…,y_k∈S^{m−1}(R)，对所有 t>0 有 P[max_{j∈[k]}|y_j^T(Q_{S,T})^{−1}x| > t] ≤ (6/t)√((n−m+1)log(ek)/m)。反复应用该引理即可证明定理 1.2。

对于部分主元法的结果，论文证明了六个关于奇异值和高斯矩阵的技术引理，然后控制前 t×t 主元子矩阵的截断逆 Σ_r(T_t) = Σ_{i=1}^{n−k} 1/σ_i(T_t)^2。命题 5.5 表明，当 r=⌈√(log n)⌉ 时，以至少 1−n^{−(α+1)} 的概率有 max_{k<n} Σ_r(Π(G)_{[k],[k]}) ≤ n·e^{C_α√(log n)}。命题 5.1 把截断逆的控制转化为增长界。把两者以指数 α+1 结合即得定理 1.4。

定理 1.4 的证明是通过人机交互完成的。AI 使用声明说，猜想 1.1 的证明始于一个仅由人类完成的关于 U_ij 右下角 o(n) 个元素的证明草图，并通过 AI 交互改进为对所有元素的证明。猜想 1.1 曾被列在 GitHub 仓库 OpenProblemsInNLA 上，被标记为公开、有挑战性且对社区有趣，在本手稿之前一直未解决。

数值结果暗示 Gumbel 波动和可能的收窄

论文报告了超出定理所证明范围的数值实验。对于 n=4^k（k=3,…,7），它计算了 n^{−1/2}growth(Π(G)) 的 7500 个样本。经验密度的尾部衰减很快，并且随着 n 增大似乎有所收窄。论文说证据并不压倒性，但经验上 n^{−1/2}growth(G) 的波动经过适当平移和归一化后似乎类似 Gumbel 分布，这并不太令人意外，因为这类分布常常出现在取大量随机变量最大值的时候。

论文还指出，随着 n 增大，n^{−1/2}growth(G) 的经验密度似乎收窄，留下了 n^{−1/2}growth(G) 收敛到常数的可能性。这些是经验观察，不是已证明的结果，论文明确标记证据并不压倒性。它们值得与定理 1.4（一个严格的高概率上界）以及推论 1.5（一个关于指数的严格依概率收敛陈述）区分开来。

该保证针对高斯矩阵和精确算术增长

定理 1.4 适用于 n×n 高斯矩阵，即元素为独立标准正态随机变量的矩阵，在部分主元映射 Π(·) 下。它是一个渐近陈述：常数 C_α 和 n_α 依赖于 α，界对所有 n≥n_α 成立。该定理没有声称具体的有限 n 阈值，数值图针对的是 n 最大到 4^7=16384。

论文指出的一个微妙之处是，误差分析所需的增长因子是浮点算术下的增长因子，由于舍入误差累积或主元选择变化，它可能与精确算术下的增长因子不同。论文指出，部分主元法的最坏情况增长因子在精确算术和浮点算术下相同，并且高斯矩阵在部分主元法下的增长因子以高概率最多增加一个小常数倍。本论文的结果针对精确算术。

定理 1.6 中的光滑分析结果适用于任何满足 ‖A‖_2≤1 的固定 A∈R^{n×n} 加上 ε 大小的高斯扰动，其中 ε∈(0,1)。它同样是 n 的渐近结果。论文指出正确行为很可能是 n^{O(1)}，因此 n^{O(log log n)} 界是一个改进而非最终答案。定理 1.2 和 1.3 中的正交预处理结果涉及不使用主元法的增长，与部分主元法结果是不同的算法设定，不应被解读为对 growth(Π(G)) 的界。

本文引用的文献