Constrained Nonnegative Gram Feasibility is $$\exists \mathbb {R}$$

Abstract We study the computational complexity of constrained nonnegative Gram feasibility. Given a partially specified symmetric matrix together with affine relations among selected entries, the problem asks whether there exists a nonnegative matrix \(\varvec{H \in \mathbb {R}_+^{n\times r}}\) such that \(\varvec{W = HH^\top }\) satisfies all specified entries and affine constraints. Such factorizations arise naturally in structured low-rank matrix representations and geometric embedding problems. We prove that this feasibility problem is \(\varvec{\exists \mathbb {R}}\)-complete already for rank \(\varvec{r=2}\). The hardness result is obtained via a polynomial-time reduction from the arithmetic feasibility problem ETR-AMI. The reduction exploits a geometric encoding of arithmetic constraints within rank-\(\varvec{2}\) nonnegative Gram representations: by fixing anchor directions in \(\varvec{\mathbb {R}_+^2}\) and representing variables through vectors of the form \(\varvec{(x,1)}\), addition and multiplication constraints can be realized through inner-product relations. Combined with the semialgebraic formulation of the feasibility conditions, this establishes \(\varvec{\exists \mathbb {R}}\)-completeness. We further show that the hardness extends to every fixed rank \(\varvec{r\ge 2}\). Our results place constrained symmetric nonnegative Gram factorization among the growing family of semialgebraic feasibility problems that are complete for the complexity class \(\varvec{\exists \mathbb {R}}\). Finally, we discuss limitations of the result and highlight the open problem of determining the complexity of fully specified fixed-rank symmetric nonnegative Gram factorization feasibility. Data Availability No datasets were generated or analysed during the current study. References Laurent, M.: Matrix completion problems. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 1967–1975. Springer, Boston, MA (2008). https://doi.org/10.1007/978-0-387-74759-0_355 Tasissa, A., Lai, R.: Exact reconstruction of Euclidean distance geometry problem using low-rank matrix completion. IEEE Trans. Inf. Theory 65(5), 3124–3144 (2019). https://doi.org/10.1109/TIT.2018.2881749 Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003). https://doi.org/10.1142/5270 Bomze, I.M.: Copositive optimization - recent developments and applications. Eur. J. Oper. Res. 216(3), 509–520 (2012). https://doi.org/10.1016/j.ejor.2011.04.026 Cohen, J.E., Rothblum, U.G.: Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Algebra Appl. 190, 149–168 (1993). https://doi.org/10.1016/0024-3795(93)90226-J Vavasis, S.A.: On the complexity of nonnegative matrix factorization. SIAM J. Optim. 20(3), 1364–1377 (2010). https://doi.org/10.1137/070709967 Lee, D.D., Seung, H.S.: Learning the parts of objects by non-negative matrix factorization. Nature 401(6755), 788–791 (1999). https://doi.org/10.1038/44565 Schaefer, M.: Complexity of some geometric and topological problems. In: Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. Lecture Notes in Computer Science, vol. 5849, pp. 334–344. Springer, Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11805-0_32 Schaefer, M., Cardinal, J., Miltzow, T.: The existential theory of the reals as a complexity class: A compendium (2024). arXiv preprint arXiv:2407.18006 Mnëv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and Geometry: Rohlin Seminar. Lecture Notes in Mathematics, vol. 1346, pp. 527–544. Springer, Berlin, Heidelberg (1988). https://doi.org/10.1007/BFb0082792 Richter-Gebert, J.: Realization Spaces of Polytopes. Lecture Notes in Mathematics, vol. 1643. Springer, Berlin, Heidelberg (2006) Förster, H., Miltzow, T., Schnider, P.: Geometric thickness of multigraphs is \(\exists \mathbb{R} \)-complete. Algorithmica 88(3), 1–38 (2026). https://doi.org/10.1007/s00453-025-01351-7 Abrahamsen, M., Kleist, L., Miltzow, T.: Geometric embeddability of complexes is \(\exists \mathbb{R} \)-complete. In: Barequet, G., Tóth, C.D. (eds.) 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 258, pp. 1–1119. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2023). https://doi.org/10.4230/LIPIcs.SoCG.2023.1 Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for \(\exists \mathbb{R} \)-completeness of two-dimensional packing problems. TheoretiCS. 3, 12–11253 (2024). https://doi.org/10.46298/theoretics.2024.11145, arXiv:2004.07090 Shitov, Y.: A universality theorem for nonnegative matrix factorizations (2016). https://doi.org/10.48550/arXiv.1606.09068, arXiv:1606.09068 Miltzow, T., Schmiermann, R.F.: On classifying continuous constraint satisfaction problems. TheoretiCS 3 (2024). https://doi.org/10.46298/theoretics.24.10 Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization – provably. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing (STOC 2012), pp. 145–162. Association for Computing Machinery, New York, NY, USA (2012). https://doi.org/10.1145/2213977.2214002 Fawzi, H., Gouveia, J.A., Parrilo, P.A., Robinson, R., Thomas, R.R.: Positive semidefinite rank. Math. Program. 153(1), 133–177 (2015). https://doi.org/10.1007/s10107-014-0818-z Funding The author received no funding for this work. Author information Authors and Affiliations Contributions Angshul Majumdar conceived the problem, developed the theoretical results and proofs, carried out the analysis, and wrote the manuscript. Corresponding author Additional information Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Rights and permissions Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law. About this article Cite this article Majumdar, A. Constrained Nonnegative Gram Feasibility is \(\exists \mathbb {R}\)-Complete. Theory Comput Syst 70, 51 (2026). https://doi.org/10.1007/s00224-026-10292-9 Received: Accepted: Published: Version of record: DOI: https://doi.org/10.1007/s00224-026-10292-9