LU Factorization of Discrete Random Matrices

技术摘要：离散随机矩阵的 LU 分解

问题陈述
本文研究了离散随机矩阵 $M_n(\xi)$ 是“强非奇异”的概率，其中矩阵项是从离散随机变量 $\xi$ 中独立采样的。如果一个矩阵的所有主子矩阵（leading principal submatrices）都是非奇异的，则该矩阵被定义为强非奇异。这一性质等价于存在不进行选主元（pivoting）的 LU 分解。作者分析了该问题的两个主要方面：

1. 存在性： 这种分解存在的概率（即矩阵是强非奇异的）。
2. 稳定性： 在有限精度下，该分解在数值上是稳定的概率，其受增长因子 $\text{growth}(A) = \max\{\|L\|_{\max}, \|U\|_{\max}\} / \|A\|_{\max}$ 控制。
   这项工作架起了数值线性代数（特别是高斯消元法的稳定性）与离散随机矩阵奇异性组合数学研究之间的桥梁。

方法论
作者采用了一种结合了概率分析、组合计数和算法枚举的多维度方法：

• 概率界限： 分析根据矩阵维度 $n$（小规模、中等规模和大规模）进行分层。
  • 对于 小规模 $n$，使用了简单的归纳法和联合界限（union bounds）。
  • 对于 中等规模 $n$，作者借鉴了 Komlós [10] 关于随机矩阵可逆性的技术。他们利用 Littlewood-Offord 型不等式（特别是 Rogozin 不等式）通过分析随机变量线性组合的碰撞概率，来限制奇异主子式的概率。
  • 对于 大规模 $n$，作者利用了 Jain, Sah, 和 Sawhney [8] 以及 Bourgain, Vu, 和 Wood [2] 关于离散随机矩阵最小奇异值的最新结果。他们通过一个新引理（引理 2.7）将增长因子与主子式的最小奇异值的倒数联系起来。
• 反集中分析（Anti-Concentration Analysis）： 为了在最大项概率 $|\xi|_\infty \to 0$ 时推导出紧致的渐近界限，作者分析了独立随机变量之和的碰撞概率。他们利用 Freiman 同构引理和凸性论证来界定 $2 \times 2$ 和 $3 \times 3$ 子式的奇异概率，并应用 Elkes-Szabó 关于半代数簇（semi-algebraic varieties）定理来处理更高维度的情形。
• 精确枚举： 针对特定的二元矩阵情况（$\xi \sim \text{Ber}(p)$），作者开发了一种精确计数算法。该算法通过识别行和列置换（及转置）下的矩阵等价类来缩小搜索空间。它利用了：
  • 图同构： 将二元矩阵映射为二部图。
  • 规范形式： 使用一维 Weisfeiler-Leman (1-WL) 算法（颜色细化）以及个体化细化搜索树（类似于 nauty 和 Traces）来计算规范代表。
  • 自同构剪枝： 使用稳定链（stabilizer chains）和群论计算在搜索树中对对称分支进行剪枝。

主要贡献与结果

1. 有界增长的常数概率：
   作者证明，对于任何具有有限支撑集且 $|\xi|_\infty < 1$ 的离散随机变量 $\xi$，存在一个常数概率使得 $M_n(\xi)$ 的增长因子被 $n^{5/2+\delta}$ 控制（对于任何 $\delta > 0$，见定理 1.1）。因此，该矩阵以常数概率是强非奇异的（推论 1.2）。作者指出，虽然 $5/2$ 这个指数可能不是紧致的（实验证据表明是 $3/2$），但它确立了离散矩阵存在稳定 LU 分解的存在性。

2. 紧致渐近下界：
   论文为当 $|\xi|_\infty \to 0$ 时强非奇异性的概率提供了一个紧致的渐近下界。具体而言，对于项被 $p$ 限制的矩阵 $M_n(p)$，其强非奇异性的概率至少为 $1 - \frac{5}{3}p - O(p^{1+\alpha})$（定理 1.3）。系数 $5/3$ 被证明是紧致的，可以通过特定的几何级数分布实现。这一结果精炼了对奇异性概率随最大项概率缩放关系的理解。

3. 二元矩阵的精确计数：
   作者将已知的强非奇异二元矩阵序列（OEIS A125587）从维度 $n=6$ 扩展到了 $n=9$。他们提供了对于所有 $n \le 9$ 的具有恰好 $k$ 个非零项的此类矩阵的精确计数 $N_{n,k}$。

   • $N_7 \approx 1.33 \times 10^{13}$
   • $N_8 \approx 3.39 \times 10^{17}$
   • $N_9 \approx 3.66 \times 10^{22}$
     这些计算需要大量的计算资源：评估维度达 $8 \times 8$ 的规范等价类需要 30.5 天，而计算 $9 \times 9$ 的扩展部分又额外需要 7.2 天。

4. 大维度的改进上界：
   利用 $n=9$ 的精确计数，作者推导出了更大维度（$n > 9$）下强非奇异性概率的改进上界。对于维度 $n=30$ 的均匀随机二元矩阵（$p=1/2$），他们确立了一个约为 $1.45\%$ 的上界，这比之前的隐式界限更紧凑，尽管他们承认证明紧致下界仍然是一个困难的开放问题。

意义与主张
该论文声称，这是首次针对一般离散随机矩阵进行的关于高斯消元法的平均情况分析，该分析既确立了 LU 分解的存在性，又确立了增长因子的多项式界限（以常数概率出现）。通过将高斯消元法的数值稳定性（增长因子）与离散矩阵的奇异性问题联系起来，这项工作统一了两个此前相互独立的研究领域。

作者明确指出，他们关于增长因子 $n^{5/2+\delta}$ 的界限可能不是紧致的，暗示真实的指数可能是 $3/2$，但其结果足以证明指数级增长是罕见的（或者说，多项式级增长以常数概率发生）。此外，论文强调了在二元情形下建立有效的强非奇异性概率下界是非常困难的，这使得对于 $n \to \infty$ 时该概率是否超过 $0.5\%$ 的问题仍是一个开放问题（开放问题 1.5）。精确枚举结果为测试理论预测和离散环境下的平滑分析（smoothed analysis）提供了新的基准。