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.

  • 1
    $\begingroup$ 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. $\endgroup$ Dec 27, 2022 at 1:39
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 27, 2022 at 1:41

1 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.

  • $\begingroup$ 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! $\endgroup$
    – Malkoun
    Dec 27, 2022 at 3:22
  • $\begingroup$ I don't know of an off-the-shelf Python script for computing factor width, but it can be computed by semidefinite programming, so it should be straightforward-ish to make a Python script that computes it via something like CVXPY. I have a MATLAB script that determines whether or not a matrix has factor width <= k that I can share with you, if it's useful (e-mail me at njohnston@mta.ca). $\endgroup$ Dec 27, 2022 at 15:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .