5
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented 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 [email protected]). $\endgroup$ Commented Dec 27, 2022 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.