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
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.