Sharp singularity rates for symmetric random sign matrices

← All digests

Family 239 · Probability and statistical mechanics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Fill the upper half of a square matrix with independent random signs, then reflect it across the diagonal. How likely is the resulting symmetric matrix to have determinant zero?

For matrices with continuously distributed independent inputs, an exact algebraic dependency usually has probability zero. Discrete signs are different. Two rows can agree exactly, immediately forcing singularity. More complicated dependencies are also possible, and there are enormously many ways to choose their coefficients.

Family 239 contains two manuscripts claiming the sharp exponential rate of singularity for symmetric sign matrices. In the unbiased case it is $2^{-n+o(n)}$. With a fixed probability $p$ of a positive sign, the exponential base becomes $p^2+(1-p)^2$.

The point is that all possible dependencies together have the same exponential scale as a simple equal-row event. The claim does not determine a multiplicative prefactor or assert that almost every singular matrix has equal rows.

2. Background and essential definitions

The random matrix model

Let $A_n^{(p)}$ be a real symmetric $n$-by-$n$ matrix. The entries $A_{ij}$ for $i\leq j$, including the diagonal, are independent and satisfy

$$\mathbb P(A_{ij}=1)=p, \qquad \mathbb P(A_{ij}=-1)=1-p.$$

Set $A_{ji}=A_{ij}$ below the diagonal. Thus there are $n(n+1)/2$ independent signs, not $n^2$. The parameter $p\in(0,1)$ is fixed as $n$ grows.

A matrix is singular when $\det A=0$. Equivalently, there is a nonzero vector $v$ with $Av=0$, or its columns are linearly dependent. The space of such vectors is the kernel, and its dimension is the corank. Corank one means the matrix has rank $n-1$.

A principal submatrix keeps the same subset of row and column indices. This preserves symmetry and is the natural object when exposing a symmetric matrix one coordinate at a time.

What an exponential rate says

If a probability $s_n$ satisfies

$$s_n=(q+o(1))^n,$$

then $s_n^{1/n}\to q$, or equivalently $\log s_n=n\log q+o(n)$. Factors such as $n^2$, or even $e^{\sqrt n}$, are invisible at this precision.

Consequently, $s_n=2^{-n+o(n)}$ is much sharper than merely $s_n\leq e^{-cn}$ for an unspecified positive $c$, but weaker than a formula $s_n\sim Cn^2 2^{-n}$. The family establishes the first kind of sharpness, according to its stated theorems.

The elementary obstruction

For a specified pair of rows, agreement outside their two shared coordinates has probability

$$Q^{n-2},\qquad Q=p^2+(1-p)^2.$$

The three entries in the remaining symmetric corner must all agree, which has probability $p^3+(1-p)^3$. Therefore the exact probability that this pair agrees is

$$\bigl(p^3+(1-p)^3\bigr)Q^{n-2}.$$

This event forces singularity and already has exponential base $Q$. When $p=1/2$, it equals $2^{-n}$. The difficult direction is showing that other dependencies do not produce a larger exponential base.

3. Development history and previous partial results

Komlós proved that square matrices with independent uniform zero-one entries are nonsingular with probability tending to one. For independent signs, Kahn, Komlós and Szemerédi later obtained an exponential upper bound, and Tikhomirov identified the sharp rate $(1/2+o(1))^n$. These models have independent rows. Exponential independent-entry bound, Tikhomirov’s sharp rate.

For nonuniform independent discrete entries, Jain, Sah and Sawhney obtained sharp singularity asymptotics; biased signs have the same collision-probability base $p^2+(1-p)^2$ appearing here. The biased manuscript also cites a September 2026 preprint of Hu, Song and Wu claiming the full prefactor asymptotic for independent uniform signs. These independent-entry results are predecessors, not symmetric-matrix theorems. Nonuniform discrete matrices, 2026 independent-sign preprint.

Symmetry changes the problem because revealing a row simultaneously reveals entries in future rows. Costello, Tao and Vu proved asymptotic nonsingularity for symmetric Bernoulli matrices, developing quadratic Littlewood–Offord estimates. These estimate how concentrated a random quadratic expression can be, an analogue of anti-concentration for sums of independent variables. Symmetric nonsingularity.

Nguyen improved the probability bound to arbitrarily high polynomial decay, and Vershynin obtained stretched-exponential bounds within a broader invertibility theory. Further quantitative progress led to the exponential bound $e^{-cn}$ of Campos, Jenssen, Michelen and Sahasrabudhe. That was already a major resolution of the question whether symmetric singularity is exponentially unlikely. Nguyen’s work, Vershynin’s work, exponential symmetric bound.

The remaining gap addressed by this family is the exact leading exponential rate, first for uniform signs and then for every fixed nonuniform bias. The second paper explicitly builds on arithmetic tools and principal-minor identities from the first.

4. What the new manuscripts claim

M1: unbiased symmetric signs

For independent uniform signs on and above the diagonal, M1 claims

$$\mathbb P(\det A_n^{(1/2)}=0) =\left(\frac12+o(1)\right)^n =2^{-n+o(n)}.$$

The lower bound comes from equal rows. The asserted upper bound controls every real linear dependency, including those whose kernel vectors have no simple sparse pattern.

The manuscript also uses an exact distributional reduction: the singularity probability of the symmetric sign matrix of size $n$ equals that of a symmetric matrix of independent unbiased bits on and above the diagonal of size $n-1$. This reduction exploits sign symmetry and a Schur complement; it is not a general identity for arbitrary biased signs.

M2: a fixed nonuniform bias

For every fixed $p\in(0,1)\setminus\{1/2\}$, M2 claims

$$\lim_{n\to\infty} \mathbb P(\det A_n^{(p)}=0)^{1/n} =p^2+(1-p)^2.$$

Together with M1, this covers every fixed $p\in(0,1)$. The error terms may depend on $p$; the two statements do not provide uniform control when the bias changes with dimension.

For example, at $p=1/4$, the base is $5/8$, larger than the unbiased base $1/2$. The theorem says singularity is exponentially more likely at that fixed bias, while still tending to zero. Negating the whole matrix exchanges $p$ and $1-p$, consistent with the symmetry of the formula.

Both the diagonal distribution and the use of real singularity are part of the model. The theorem does not silently cover zero diagonals, arbitrary deterministic diagonals or singularity over a finite field.

5. Why the advance matters

Importance: 4/5. If correct, these claims complete the leading exponential picture for a central discrete symmetric random-matrix model and its fixed-bias extension.

The rate is strikingly simple: it is the probability that two independent entries agree. Yet proving that this elementary obstruction gives the correct exponential scale requires ruling out a vast collection of more complicated linear relations under row–column dependence.

The extension to biased signs adds a real difficulty. Under uniform signs, every candidate column has the same probability. Under bias, some columns are much more likely than others, so merely counting how many columns can cause singularity is not enough. The second manuscript combines arithmetic structure with entropy to account for their unequal weights.

The rating recognizes this sharp quantitative advance and its methods, while distinguishing it from the already-established exponential decay theorem and from the still finer problem of a full asymptotic prefactor.

6. The main idea

Turn singularity into a count of possible columns

For the unbiased model, multiply rows and matching columns by selected signs so that the first row and column become all ones. Taking the Schur complement at the first diagonal entry leaves minus twice a symmetric bit matrix. Independence and unbiasedness survive in the remaining upper triangle.

The next reduction handles corank. A small number of diagonal flips can turn a matrix of small positive corank into one of corank one, with only a subexponential counting loss. Matrices of large corank have a much smaller probability and are treated separately.

For a corank-one matrix, choose a largest coordinate of a kernel vector and delete its row and column. The remaining principal matrix $B$ is nonsingular. If $z$ is the deleted bit column and $a$ its diagonal bit, the Schur-complement identity requires

$$a=z^{\mathsf T}B^{-1}z.$$

The largest-coordinate choice also gives $\|B^{-1}z\|_\infty\leq1$. Thus the argument counts bit vectors $z$ satisfying both restrictions. M1’s central target is that their expected number is only $2^{o(n)}$; each column and diagonal choice has probability approximately $2^{-n}$.

Record the arithmetic of the inverse

Because $B$ has integer entries, the group

$$G_B=\mathbb Z^m/B\mathbb Z^m$$

is finite when $B$ is nonsingular. It records integer vectors modulo the lattice generated by the columns of $B$. The inverse matrix defines a pairing

$$([x],[y])\longmapsto x^{\mathsf T}B^{-1}y\pmod{\mathbb Z}.$$

The allowed columns have restricted self-pairings. Decomposing the finite group into cyclic factors organizes the denominators that can occur. Lattice geometry and simultaneous bounds for rational subspaces then constrain how many cube vertices can satisfy these arithmetic requirements.

The manuscript tracks an arithmetic potential along paths of nonsingular principal minors, adding one or two coordinates at a time. A large population of admissible columns forces expensive structural behavior along these paths. Bounds on those events supply the expected column estimate. The geometry-of-numbers tools include the Reverse Minkowski Theorem of Regev and Stephens-Davidowitz. That theorem.

Bias requires probability as well as counting

In M2, the sign normalization leaves independent bit entries with probabilities drawn from $\{p,1-p\}$, conditional on the anchor row. One cannot treat them as uniform bits.

The argument separately handles kernel vectors close to sparse ones. For the others, it selects a useful deleted coordinate whose original sign column has close to the typical fraction of positive entries. Such columns have probabilities governed by binary entropy

$$h(p)=-p\log_2p-(1-p)\log_2(1-p).$$

For nonuniform $p$, this exceeds $-\log_2(p^2+(1-p)^2)$. That strict gap leaves room to combine a small count of compatible columns with their probability cost. Exceptional arithmetic structure is controlled through two rare extensions, or a two-column extension, rather than one overly generous maximum-column-probability bound.

The biased argument therefore adapts the first paper’s arithmetic framework while adding a mechanism that preserves the desired collision-probability rate.

7. Scope, limitations, and open questions

The results concern independent signs in the upper triangle, reflected symmetrically, with the diagonal sampled by the same rule. Other symmetric discrete distributions, sparsity patterns and diagonal conventions require separate statements.

The bias is fixed. The theorem does not cover $p=p_n\to0$ or $1$, where near-constant matrices introduce different scales, nor does it supply a uniform crossover as $p\to1/2$.

An exponential rate does not identify a prefactor. It also does not prove that equal or opposite rows account for almost all singular matrices. Establishing a full asymptotic formula would require distinguishing mechanisms at a finer scale than $e^{o(n)}$.

Finally, exact singularity differs from being numerically close to singular. The least singular value measures near-degeneracy and numerical stability; these two theorems do not provide its full small-value distribution. Sharper singularity asymptotics, near-singularity estimates and extensions to other dependent ensembles remain further directions.

8. Sources and further reading

M1 gives the unbiased theorem, sign-to-bit reduction and arithmetic principal-minor framework. M2 gives the fixed-bias extension and explains the entropy gain needed for unequal column probabilities.

For the previous symmetric milestone, see Campos, Jenssen, Michelen and Sahasrabudhe’s exponential bound. Tikhomirov’s independent-entry theorem and Jain, Sah and Sawhney’s nonuniform discrete-matrix paper clarify which earlier conclusions relied on independent rows.

Source manuscripts

• M1. OpenAI, The sharp exponential rate of singularity for symmetric Bernoulli matrices (October 3, 2026).
• M2. OpenAI, The sharp singularity rate for biased symmetric sign matrices (October 4, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.