The nonnegative rank Rank+(A,F)\mathrm{Rank}_+(A,\mathbb{F}) of a nonnegative matrix AA over an ordered field F⊂R\mathbb{F}\subset\mathbb{R} is the smallest number of nonnegative rank-one matrices with entries in F\mathbb{F} that sum to AA. Cohen and Rothblum (1993) asked whether Rank+(A,Q)=Rank+(A,R)\mathrm{Rank}_+(A,\mathbb{Q})=\mathrm{Rank}_+(A,\mathbb{R}) for every rational matrix AA; Shitov (arXiv:1605.07173, published in SIAM Review 2017) settled this negatively with a 21×2121\times 21 integer matrix whose real nonnegative rank is at most 19 but whose rational nonnegative rank is at least 20, and Chistikov–Kiefer–Marušić–Shirmohammadi–Worrell independently gave a 6×116\times 11 example. The open problem is the program these resolutions leave open: classify the rational matrices for which the two ranks differ — in particular, whether the gap can already occur for matrices of conventional rank 3, given that equality is known for rank at most 2 and for nonnegative rank at most 3 — and determine the computational status of deciding and certifying the existence of rational factorizations of minimal length, which at present reduces only to the existential theory of the rationals.

Background

Nonnegative matrix factorization (NMF) decomposes a matrix AA with nonnegative real entries into a sum of nonnegative rank-one matrices, or equivalently a product A=WHA=WH of nonnegative matrices; the smallest number of summands (the inner dimension) is the nonnegative rank Rank+(A)\mathrm{Rank}_+(A), an invariant that can strictly exceed the usual linear-algebraic rank. If F⊂R\mathbb{F}\subset\mathbb{R} is an ordered field, one may require all entries of the factors to lie in F\mathbb{F}, which defines Rank+(A,F)\mathrm{Rank}_+(A,\mathbb{F}); since a factorization over F\mathbb{F} is also one over R\mathbb{R}, one always has Rank+(A,R)≤Rank+(A,F)\mathrm{Rank}_+(A,\mathbb{R})\le\mathrm{Rank}_+(A,\mathbb{F}). NMF is a standard tool in data mining, statistics, and imaging, and nonnegative rank governs the size of extended formulations — compact linear-programming descriptions of polytopes through their slack matrices (the nonnegative matrices tabulating, for each facet-defining inequality of the polytope, its slack at each vertex), in the sense of Yannakakis — so the field over which factors are computed bears both on exact computation and on the existence of rational linear-programming descriptions of rational polytopes.

Cohen and Rothblum, in their foundational 1993 study of nonnegative ranks, asked whether the ranks over Q\mathbb{Q} and over R\mathbb{R} coincide for every matrix with rational entries; they proved coincidence for matrices of (conventional) rank at most 2. Kubjas, Robeva, and Sturmfels, studying the algebraic boundary of the set of matrices of nonnegative rank at most 3 (in connection with fixed points of the expectation-maximization algorithm in statistics), proved that a rational matrix of nonnegative rank at most 3 always has a rational factorization of the same length (Corollary 4.6 of their Annals of Statistics article). Two independent constructions then broke the general question in 2016–2017. Shitov exhibited a 21×2121\times 21 matrix with nonnegative integer entries that is a sum of 19 real but not of 19 rational nonnegative rank-one matrices (arXiv:1605.07173; published, together with a short proof that computing nonnegative rank is NP-hard, as SIAM Review 59 (2017) 794–800). Chistikov, Kiefer, Marušić, Shirmohammadi, and Worrell exhibited a 6×116\times 11 rational matrix of real nonnegative rank 5 and rational nonnegative rank 6, obtained from a pair of nested three-dimensional rational polytopes whose unique five-vertex intermediate polytope has irrational coordinates; in matrix terms, a rational matrix with a unique minimal factorization, and that factorization is irrational. Shitov's earlier work 'Nonnegative rank depends on the field' (published in Mathematical Programming 186 (2021)) had already shown field-dependence over a non-rational subfield, and his universality theorem for NMF (arXiv:1606.09068) shows that deciding nonnegative rank is complete for ∃R\exists\mathbb{R} (the class of problems polynomial-time equivalent to deciding solvability of polynomial systems over the reals) and that nonnegative rank separates any two distinct intermediate fields lying between an ordered field and its real closure (the smallest algebraic extension in which every positive element has a square root and every odd-degree polynomial has a root). Field-dependence by choice of field is thus completely settled, and an analogous gap between rational and real positive semidefinite rank was shown by Fawzi, Gouveia, and Robinson. What remains unsettled is the classification by matrix: for which rational matrices the rational and real nonnegative ranks coincide, how small a gap example can be, and whether the rational nonnegative rank is computable at all.

Problem Statement

Determine where the rational–real nonnegative rank gap occurs and how it can be detected and certified. The common objective is a classification, by conventional rank, size, and structure, of the rational matrices AA with Rank+(A,Q)>Rank+(A,R)\mathrm{Rank}_+(A,\mathbb{Q})>\mathrm{Rank}_+(A,\mathbb{R}), together with its algorithmic face: deciding and certifying the existence of rational nonnegative factorizations of minimal length. Its currently sharp cores are: (1) Threshold question — decide whether there exists a rational matrix of conventional rank 3 whose rational nonnegative rank strictly exceeds its real nonnegative rank, or prove that every rank-3 rational matrix admits a rational factorization achieving its real nonnegative rank, which would show that the known rank-4 constructions are optimal; separately, determine whether the gap can already occur at real nonnegative rank 4, i.e., whether a rational matrix AA with Rank+(A,R)=4<Rank+(A,Q)=5\mathrm{Rank}_+(A,\mathbb{R})=4<\mathrm{Rank}_+(A,\mathbb{Q})=5 exists (Shitov's Problem 6 specialized to rational entries); the smallest known gap examples are 6×116\times 11 with ranks 5 versus 6 and 21×2121\times 21 with at most 19 versus at least 20, recorded here as context only. (2) Computability and certification question — determine whether Rank+(A,Q)\mathrm{Rank}_+(A,\mathbb{Q}) is computable, i.e., whether the problem 'given a rational matrix AA and an integer kk, is AA a sum of kk rational nonnegative rank-one matrices' is decidable, and independently, whether membership in {(A,k):Rank+(A)≤k}\{(A,k):\mathrm{Rank}_+(A)\le k\} admits certificates of polynomially bounded bit size (Vavasis's question whether nonnegative rank belongs to NP, which the known irrational examples show cannot be settled by the naive rational-factorization certificate). (3) Structural classification — extend the known equality classes, namely matrices of rank at most 2 (Cohen–Rothblum) and of nonnegative rank at most 3 (Kubjas–Robeva–Sturmfels), and characterize the structural families, such as matrices whose minimal factorization is unique, on which the known gap constructions rely.

References

  1. Yaroslav Shitov, Nonnegative rank depends on the field II, preprint (2016), arXiv:1605.07173, DOI 10.48550/arXiv.1605.07173, https://arxiv.org/abs/1605.07173
  2. Yaroslav Shitov, The nonnegative rank of a matrix: hard problems, easy solutions, SIAM Review 59(4) (2017) 794–800, DOI 10.1137/16M1080999, https://doi.org/10.1137/16M1080999 (journal version of the result in arXiv:1605.07173; preprint arXiv:1605.04000)
  3. Dmitry Chistikov, Stefan Kiefer, Ines Marušić, Mahsa Shirmohammadi, James Worrell, Nonnegative matrix factorization requires irrationality, SIAM Journal on Applied Algebra and Geometry 1(1) (2017) 285–307, DOI 10.1137/16M1078835, https://doi.org/10.1137/16M1078835 (preprint arXiv:1605.06848)
  4. Joel E. Cohen, Uriel 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
  5. Kaie Kubjas, Elina Robeva, Bernd Sturmfels, Fixed points of the EM algorithm and nonnegative rank boundaries, The Annals of Statistics 43(1) (2015) 422–461, DOI 10.1214/14-AOS1282, https://doi.org/10.1214/14-AOS1282 (preprint arXiv:1312.5634)
  6. Yaroslav Shitov, Nonnegative rank depends on the field, Mathematical Programming 186 (2021) 479–486, DOI 10.1007/s10107-019-01448-2, https://doi.org/1007/s10107-019-01448-2 (preprint arXiv:1505.01893)
  7. Yaroslav Shitov, A universality theorem for nonnegative matrix factorizations, preprint (2016, revised 2018), arXiv:1606.09068, DOI 10.48550/arXiv.1606.09068, https://arxiv.org/abs/1606.09068
  8. Hamza Fawzi, João Gouveia, Richard Z. Robinson, Rational and real positive semidefinite rank can be different, Operations Research Letters 44(1) (2016) 59–60, DOI 10.1016/j.orl.2015.11.012, https://doi.org/10.1016/j.orl.2015.11.012
  9. Stephen A. Vavasis, On the complexity of nonnegative matrix factorization, SIAM Journal on Optimization 20(3) (2009) 1364–1377, DOI 10.1137/070709967, https://doi.org/10.1137/070709967
  10. Mihalis Yannakakis, Expressing combinatorial optimization problems by linear programs, Journal of Computer and System Sciences 43(3) (1991) 441–466, DOI 10.1016/0022-0000(91)90024-Y, https://doi.org/10.1016/0022-0000(91)90024-Y
  11. Nicolas Gillis, Introduction to Nonnegative Matrix Factorization, survey (2017), arXiv:1703.00663, DOI 10.48550/arXiv.1703.00663, https://arxiv.org/abs/1703.00663
  12. Manuel Aprile, Gennadiy Averkov, Marco Di Summa, Christopher Hojny, The role of rationality in integer-programming relaxations, Mathematical Programming 205 (2024) 745–771, DOI 10.1007/s10107-023-01994-w, https://doi.org/10.1007/s10107-023-01994-w (preprint arXiv:2206.12253)
  13. Michael G. Dobbins, Andreas Holmsen, Tillmann Miltzow, A universality theorem for nested polytopes, preprint (2019), arXiv:1908.02213, DOI 10.48550/arXiv.1908.02213, https://arxiv.org/abs/1908.02213
  14. Robert Krone, Kaie Kubjas, Uniqueness of nonnegative matrix factorizations by rigidity theory, SIAM Journal on Matrix Analysis and Applications 42 (2021) 134–164, DOI 10.1137/19M1279472, https://doi.org/10.1137/19M1279472 (preprint arXiv:1902.02868)
  15. Yaroslav Shitov, On the nonnegative ranks of matrices in Puiseux series fields, Advances in Applied Mathematics 170 (2025), article 102916, DOI 10.1016/j.aam.2025.102916, https://doi.org/10.1016/j.aam.2025.102916