SNT-Rank: Kronecker Products and Euclidean Distance Matrices

Abstract

Symmetric nonnegative matrix trifactorizations (SN-Trifactorizations) were introduced by Bukov\v{s}ek-\v{S}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 = BCB^{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\v{s}ek-\v{S}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].