A characterization for positive semi-definite matrix products

A well-known fact in linear algebra is that $A^{T}A$ is always positive semi-definite for any real matrix $A$. We consider a generalization of this fact via the following decision problem. Given a symbolic product of length $k$, consisting of $\mathrm{\ell }$ variables and their transposes, such as $AB{B}^{T}C{A}^T$, does there exist an $n\in \mathbb{N}$ and an assignment of matrices from ${\mathbb{R}}^{n\times n}$ such that the resulting matrix product has a negative eigenvalue? We show that this problem is decidable and provide a simple characterization of those symbolic products that have only non-negative real eigenvalues for any assignment of matrices. This characterization can also be understood as a matrix analogue of the positive graph conjecture by Camarena, Csóka, Hubai, Lippner, and Lovász, and the proof relies on this surprising connection to graph theory.