Sharp singularity rates for symmetric random sign matrices

Source and verification

This article explains family 239 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

A random symmetric sign matrix can be singular because two rows coincide. Family 239 claims that this elementary obstruction determines the sharp exponential rate, both for fair signs and for any fixed nontrivial bias. Symmetry makes the matching upper bound much harder than the lower bound.

🏷️ Preliminaries: a symmetric random matrix

Let $A_n$ be real symmetric. Its entries on and above the diagonal are independent signs, equal to $+1$ with probability $p$ and $-1$ otherwise. Entries below the diagonal are their reflected copies.

Singularity means that $A_{n}x=0$ for some nonzero real vector $x$, equivalently that the determinant vanishes. The rows are not independent: row $i$ and row $j$ share the entry $A_{ij}$. A row-by-row argument valid for an iid nonsymmetric matrix therefore does not transfer directly.

An exponential-rate statement identifies ${\lim }_n\mathbb{P}(A_n\text{ singular}{)}^{1/n}$. It permits polynomial and other subexponential corrections.

🏷️ The two claimed rates

Sharp singularity exponents

For fair signs, the first companion claims

$$\begin{array}{c}\mathbb{P}(\det A_n=0)\\ ={\left(\frac{1}{2}+o(1)\right)}^n.\end{array}$$

(OpenAI, 2026)

For each fixed $p\in (0,1)\setminus \{1/2\}$, the biased companion claims

$$\begin{array}{c}\mathbb{P}(\det A_n=0)\\ =(p^2+(1-p{)}^2+o(1){)}^n.\end{array}$$

(OpenAI, 2026b)

The parameter is fixed as dimension grows. These statements do not give a uniform estimate when $p$ tends to zero or one with $n$, nor an exact leading polynomial prefactor.

🏷️ An exact two-row lower bound

Require rows one and two to agree. For each $k\ge 3$, the independent pair $A_{1k},A_{2k}$ agrees with probability

$$s=p^2+(1-p{)}^2.$$

The remaining conditions are $A_{11}=A_{12}=A_{22}$, whose probability is $p^3+(1-p{)}^3$. These events use disjoint independent upper-triangular entries. Hence

$$\begin{array}{c}\mathbb{P}(\text{row }1=\text{row }2)\\ =(p^3+(1-p{)}^3)s^{n-2}.\end{array}$$

This event forces singularity, proving a lower exponential rate at least $s$. When $p=1/2$, the expression is exactly $2^{-n}$.

The rate is symmetric under $p\leftrightarrow 1-p$, as it must be: multiplying the whole matrix by $-1$ does not change singularity. Since $s=1/2+2(p-1/2{)}^2$, bias increases this obstruction’s exponential base.

An opposite-row event has off-diagonal base $2p(1-p)$, strictly smaller than $s$ for fixed biased signs. Thus equal rows, rather than opposite rows, furnish the displayed biased lower rate.

🏷️ The upper-bound obstruction: quadratic concentration

If a principal block $B$ is nonsingular, write the next extension as

$$A=\left(\begin{array}{cc}B& v\\ v^{\mathsf{T}}& a\end{array}\right).$$

A block determinant calculation gives

$$\det A=\det B(a-v^{\mathsf{T}}{B}^{-1}v).$$

Conditional on $B$, singularity becomes a quadratic concentration event for the independent new column $v$ and diagonal sign $a$. The inverse matrix can have highly structured coefficients, so an ordinary variance estimate for this quadratic form cannot establish the sharp exponentially small probability.

The nonsingularity of $B$ is also essential. An argument must account for matrices with singular principal blocks rather than simply conditioning them away.

🏷️ Structure of the fair-sign proof

The fair-sign manuscript organizes arithmetic information from inverses of principal minors into layers and a potential measuring retained structure. Static estimates control how many sign columns can preserve a specified lattice constraint.

A nonsingular symmetric matrix admits a sequence of nonsingular principal minors enlarged by one or two coordinates. Two-coordinate extensions require both columns to satisfy a gate. The proof uses that extra cost instead of treating a width-two extension as an ordinary independent single-column step.

A long initial portion of the sequence suppresses high-layer tails, while a shorter terminal window limits accumulated local errors. Conditional exponential-moment estimates then show that unusually persistent structure is too costly. This is the part needed to match the simple two-row lower exponent.

🏷️ Additional issues for biased signs

A particular sign column can have probability as large as $\max (p,1-p{)}^{n-1}$, which is too large to recover the claimed base $s$. The biased proof separates nearly sparse kernel directions from the remaining ones.

After normalizing a kernel vector at a largest coordinate, the latter case can be transformed to a symmetric binary-matrix problem with entry probabilities in $\{p,1-p\}$ and a low-rank mean correction. Structural exceptions require two rare extensions. Outside them, a suitable deletion exposes a column retaining nearly its full entropy.

The entropy and structural estimates must be combined under the same conditioning. Counting possible columns without their unequal probabilities would lose the improvement required by bias. The elementary lower bound illustrates the correct answer; it does not remove this upper-bound work.

🏷️ Key steps and proof outlines

The useful reduction is to count possible completing columns after exposing a principal minor. In the biased case, that count must be combined with the probability of each original sign column under exactly the same conditioning. The arithmetic estimates below are identified as inputs; the probabilistic reductions explain how they deliver the exponential rate (OpenAI, 2026a; OpenAI, 2026b).

Removing large corank without losing the exponent

A symmetric rank-$r$ matrix has a nonsingular principal $r$-minor: write it as $XS{X}^{\mathsf{T}}$ with $X$ of full column rank and $S$ invertible, and choose $r$ independent rows of $X$. Once that minor and its cross block are exposed, keeping the same rank forces every entry in the remaining symmetric block by the Schur complement. For fair binary entries this gives

$$\mathbb{P}(\mathrm{corank}{B}_m\ge k)\le \sum _{j=k}^m\left(\genfrac{}{}{0ex}{}{m}{j}\right)2^{-j(j+1)/2}.$$

Thus corank above $m^{3/5}$ costs $2^{-\Omega (m^{6/5})}$. For smaller corank $k$, choose $k-1$ coordinate functionals independent on the kernel and flip those diagonal entries. Pairing the new kernel equation with the old kernel shows that its selected coordinates must vanish. The new kernel is exactly the old kernel intersected with these $k-1$ coordinate hyperplanes, hence has dimension one.

Specifying the flipped coordinates recovers the original matrix. There are only $2^{O(m^{3/5}\log m)}$ possibilities. Under bias, the probability ratio additionally costs at most $((1-p)/p{)}^{m^{3/5}}$ after reducing to $p<1/2$; this too is subexponential. It therefore suffices to control corank one.

The fair-sign column count

Condition on the first sign row. First multiply the whole matrix by its first diagonal sign, then apply the diagonal congruence with entries $1,A_{11}{A}_{12},\dots ,A_{11}{A}_{1n}$. This makes the first row all ones; the remaining signs stay independent and fair. Its Schur complement is $-2B_{n-1}$ for a fair symmetric binary matrix. This proves equality of the two singularity probabilities, with the dimension reduced by one.

For a corank-one binary matrix, delete a largest coordinate of a nonzero kernel vector $v$. The remaining minor $B$ is nonsingular because the adjugate is a nonzero multiple of $v{v}^{\mathsf{T}}$. Its completing column $z$ satisfies

$$B^{-1}z=-v_{-i}/v_i,z^{\mathsf{T}}{B}^{-1}z=a\in \{0,1\}.$$

Hence $\Vert B^{-1}z{\Vert }_{\infty }\le 1$. Define $\mathcal{S}(B)$ by these two conditions for binary $z$, and set it empty when $B$ is singular. Conditional on a fixed $(N-1)$-minor, each pair $(z,a)$ has probability $2^{-N}$ and $a$ is forced by $z$. Union over the deleted index gives

$$\mathbb{P}(\mathrm{corank}{B}_N=1)\le N{2}^{-N}\mathbb{E}|\mathcal{S}(B_{N-1})|.$$

The substantive target is now $\mathbb{E}|\mathcal{S}(B_{N-1})|\le 2^{o(N)}$.

Why a short terminal window is needed

The source assigns a potential $0\le \Psi (B)\le 1$ to arithmetic constraints on possible inverse columns. Its static counting estimate is $|\mathcal{S}(B)|\le 2^{N(\Psi (B)+o(1))}$ outside an event of probability $2^{-\omega (N)}$. Its local estimate bounds the conditional exponential moment of the potential after enlarging a nonsingular minor by one or two coordinates.

A two-coordinate enlargement has a gate: both cross columns belong to $\mathcal{S}(C)$ for the old minor $C$. They are conditionally independent, so this gate costs $2^{-2m}|\mathcal{S}(C){|}^2$ at dimension $m$. Keeping this factor is essential; treating the enlargement as one ordinary step loses the estimate.

The path is chosen backwards from a realized matrix, but it is not then used as a conditioning event. Instead, cover the possibilities by all fixed index paths, at cost $2^{o(N)}$, and expose each fixed path forwards. Fresh cross columns then retain their stated laws, while future gates and nonsingularity remain indicators.

Write $\ell =\log \log N$. A long initial path of order $N^{3/5}$ eliminates large arithmetic tails. Only a terminal window of order ${\ell }^{24}$ accumulates the local potential error ${\ell }^{-60}$, making the total error $o(1)$. In that window either some potential is at most a fixed $ϵ$, or persistence of larger potential forces many costly constraint-retention events. The first case contributes at most $2^{N(ϵ+o(1))}$; the second is superexponentially small after the prescribed tail estimates. First let $N\to \infty$, then $ϵ\downarrow 0$. This proves the required moment and column bounds. Iterating the local error across the entire long path would not give this conclusion.

Bias requires two distinct strict margins

Assume $p<1/2$, put $b=1-p$, $Q=p^2+b^2$, and define

$$a=-{\log }_{2}b,d=-{\log }_{2}Q,h=-p{\log }_{2}p-b{\log }_{2}b.$$

Then $2a>d$ because $b^2<Q$, and $h>d$ by strict concavity of the logarithm. The proof uses the first margin for exceptional minors and the second for typical completing columns.

First remove normalized off-anchor kernel tails close to sparse vectors. A net argument reduces their equations to independent tests on rows outside the chosen support. If two coefficients are large, an interval small enough cannot contain adjacent vertices of their two-sign square; its probability is at most $Q$. If all tail coefficients are small, Berry–Esseen gives an even smaller interval probability. The independent tests contribute $Q^{n-o(n)}$, and choosing the net tolerances before the support fraction makes its entropy loss arbitrarily small. The mean matrix is handled by separately approximating the coordinate sum, so its rank-one part does not magnify the net error.

For the remaining tails, many coordinates have magnitude at least $c/\sqrt{n}$. A concentration bound shows that all but a small fraction of original rows have close to $pn$ positive entries. Choose the deletion index among both sets. After conditioning on a fixed anchor row, the transformed bits remain independent, have success probabilities in $\{p,b\}$, and their mean matrix has rank at most two.

The source’s column theorem says, for fixed $L_0$ and small $e_0>0$, that the admissible set with $\Vert B^{-1}z{\Vert }_2\le L_0\sqrt{N}$ has at most $2^{e_{0}N}$ elements except with probability $2^{-N(2a-10e_0)}$. Each column compatible with the chosen original row count has probability at most $2^{-N(h-C_{p}w-o(1))}$, where $w$ is the row-count tolerance. Thus the two contributions have exponents $2a-10e_0$ and $h-e_0-C_{p}w-o(1)$. Choose $e_0,w$ small so both exceed $d$. Fixing candidate indices before conditioning and finally taking their $n^2$ union bound preserves independence. The already removed sparse-tail event supplies the limiting rate $Q$, matching the two-row lower bound.

See Also

• Family 219 studies local eigenvalue statistics, a different question from exact singularity.
• Family 238 illustrates why global dependence cannot be read from individual-coordinate marginals.

🏷️ Manuscripts and verification scope

• The sharp exponential rate of singularity for symmetric Bernoulli matrices — pinned manuscript and companion source.
• The sharp singularity rate for biased symmetric sign matrices — pinned manuscript and companion source.

No family scope page was present at lean/docs/239.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. The sharp exponential rate of singularity for symmetric Bernoulli matrices.

🐻  OpenAI 2026b. The sharp singularity rate for biased symmetric sign matrices.