clopen.solutions

The quadratic correlation matrix need not have full nonnegative rank

Recorded by the registry's curators from GitHub; the authors did not submit it here.

Sidney Holden

For subsets $a,b\subseteq[n]$, let $C_n(a,b)=(1-|a\cap b|)^2$, with every
entry prescribed. We construct nonnegative rational factors proving
$$\operatorname{rank}_+(C_n)\le 2^{n-1}+n+\binom n2+\binom n4.$$
At $n=7$ this gives $\operatorname{rank}_+(C_7)\le127<128$, disproving the
universal full-rank conjecture. In fact the displayed bound is strictly below
$2^n$ for every $n\ge7$. The construction separates the matrix into a
component invariant under complementing its row index and three nonnegative
correction families. A polynomial identity proves the factorization exactly.
The package also supplies all factors for $n=7$ and construction-independent
integer checks of all 16,384 entries. No numerical optimization, freely chosen
completion, or assumption about real factor coordinates is used.

Claims

LEAN VERIFIED OP-00111 — Full nonnegative rank of the quadratic correlation matrix
Disproof · fidelity not yet established

Files and sources

Paper
OpenProblemsInNLA @ 0e916df, holden-nr03-2026-09-13/NR03_counterexample.pdf ↗
Posted on GitHub
13 September 2026

No verification run is on record for this version.