Questions about hermitian positive semidefinite matrices

Question

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.

Answer 1

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.