Matrix positive semidefinitness and sum of (weakly) diagonally dominant matrices

convex-analysislinear algebrareference-request

I remember reading, some time ago, about a few decomposition theorems for (symmetric) positive semidefinite matrices. I can't recall the results (I can barely even recall the paper) but I vaguely remember some decomposition theorem saying the following (here, all matrices are assumed to be symmetric):

Given a symmetric matrix $A \in \mathbf{S}^n$, $A$ is PSD if, and only if, it can be written as a conic combination of (weakly) diagonally dominant matrices. In other words, if $\mathcal{D}$ is the set of diagonally dominant matrices, then $A$ is PSD if, and only if, there exists matrices $D_i \in \mathcal{D}$ and nonnegative $\alpha_i \ge 0$ such that
$$
A = \sum_{i=1}^d \alpha_iD_i.
$$

(In fact, the scaling by $\alpha_i$ is not needed since $\alpha_iD_i$ is also diagonally dominant, so it would suffice to simply be the sum of diagonally dominant matrices.)

Clearly the "only if" part is true, but the "if" part is not fully clear to me. (That is, if it's even true at all!) I was wondering if anyone had a reference, or a slick proof or counterexample to this claim? That would be phenomenal! Thanks 🙂

Best Answer

Actually, this statement is certainly not true. (I only realized this after posting.) A simple proof follows from the basic fact that this statement is equivalent to asking if the convex hull of (positive semidefinite) diagonally dominant matrices is equal to the set of positive semidefinite matrices.

But the set of diagonally dominant matrices is already a convex set! This is because it can be written as the intersection convex sets, since $$ \mathcal{D} = \left\{A \in \mathbf{R}^{n\times n} \mid A_{ii} \ge \sum_{j\ne i} |A_{ij}|, ~ i=1, \dots, n\right\}, $$ which is just the intersection of a bunch of affine inequalities. So, its convex hull can be no larger than the set itself, and, because we know that $\mathcal{D} \subsetneq \mathbf{S}_+^n$, the result follows.

Related Question