SNT-Rank: Kronecker Products and Euclidean Distance Matrices

Abstract

Symmetric nonnegative matrix trifactorizations (SN-Trifactorizations) were introduced by Bukovšek-Šmigoc [Linear Algebra Appl. 2023] as a symmetric analogue of nonnegative matrix factorizations. A SN-Trifactorization of a symmetric nonnegative matrix $A$ is of the form $A=BC{B}^T,$ where $B$ and $C$ are nonnegative matrices, with $C$ symmetric. The associated SNT-rank of $A$ is defined as the smallest integer $k$ for which $A$ admits such a factorization with $C\in {\mathbb{R}}_{+}^{k\times k}$. In this paper, we derive sharper upper bounds for the SNT-rank of the Euclidean distance matrices considered by Shitov [Linear Algebra Appl. 2025] and Bukovšek-Šmigoc [Linear Algebra Appl. 2023]. We also establish several new relationships between the rank and the SNT-rank of symmetric nonnegative matrices and show that the SNT-rank is submultiplicative with respect to the Kronecker product. Finally, motivated by a conjecture posed in the Dagstuhl Seminar Report 13082, we prove a multiplicativity result for the nonnegative rank under an additional structural assumption. We also partially resolve a conjecture of Vandaele-Gillis-Glineur-Tuyttens [J. Global Optim. 2016].

15 pages, no figures