🔢 mathematics

LU Factorization of Discrete Random Matrices

This paper establishes that discrete random matrices with finite support and bounded entries have a constant probability of being strongly non-singular (admitting an LU factorization) with a controlled growth factor, while also providing tight asymptotic lower bounds for this probability and improved upper bounds for the Bernoulli case through exact enumeration up to $n=9$ .

Original authors: Samuel Orellana Mateo, John Urschel, Nicholas West

Published 2026-08-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Samuel Orellana Mateo, John Urschel, Nicholas West

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant puzzle where every piece is a number, and the only way to solve it is to break the whole picture down into two simpler, triangular shapes. This is the world of linear algebra, specifically a method called Gaussian elimination. Think of it like taking a complex recipe and trying to separate the ingredients into two distinct piles: one pile for the "base" and one for the "top." If the recipe works perfectly, you can split it cleanly. But sometimes, a crucial ingredient is missing or zero, and the whole separation fails. In the real world, computers do this math all the time to run everything from video games to weather forecasts. However, if the numbers get messy or the "split" goes wrong, the computer might get confused, make huge errors, or just crash.

The big question mathematicians have been asking is: "How often does this clean split actually work?" If you fill a grid with random numbers, will the computer be able to break it down, or will it get stuck? This paper dives into that mystery, but with a twist: instead of using smooth, continuous numbers (like any number on a ruler), they look at grids filled with discrete, "stepped" numbers (like dice rolls or binary switches). They want to know the odds that a random grid of these numbers is "strongly non-singular"—a fancy way of saying it's sturdy enough to be split into those two triangular shapes without needing to shuffle the rows around. They also care about how "stable" the process is, meaning the numbers don't explode to gigantic sizes during the calculation, which would cause the computer to lose its mind.

The Paper's Big Discovery: A Lucky Break for Random Grids

In this study, Samuel Orellana Mateo, John Urschel, and Nicholas West act like detectives investigating the stability of these random number grids. They found that if you build a grid using a random variable (like rolling a die or flipping a coin) that doesn't get stuck on just one number, there is a constant, reliable chance that the grid will be perfectly splitable. It's not a guaranteed win every time, but it's not a rare fluke either; it happens often enough that you can count on it.

Even better, they proved that when this split happens, the numbers involved in the calculation don't grow out of control. They showed that the "growth factor"—a measure of how big the numbers get during the process—is bounded by a manageable size, roughly proportional to $n^{5/2}$ (where $n$ is the size of the grid). While they suspect the true limit might be even lower (around $n^{3/2}$ ), their proof guarantees that the numbers stay within a safe, polynomial limit, meaning the computer won't crash from overflow.

The "Zero" Problem and the 5/3 Rule

One of the most interesting parts of the paper is figuring out exactly why these grids sometimes fail. The main culprit is usually a "zero" or a "collision" where two different paths lead to the same result, causing a division by zero. The authors calculated exactly how the probability of failure changes as the numbers get smaller and more likely to be zero.

They discovered a precise mathematical rule for this. If the chance of getting a specific number is $p$ (which is small), the probability that the grid fails to be splitable is roughly $5/3$ times $p$ . In other words, if you have a 1% chance of picking a specific "bad" number, your chance of the whole grid failing is about 1.67%. This isn't just a guess; they proved this rate is "tight," meaning you can't make the formula any simpler or more accurate without changing the fundamental nature of the problem. They even showed a specific example where a grid built from a geometric progression of numbers hits this $5/3$ limit almost immediately, confirming their theory with experimental data.

Counting the Impossible: The Binary Grid Challenge

The authors didn't just stop at theory; they got their hands dirty with actual counting. They focused on the simplest case: grids filled only with 0s and 1s (like a giant light switch board). For small grids, you can just write a computer program to check every single possibility. But as the grid gets bigger, the number of possibilities explodes. A $9 \times 9$ grid has $2^{81}$ possible combinations—that's more than the number of atoms in the solar system.

To solve this, the team invented a clever algorithm that treats the grids like social networks. They realized that many grids are just "twins" of each other, just with rows and columns swapped. By grouping these twins together and only checking one "representative" from each group, they drastically reduced the work. Using a supercomputer cluster with 100 CPU threads and 500 GB of RAM, they spent over a month crunching numbers to find the exact count of "strongly non-singular" binary grids up to size $9 \times 9$ .

Their results are staggering. For a $9 \times 9$ grid, there are exactly 36,646,054,311,185,413,881,216 ways to arrange the 0s and 1s so that the grid can be split cleanly. This is a massive number, but it's still a tiny fraction of all possible grids.

Looking Ahead: The 30x30 Mystery

With their exact counts for small grids, the authors used a technique called extrapolation to guess what happens with much larger grids, like $30 \times 30$ . They found that for a random $30 \times 30$ grid of 0s and 1s, the chance of it being splitable is very small—less than 1.45%. Their experiments suggest the real number is even lower, around 0.94%.

While they have a very good upper bound (a "ceiling" on the probability), they admit that proving a solid "floor" (a guaranteed minimum probability) is much harder. They leave this as an open challenge for future mathematicians: Can we prove that for a random $n \times n$ grid where 0s and 1s are equally likely, the chance of success stays above 0.5% even as the grid gets infinitely large? For now, the answer remains a mystery, but the authors have paved the way with their new counting techniques and tight probability bounds.

Technical Summary: LU Factorization of Discrete Random Matrices

Problem Statement
This paper investigates the probability that a discrete random matrix $M_n(\xi)$ , with entries sampled independently from a discrete random variable $\xi$ , is "strongly non-singular." A matrix is defined as strongly non-singular if all its leading principal submatrices are non-singular. This property is equivalent to the existence of an LU factorization without pivoting. The authors analyze two primary aspects of this problem:

Existence: The probability that such a factorization exists (i.e., the matrix is strongly non-singular).
Stability: The probability that the factorization is numerically stable in finite precision, governed by the growth factor $\text{growth}(A) = \max\{\|L\|_{\max}, \|U\|_{\max}\} / \|A\|_{\max}$ .

The work bridges the fields of numerical linear algebra (specifically the stability of Gaussian elimination) and the combinatorial study of the singularity of discrete random matrices.

Methodology
The authors employ a multi-faceted approach combining probabilistic analysis, combinatorial counting, and algorithmic enumeration:

Probabilistic Bounds: The analysis is stratified by matrix dimension $n$ $n$ (small, moderate, and large).
- For small $n$ , simple induction and union bounds are used.
- For moderate $n$ , the authors adapt techniques from Komlós [10] regarding the invertibility of random matrices. They utilize Littlewood-Offord type inequalities (specifically Rogozin's inequality) to bound the probability of singular leading principal minors by analyzing the collision probability of linear combinations of random variables.
- For large $n$ , the authors leverage recent results on the smallest singular values of discrete random matrices by Jain, Sah, and Sawhney [8] and Bourgain, Vu, and Wood [2]. They relate these singular value bounds to the growth factor via a new lemma (Lemma 2.7) connecting the growth factor to the inverse of the smallest singular values of leading submatrices.
Anti-Concentration Analysis: To derive tight asymptotic bounds as the maximum entry probability $|\xi|_\infty \to 0$ , the authors analyze the collision probability of sums of independent random variables. They utilize the Frieman isomorphism lemma and convexity arguments to bound the probability of singular $2 \times 2$ and $3 \times 3$ minors, applying the Elkes-Szabó theorem for semi-algebraic varieties to handle higher dimensions.
Exact Enumeration: For the specific case of binary matrices ( $\xi \sim \text{Ber}(p)$ $ξ \sim Ber (p)$ ), the authors develop an exact counting algorithm. This algorithm reduces the search space by identifying equivalence classes of matrices under row and column permutations (and transposition). It utilizes:
- Graph Isomorphism: Mapping binary matrices to bipartite graphs.
- Canonical Forms: Using the 1-dimensional Weisfeiler-Leman (1-WL) algorithm (color refinement) and individualization-refinement search trees (similar to nauty and Traces) to compute canonical representatives.
- Automorphism Pruning: Pruning symmetric branches in the search tree using stabilizer chains and group-theoretic computations.

Key Contributions and Results

Constant Probability of Bounded Growth:
The authors prove that for any discrete random variable $\xi$ with finite support and $|\xi|_\infty < 1$ , there exists a constant probability that $M_n(\xi)$ has a growth factor bounded by $n^{5/2+\delta}$ for any $\delta > 0$ (Theorem 1.1). Consequently, the matrix is strongly non-singular with constant probability (Corollary 1.2). The authors note that while the exponent $5/2$ is likely not tight (experimental evidence suggests $3/2$ ), it establishes the existence of stable LU factorizations for discrete matrices with constant probability.
Tight Asymptotic Lower Bound:
The paper provides a tight asymptotic lower bound for the probability of strong non-singularity as $|\xi|_\infty \to 0$ . Specifically, for a matrix $M_n(p)$ with entries bounded by $p$ , the probability of being strongly non-singular is at least $1 - \frac{5}{3}p - O(p^{1+\alpha})$ (Theorem 1.3). The coefficient $5/3$ is shown to be tight, achieved by a specific geometric progression distribution. This result refines the understanding of how singularity probability scales with the maximum entry probability.
Exact Counts for Binary Matrices:
The authors extend the known sequence of strongly non-singular binary matrices (OEIS A125587) from dimension $n=6$ to $n=9$ . They provide exact counts $N_{n,k}$ for the number of such matrices with exactly $k$ non-zero entries for all $n \le 9$ .
- $N_7 \approx 1.33 \times 10^{13}$
- $N_8 \approx 3.39 \times 10^{17}$
- $N_9 \approx 3.66 \times 10^{22}$
  These computations required significant computational resources: evaluating canonical equivalence classes up to dimension $8 \times 8$ required 30.5 days, and computing the $9 \times 9$ extensions required an additional 7.2 days.
Improved Upper Bounds for Large Dimensions:
Using the exact counts for $n=9$ , the authors derive improved upper bounds for the probability of strong non-singularity for larger dimensions ( $n > 9$ ). For a uniformly random binary matrix ( $p=1/2$ ) of dimension $n=30$ , they establish an upper bound of approximately $1.45\%$ , which is tighter than previous implicit bounds, though they acknowledge that proving tight lower bounds remains a difficult open problem.

Significance and Claims
The paper claims to provide the first average-case analysis of Gaussian elimination for general discrete random matrices that establishes both the existence of an LU factorization and a polynomial bound on the growth factor with constant probability. By connecting the numerical stability of Gaussian elimination (growth factors) with the singularity problem of discrete matrices, the work unifies two previously disjoint areas of research.

The authors explicitly state that their bound of $n^{5/2+\delta}$ for the growth factor is likely not tight, suggesting the true exponent is $3/2$ , but their result is sufficient to prove that exponential growth is rare (or rather, that polynomial growth occurs with constant probability). Furthermore, the paper highlights the difficulty of establishing effective lower bounds for the probability of strong non-singularity in the binary case, leaving the question of whether this probability exceeds $0.5\%$ for $n \to \infty$ as an open problem (Open Problem 1.5). The exact enumeration results provide a new benchmark for testing theoretical predictions and smoothed analysis in discrete settings.

The Paper's Big Discovery: A Lucky Break for Random Grids

The "Zero" Problem and the 5/3 Rule

Counting the Impossible: The Binary Grid Challenge

Looking Ahead: The 30x30 Mystery

More like this