Additivity for Cartesian-product slack matrices
Let $P \subset \mathbb{R}^d$ and $Q \subset \mathbb{R}^e$, with $d, e \ge 1$, be full-dimensional polytopes, and let $S \in \mathbb{R}_{\ge 0}^{m \times n}$ and $T \in \mathbb{R}_{\ge 0}^{p \times q}$ be slack matrices of $P$ and $Q$ with one row for each facet and one column for each vertex. Let $C \in \mathbb{R}_{\ge 0}^{(m+p) \times nq}$ have one column for each pair $(i, j)$ of a vertex $i$ of $P$ and a vertex $j$ of $Q$, $$C_{:,(i,j)} = \begin{pmatrix} S_{:,i} \\ T_{:,j} \end{pmatrix};$$ it is a slack matrix of $P \times Q$. Let $\operatorname{rank}_+$ be the nonnegative rank over $\mathbb{R}$; the nonnegative rank of a slack matrix of a polytope is the polytope's extension complexity $\operatorname{xc}$. The inequality $\operatorname{rank}_+(C) \le \operatorname{rank}_+(S) + \operatorname{rank}_+(T)$ always holds, and equality holds when $P$ or $Q$ is a simplex (Grande, Padrol and Sanyal) or, more generally, a pyramid (Tiwary, Weltge and Zenklusen). For nonnegative matrices $S$ and $T$ that are not slack matrices, the inequality can be strict (Gillis).
Problem. Is $$\operatorname{rank}_+(C) = \operatorname{rank}_+(S) + \operatorname{rank}_+(T)$$ for all such $P$ and $Q$? Equivalently, is $\operatorname{xc}(P \times Q) = \operatorname{xc}(P) + \operatorname{xc}(Q)$?
Source: Grande, Padrol and Sanyal (2018), Conjecture 1, who say it was first asked at a Dagstuhl seminar in 2013; in this slack-matrix form, Gillis (2020), §3.6.5.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CO, OC
- Keywords
- Cartesian products, extended formulations, nonnegative rank, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{grande2018,
author = {Grande, Francesco and Padrol, Arnau and Sanyal, Raman},
title = {Extension complexity and realization spaces of hypersimplices},
journal = {Discrete Comput. Geom.},
volume = {59},
number = {3},
year = {2018},
pages = {621--642},
doi = {10.1007/s00454-017-9925-4},
eprint = {1601.02416},
archivePrefix = {arXiv},
}
@book{gillis2020,
author = {Gillis, Nicolas},
title = {Nonnegative Matrix Factorization},
publisher = {SIAM},
address = {Philadelphia, PA},
year = {2020},
doi = {10.1137/1.9781611976410},
note = {Section 3.6.5},
}
@article{tiwary2017,
author = {Tiwary, Hans Raj and Weltge, Stefan and Zenklusen, Rico},
title = {Extension complexities of {C}artesian products involving a pyramid},
journal = {Inform. Process. Lett.},
volume = {128},
year = {2017},
pages = {11--13},
doi = {10.1016/j.ipl.2017.07.011},
eprint = {1702.01959},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-nr02,
author = {Townsend, Alex},
title = {{NR-02}: Additivity for Cartesian-product 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-02/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For convex polygons $P,Q$ with $\operatorname{xc}(P)=\operatorname{xc}(Q)=6$, the note proves $\operatorname{xc}(P\times Q)=12$ by a finite, certificate-based support argument. Every such polygon has between six and nine vertices. A hypothetical eleven-term nonnegative factorization of the complete product slack matrix must satisfy explicit row-degree, vertex-slice, edge-slice, pure-column and coverage conditions. These give ten Boolean formulas, one for each unordered pair of polygon sizes, …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Cartesian-product slack matrices: complexity-six polygon products v1 recorded from OpenProblemsInNLA @ eb7c9d6, NR-02/report.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00204, "Additivity for Cartesian-product slack matrices", clopen.solutions.