Given any symmetric matrix $S \in \mathbb{R}^{n \times n}$, if $S \succeq 0$, is there a way to encode $S$ into a graph such that it takes into account the positive semidefinite constraint, and ideally, also the sparsity of $S$?
For any symmetric matrix $M \in \mathbb{R}^{n\times n}$, I think we can encode it as an undirected graph by simply considering $n$ vertices, and with entries of the matrix corresponding to edge weights. However, I cannot think of any specific ways to characterize the subset of positive semidefinite matrices. Maybe we can use the determinant characterization to do some tricks, but I am not very familiar with graph theory.
The motivation is that I want to consider the minimization problem $\operatorname{min}_{X \succeq 0} \|\mathscr{A}(X) - b\|^{2}$, where $\mathscr{A}(X) = [\langle A_{1},X \rangle, \langle A_{2}, X\rangle ,\dots ,\langle A_{n}, X \rangle]$. $A_{1},\dots ,A_{n} \in \{ 0,1 \}^{n \times n}$ and are pairwise orthogonal, somewhat like a generalization of matrix completion. I just recently heard of Chordal graphs, and maybe it's related, but I certainly need to read more about it.
