OP-00205 Partially resolved

Exact positive semidefinite rank of subset-intersection matrices

For $n \ge 5$ let $M^{(n)}$ be the matrix whose rows are indexed by the $\lfloor n/2 \rfloor$-element subsets $I$ of $\{1, \dots, n\}$, whose columns are indexed by the $\lceil n/2 \rceil$-element subsets $J$, and whose entries are $M^{(n)}_{I,J} = |I \cap J|$. Let $\operatorname{rank}_{\mathrm{psd}}$ be the positive semidefinite rank with real symmetric factors. The bounds $$\left\lceil \frac{\sqrt{1 + 8n} - 1}{2} \right\rceil \le \operatorname{rank}_{\mathrm{psd}}(M^{(n)}) \le 2 \lceil \sqrt{n} \rceil$$ and $\operatorname{rank}_{\mathrm{psd}}(M^{(5)}) \le 4$ are known (Fawzi, Gouveia, Parrilo, Robinson and Thomas). Vandaele, Glineur and Gillis use these matrices as test cases for algorithms computing positive semidefinite factorizations.

Problem. Determine $\operatorname{rank}_{\mathrm{psd}}(M^{(n)})$ as a function of $n \ge 5$.

Source: Fawzi, Gouveia, Parrilo, Robinson and Thomas (2015), Problem 9.2, whose Problem 9.1 is the case n = 5; stated for n ≥ 5 by OpenProblemsInNLA.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NA — Numerical Analysis
Secondary: CO, OC
Keywords: Johnson schemes, OpenProblemsInNLA, positive semidefinite factorizations, positive semidefinite rank
Literature checked: Oct. 8, 2026 by clemens-admin

References

@article{fawzi2015,
  author        = {Fawzi, Hamza and Gouveia, Jo{\~a}o and Parrilo, Pablo A. and Robinson, Richard Z. and Thomas, Rekha R.},
  title         = {Positive semidefinite rank},
  journal       = {Math. Program.},
  volume        = {153},
  number        = {1},
  year          = {2015},
  pages         = {133--177},
  doi           = {10.1007/s10107-015-0922-1},
  eprint        = {1407.4095},
  archivePrefix = {arXiv},
}
@article{vandaele2018,
  author        = {Vandaele, Arnaud and Glineur, Fran{\c{c}}ois and Gillis, Nicolas},
  title         = {Algorithms for positive semidefinite factorization},
  journal       = {Comput. Optim. Appl.},
  volume        = {71},
  number        = {1},
  year          = {2018},
  pages         = {193--219},
  doi           = {10.1007/s10589-018-9998-x},
  eprint        = {1707.07953},
  archivePrefix = {arXiv},
}
@misc{openproblemsinnla-pf01,
  author       = {Townsend, Alex},
  title        = {{PF-01}: Exact positive semidefinite rank of subset-intersection matrices},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/nonnegative-and-positive-factorizations/PF-01/README.md},
  note         = {Read at commit eb7c9d6, 2026-10-07},
}

Resolution claims

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

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 …

Partial resolution · not verified · fidelity not established · posted on GitHub 11 Sep 2026

Status history

When	Change	By	Reason
2026-10-08	Open → Partially resolved	The registry's curators	Positive semidefinite ranks of the five- and six-element subset-intersection matrices v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscripts/PF-01_subset_intersection.pdf.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00205, "Exact positive semidefinite rank of subset-intersection matrices", clopen.solutions.