Nontrivial upper bounds on the nonnegative rank of matrices of ordinary rank four and higher

The nonnegative rank $\operatorname{rank}_+(A)$ of a nonnegative matrix — the smallest number of nonnegative rank-one matrices summing to $A$ — satisfies $\operatorname{rank}(A) \le \operatorname{rank}_+(A) \le \min\{m,n\}$, and the upper bound is trivially attained. Shitov (2014) proved the first nontrivial upper bound in terms of ordinary rank: every nonnegative matrix of ordinary rank 3 has nonnegative rank at most $\lceil 6\min\{m,n\}/7 \rceil$, equivalently every convex $n$-gon has extension complexity (the minimum number of facets of a higher-dimensional polytope that projects onto it) at most $\lceil 6n/7 \rceil$; this ceiling was later lowered to $147\,n^{2/3}$. For matrices of ordinary rank 4 and higher, however, no nontrivial upper bound of any kind is known, and it is equally open whether matrices of ordinary rank 4 with full nonnegative rank exist for arbitrarily large sizes. The problem asks to settle the existence, form, and order of growth of nontrivial upper bounds on the worst-case nonnegative rank of matrices of any fixed ordinary rank $d \ge 4$ — equivalently, for $d = 4$, whether every pair of nested 3-dimensional polytopes $P_{\mathrm{in}} \subseteq P_{\mathrm{out}}$ admits an intermediate polytope with fewer vertices than the trivial count $\min\{v(P_{\mathrm{in}}), f(P_{\mathrm{out}})\}$ (the polytope rendering of the matrix bound $\min\{m,n\}$), where $v(\cdot)$ and $f(\cdot)$ denote vertex and facet counts.

Background

The nonnegative rank of a nonnegative $m \times n$ matrix $A$, written $\operatorname{rank}_+(A)$, is the smallest integer $k$ for which $A = BC$ with $B$ and $C$ entrywise nonnegative — equivalently, the smallest number of nonnegative rank-one matrices summing to $A$. Such decompositions are the subject of nonnegative matrix factorization (NMF), a standard dimensionality-reduction model in data analysis. One always has $\operatorname{rank}(A) \le \operatorname{rank}_+(A) \le \min\{m,n\}$, where $\operatorname{rank}$ denotes the ordinary rank over the reals, and $\operatorname{rank}_+(A) = \operatorname{rank}(A)$ whenever the ordinary rank is at most 2 (Cohen and Rothblum 1993; Beasley and Laffey 2009). The gap between the two ranks is therefore invisible below ordinary rank 3 and unbounded in general, which makes the worst-case size of this gap, as a function of the ordinary rank and of the matrix dimensions, a basic structural question about nonnegative factorizations.

A second origin of the same quantity is polyhedral optimization. An extended formulation of a polytope $P$ is a description of a polytope $Q$, in possibly higher dimension, by linear equations and inequalities, such that $P$ is a linear projection of $Q$; the extension complexity $\operatorname{xc}(P)$ is the minimum number of inequalities over all such descriptions. Yannakakis (1991) proved that $\operatorname{xc}(P)$ equals the nonnegative rank of any slack matrix of $P$ — the nonnegative matrix whose $(i,j)$ entry measures how far the $j$-th vertex is from saturating the $i$-th facet inequality — and the slack matrix of a $d$-dimensional polytope has ordinary rank $d+1$. Hence nontrivial upper bounds on the nonnegative rank of fixed-rank matrices are exactly nontrivial upper bounds on the extension complexity of fixed-dimensional polytopes, that is, on the size of their linear-programming formulations.

For ordinary rank 3 the worst case is a well-studied quantity, $\operatorname{pc}(n)$, the largest extension complexity of a convex $n$-gon (slack matrices of $n$-gons have ordinary rank 3). Beasley and Laffey (2009) asked whether a rank-3 $n \times n$ matrix with nonnegative rank $n$ exists. Gillis and Glineur (2012) characterized $\operatorname{rank}_+(A)$ geometrically as the minimum number of vertices of a polytope nested between an inner and an outer polytope determined by $A$, and settled the question positively for $n \le 5$; Gouveia, Parrilo and Thomas (2013) settled $n = 6$ via a sufficiently irregular hexagon. Shitov (2014) proved that every nonnegative rank-3 $m \times n$ matrix obeys $\operatorname{rank}_+(A) \le \lceil 6\min\{m,n\}/7 \rceil$ and consequently $\operatorname{pc}(n) \le \lceil 6n/7 \rceil$, giving a negative answer for $n \ge 7$. Shitov's later work ('Sublinear extensions of polygons', 2020 preprint, published 2026) identified $\operatorname{pc}(n)$, for $n > 3$, with the largest nonnegative rank of a matrix with at most $n$ rows and ordinary rank 3, proved $\operatorname{pc}(n) \le 147\,n^{2/3}$ — refuting widely held expectations of (near-)linear growth, such as the affirmative answer conjectured by several authors to the question of Braun and Pokutta (2016) whether $\operatorname{pc}(n) > \varepsilon n$ for a fixed $\varepsilon > 0$ — and left the asymptotics open: dimension counting gives $\operatorname{pc}(n) \ge \sqrt{2n}$ (Fiorini, Rothvoß and Tiwary 2012), Padrol (2016) improved this to $2\sqrt{2n} - O(1)$, and for regular polygons Goucha, Gouveia and Silva (2017) proved a lower bound of about $1.44\log_2 n$ on the nonnegative rank of the slack matrix.

For ordinary rank $d \ge 4$ — corresponding to polytopes of dimension 3 and higher — the picture is empty: no nontrivial upper bound on nonnegative rank is known for any $d \ge 4$, and the trivial bound $\min\{m,n\}$ is the only general one. On the lower-bound side, generic 3-dimensional polytopes with $n$ facets provide rank-4 slack matrices with nonnegative rank at least about $2\sqrt{3n}$ (Padrol 2016), and full extension complexity in dimension 3 is known to occur generically only up to 8 vertices or facets. Worst-case results do exist for neighboring invariants and cones — positive-semidefinite formulations (descriptions by linear matrix inequalities, a strictly more expressive model than linear inequalities) of size at most $4\lceil n/6 \rceil$ exist for every $n$-gon (Gouveia, Robinson and Thomas 2015), and every $d$-dimensional 0/1-polytope has linear extension complexity $O(2^d/d)$ (Averkov, Kaibel and Weltge 2018) — but neither transfers to the nonnegative rank of general matrices or to linear extension complexity of fixed-dimension polytopes.

Problem Statement

Let $R(d, n)$ denote the largest nonnegative rank attained by a nonnegative matrix of ordinary rank at most $d$ whose smaller dimension (the minimum of its numbers of rows and columns) is at most $n$. The known landmarks are: $R(2, n) = 2$ for $n \ge 2$; $R(3, n) = \operatorname{pc}(n)$, the worst-case extension complexity of a convex $n$-gon, which lies between $2\sqrt{2n} - O(1)$ and $147\,n^{2/3}$; $R(d, n) \le n$ trivially; and $R(4, n) \ge 2\sqrt{3n} - O(1)$ via slack matrices of generic 3-dimensional polytopes (Padrol 2016).

The problem is to settle, for fixed ordinary rank $d \ge 4$, whether the trivial bound $\min\{m,n\}$ can be improved in the worst case — with $d = 4$ being the first open rung. The question has two possible resolutions for a given $d \ge 4$:

(1) Prove a nontrivial upper bound: establish a function $f(d, n)$ with $f(d, n) < n$ for all sufficiently large $n$ such that every nonnegative matrix of ordinary rank at most $d$ and smaller dimension at most $n$ has nonnegative rank at most $f(d, n)$, and identify the form and order of growth of the bound $f$ so established; determining the true asymptotics of $R(d, n)$ itself is not required for this option.

(2) Disprove the possibility of such a bound: construct, for infinitely many $n$, explicit nonnegative matrices of ordinary rank $d$ whose nonnegative rank equals their smaller dimension $n$ — equivalently, by the nested-polytope interpretation of nonnegative rank, pairs of nested $(d-1)$-dimensional polytopes that admit no intermediate polytope with fewer vertices.

For $d = 4$, statement (2) asks whether a rank-4 analogue of the Beasley–Laffey full-rank matrices exists, and statement (1) asks whether the sublinearity phenomenon Shitov established for ordinary rank 3 persists one rank higher; equivalently, whether every pair of nested 3-dimensional polytopes $P_{\mathrm{in}} \subseteq P_{\mathrm{out}}$ admits an intermediate polytope with fewer vertices than the trivial count $\min\{v(P_{\mathrm{in}}), f(P_{\mathrm{out}})\}$. The common objective is the order of growth of $R(d, n)$ for fixed $d \ge 4$; a result covering every fixed $d \ge 4$, in either direction, resolves the problem in full generality. Within the per-$d$ formulation above, $d = 4$ is the smallest admissible instance: since a matrix of ordinary rank 4 also has rank at most $d$ for every $d \ge 4$, a rank-4 full-rank construction as in (2) refutes any eventual nontrivial upper bound for all $d \ge 4$, whereas an upper bound established only for $d = 4$ leaves the higher ranks open.

References

1. L. B. Beasley and T. J. Laffey, Real rank versus nonnegative rank, Linear Algebra and its Applications 431 (2009) 2330–2335. DOI: 10.1016/j.laa.2009.02.034, https://doi.org/10.1016/j.laa.2009.02.034
2. J. E. Cohen and U. G. Rothblum, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra and its Applications 190 (1993) 149–168. DOI: 10.1016/0024-3795(93)90224-C, https://doi.org/10.1016/0024-3795(93)90224-C
3. Yaroslav Shitov, An upper bound for nonnegative rank, Journal of Combinatorial Theory, Series A 122 (2014) 126–132. DOI: 10.1016/j.jcta.2013.10.004; arXiv:1303.1960, https://arxiv.org/abs/1303.1960
4. Samuel Fiorini, Thomas Rothvoß, and Hans Raj Tiwary, Extended formulations for polygons, Discrete & Computational Geometry 48 (2012) 658–668. DOI: 10.1007/s00454-012-9421-9, https://doi.org/10.1007/s00454-012-9421-9
5. N. Gillis and F. Glineur, On the geometric interpretation of the nonnegative rank, Linear Algebra and its Applications 437 (2012) 2685–2712. DOI: 10.1016/j.laa.2012.06.038, https://doi.org/10.1016/j.laa.2012.06.038
6. J. Gouveia, P. A. Parrilo, and R. R. Thomas, Lifts of convex sets and cone factorizations, Mathematics of Operations Research 38 (2013) 248–264. DOI: 10.1287/moor.1120.0575, https://doi.org/10.1287/moor.1120.0575
7. João Gouveia, Richard Z. Robinson, and Rekha R. Thomas, Worst-case results for positive semidefinite rank, Mathematical Programming 153 (2015) 201–212. DOI: 10.1007/s10107-015-0867-4, https://doi.org/10.1007/s10107-015-0867-4
8. Arnau Padrol, Extension complexity of polytopes with few vertices or facets, SIAM Journal on Discrete Mathematics 30 (2016) 2162–2176. DOI: 10.1137/16M1063721; arXiv:1602.06894, https://arxiv.org/abs/1602.06894
9. António Pedro Goucha, João Gouveia, and Pedro M. Silva, On ranks of regular polygons, SIAM Journal on Discrete Mathematics 31 (2017) 2612–2625. DOI: 10.1137/16M1105608, https://doi.org/10.1137/16M1105608
10. Gennadiy Averkov, Volker Kaibel, and Stefan Weltge, Maximum semidefinite and linear extension complexity of families of polytopes, Mathematical Programming 167 (2018) 381–394. DOI: 10.1007/s10107-017-1134-7; arXiv:1605.08538, https://arxiv.org/abs/1605.08538
11. Matthew Kwan, Lisa Sauermann, and Yufei Zhao, Extension complexity of low-dimensional polytopes, Transactions of the American Mathematical Society 375 (2022) 4209–4250. DOI: 10.1090/tran/8614; arXiv:2006.08836, https://arxiv.org/abs/2006.08836
12. Yaroslav Shitov, Sublinear extensions of polygons, Proceedings of the London Mathematical Society 132 (2026), no. 4, e70137. DOI: 10.1112/plms.70137; arXiv:1412.0728, https://arxiv.org/abs/1412.0728
13. Roman Drnovšek and Marko Kandič, On the nonnegative rank of positive operators, arXiv:2605.21232 (2026), https://arxiv.org/abs/2605.21232
14. M. Yannakakis, Expressing combinatorial optimization problems by linear programs, Journal of Computer and System Sciences 43 (1991) 441–466. DOI: 10.1016/0022-0000(91)90024-Y, https://doi.org/10.1016/0022-0000(91)90024-Y
15. G. Braun and S. Pokutta, Common information and unique disjointness, Algorithmica 76 (2016) 597–629. DOI: 10.1007/s00453-016-0132-0, https://doi.org/10.1007/s00453-016-0132-0