Motivation: I am faced with a $5 \times 5$ hermitian positive semidefinite matrix, depending on parameters, and I wish to show that it is positive definite, for any points in the parameter space (I actually already know it is always positive semidefinite, so I basically would like to show that it is always non-singular).


My approach was to first try to write it as a sum of hermitian positive semidefinite matrices of the following form. Let $S \subset \{1, 2, 3, 4, 5\}$ be non-empty and not the whole set. In other words, $0 < |S| < 5$. Denote by $S^c$ its complement in $\{1, \ldots, 5 \}$. By a principal $S$-matrix, we mean a $5 \times 5$ matrix, say $A = (a\_{ij})$, such that $a\_{ij} = 0 \text{ if $i \in S^c$ or if $j \in S^c$}$. In other words, the entry of $A$ corresponding to the pair of indices $(i, j)$ is $0$ whenever $(i, j) \notin S \times S$.


Indeed, assuming this can be done, it would then be much easier to prove positive definiteness. It is enough to find, say $S\_1$ and $S\_2$, with $S\_1 \cup S\_2 = \{1, \ldots, 5 \}$ and such that both the principal $S\_1$ and $S\_2$ summands of the original matrix in the sum have positive definite $S\_1$-, respectively $S\_2$-, principal submatrix (Please note that I am not at all claiming that there is a unique way of writing the original matrix as such a sum). This would then imply that the original matrix is positive definite.


I wrote things for $n = 5$, but one could of course definite things similarly for a general $n$.


Question 1: which $n \times n$ hermitian positive semidefinite matrices can be written as a sum of hermitian positive semidefinite principal $S$-matrices, where $S$ runs over the collection of all non-empty proper subsets of $\{1, \ldots, n\}$?


Note that, in practice, being able to write an hermitian positive semidefinite matrix as a sum of hermitian positive semidefinite principal $S$-matrices may be useful within an induction argument over $n$.


If $n = 2$, it is clear that only diagonal hermitian positive semidefinite matrices can be written as a sum of hermitian positive semidefinite principal $S$-matrices.


This indicates that, in order to obtain a more general result, which is applicable to any hermitian $n \times n$ positive semidefinite matrix, one may need a more complicated "ansatz" than just a sum of hermitian positive semidefinite principal $S$-matrices.


Question 2: What would such a "positivstellensatz" be please? In other words, how can we modify the statement "original matrix is the sum of hermitian positive semidefinite principal $S$-matrices" so that the statement would then be true for any $n \times n$ hermitian positive semidefinite matrix?


Question 3 (related to question 2): if $n \geq 3$, can any $n \times n$ hermitian positive semidefinite matrix be written as a sum of hermitian positive semidefinite principal $S$-matrices?


Edit 1: I see that, at the time of writing, I got both an upvote and a vote to close, which is why I did some editing to my post above, added some more details and made it a little clearer hopefully (especially as regards to question 2). I also added question 3, which is related to question 2.


Edit 2: Thanks to Joseph Van Name and Brendan McKay's comments below, the answer to question 1 is the following. An $n \times n$ hermitian positive semidefinite matrix $A$ can be written as a sum of hermitian positive semidefinite principal $S$-matrices iff


$$A = c\_1 v\_1 v\_1^\* + \cdots + c\_r v\_r v\_r^\*$$


where $c\_i \geq 0$ for $i = 1, \ldots, r$ and each $v\_i \in \mathbb{C}^n$ has at least one zero component. The "if" direction is obvious. For the "only if" direction, it suffices to show that any hermitian positive semidefinite principal $S$-matrix is a linear combination, with nonnegative coefficients, of matrices of the form $v v^\*$, where $v$ has $0$ coefficients for all indices in $S^c$. This is easy to see, since any principal $S$-matrix is the direct sum of an $|S| \times |S|$ principal $S$-submatrix of $A$ and an $|S^c| \times |S^c|$ zero matrix. We then apply the spectral theorem to the $|S| \times |S|$ principal $S$-submatrix of $A$ and then "append zeros" to the obtained vectors.



Questions about hermitian positive semidefinite matrices
You noted in your "Edit 2" that these $n \times n$ matrices $A$ are exactly those that can be written in the form
$$
A = \sum\_j \mathbf{v\_j}\mathbf{v}\_{\mathbf{j}}^\*,
$$
where each $\mathbf{v\_j}$ has at most $(n-1)$ non-zero entries. These matrices $A$ are exactly those with "factor width" at most $n-1$ (I don't know what the best reference for the factor width of a matrix is, but Googling the term results in numerous papers about the concept).


This concept comes up with some frequency in quantum information theory, where such a matrix $A$ would instead be said to be "$(n-1)$-incoherent". Googling terms like "multilevel incoherence" or "$k$-incoherence" will lead you to quantum information theory papers about this concept.


