# Questions about hermitian positive semidefinite matrices

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.

• For question 3, we can produce a negative answer using the fact that if $P,Q$ are positive semidefinite, then $\text{Im}(P+Q)=\text{Im}(P)+\text{Im}(Q)$. In particular, if $P+Q$ is rank 1, then $P,Q$ are linearly dependent. This means that if $u$ is a row vector where all the coordinates are non-zero, then $uu^*$ cannot be written as a sum of positive definite principal $S$-matrices. Commented Dec 27, 2022 at 1:39
• For Q3, consider the $3\times 3$ matrix with all 1s. To catch the off-diagonal elements you need three $2\times 2$ $S$-matrices with off-diagonal 1s and positive diagonal elements whose product is at least 1. Subtracting them off leaves at least one negative diagonal element. Commented Dec 27, 2022 at 1:41

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.
• nice, thanks a lot! Interestingly, for $n = 4$ (the previous case), the matrices relevant to my problem were all $n-1$-incoherent. I will google for some algorithms to compute the factor width. Do you happen to know of a Python library by any chance which computes the factor width? Anyway, I now know what it is called in the literature. Thank you very much! Commented Dec 27, 2022 at 3:22