Exact nonnegative rank of regular polygon slack matrices
For $n \ge 3$ let $S_n \in \mathbb{R}^{n \times n}$ have entries $$S_n(i, j) = \cos(\pi/n) - \cos\bigl((2i + 1 - 2j)\pi/n\bigr), \qquad 0 \le i, j < n,$$ the slack matrix of the regular $n$-gon inscribed in the unit circle, and let $\operatorname{rank}_+$ be the nonnegative rank over $\mathbb{R}$, so that $\operatorname{rank}_+(S_n)$ is the extension complexity of the regular $n$-gon. Vandaele, Gillis and Glineur proved that the value below is an upper bound for every $n$. Equality holds for $n \le 16$, for $21 \le n \le 24$ and for $n = 31, 32$ (see Vandaele, Gillis and Glineur; the case $n = 14$ is from Dewez's thesis, as reported by Baeckelant, Vandaele and Gillis).
Problem. With $k = \lceil \log_2 n \rceil$, is $$\operatorname{rank}_+(S_n) = \begin{cases} 2k - 1, & 2^{k-1} < n \le 2^{k-1} + 2^{k-2},\\ 2k, & 2^{k-1} + 2^{k-2} < n \le 2^k, \end{cases}$$ for every $n \ge 3$?
Source: Vandaele, Gillis, Glineur and Tuyttens (2016), Conjecture 2.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CO, OC
- Keywords
- extended formulations, nonnegative rank, OpenProblemsInNLA, regular polygons
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{vandaele2016,
author = {Vandaele, Arnaud and Gillis, Nicolas and Glineur, Fran{\c{c}}ois and Tuyttens, Daniel},
title = {Heuristics for exact nonnegative matrix factorization},
journal = {J. Global Optim.},
volume = {65},
number = {2},
year = {2016},
pages = {369--400},
doi = {10.1007/s10898-015-0350-z},
eprint = {1411.7245},
archivePrefix = {arXiv},
}
@article{vandaele2017,
author = {Vandaele, Arnaud and Gillis, Nicolas and Glineur, Fran{\c{c}}ois},
title = {On the linear extension complexity of regular $n$-gons},
journal = {Linear Algebra Appl.},
volume = {521},
year = {2017},
pages = {217--239},
doi = {10.1016/j.laa.2016.12.023},
eprint = {1505.08031},
archivePrefix = {arXiv},
}
@misc{baeckelant2026,
author = {Baeckelant, Timothy and Vandaele, Arnaud and Gillis, Nicolas},
title = {Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers},
year = {2026},
eprint = {2605.14058},
archivePrefix = {arXiv},
note = {Version 3, 1 October 2026, Appendix A.2},
}
@misc{openproblemsinnla-nr01,
author = {Townsend, Alex},
title = {{NR-01}: Exact nonnegative rank of regular polygon slack matrices},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/nonnegative-and-positive-factorizations/NR-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
A computer-assisted exclusion of four-dimensional, eight-facet lifts proves that the regular $n$-gon slack matrix has real nonnegative rank nine for $17\le n\le20$; explicit nine-term factorizations give the matching upper bound. The reduction uses both factors of a nonnegative factorization, a complete finite cover of planar shadows, and exact determinant and Plücker-relation calculations over finite fields. The finite-field calculations certify ranks …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Exact ranks for the regular 17-, 18-, 19-, and 20-gons v1 recorded from OpenProblemsInNLA @ eb7c9d6, holden-nr01-2026-09-13/report.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00203, "Exact nonnegative rank of regular polygon slack matrices", clopen.solutions.