clopen.solutions

Positive semidefinite ranks of the five- and six-element subset-intersection matrices

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

Matthew J. Colbrook

The $10\times10$ matrix with rows indexed by two-element subsets
$I\subset[5]$, columns indexed by three-element subsets $J\subset[5]$ and
entries $|I\cap J|$ has real positive semidefinite rank exactly four. The
lower bound uses elementary rank constraints on the Hessian of a $3\times3$
determinant: a hypothetical size-three factorization gives a cubic in a
six-dimensional family, and ten Hessian conditions and positivity reduce it
to eight forms, each excluded by a small exact certificate. A two-layer graph
construction shows that the six-element instance also has positive
semidefinite rank four, and gives the general upper bound
$\lceil2\sqrt{2\lfloor(n-1)/2\rfloor}\rceil$. Since each matrix embeds as a
submatrix of the next, the rank is at least four for every $n\ge5$. The
five-element case is Problem 9.1 of Fawzi, Gouveia, Parrilo, Robinson and
Thomas.

Claims

PARTIALLY RESOLVED OP-00205 — Exact positive semidefinite rank of subset-intersection matrices
Partial resolution · fidelity not yet established

Files and sources

Paper
OpenProblemsInNLA @ eb7c9d6, manuscripts/PF-01_subset_intersection.pdf ↗
Posted on GitHub
11 September 2026

No verification run is on record for this version.