Sum of a diagonal matrix and a symmetric positive semidefinite matrix

Question

Let the following symmetric matrix $A = \left[ \matrix{a_{12}+a_{13} & -a_{12} & -a_{13} \\ -a_{12} & a_{12}+a_{23} & -a_{23} \\ -a_{13} & -a_{23} & a_{13}+a_{23} } \right]$,

where each $a_{ij}$ is a nonnegative real number, and hence, $A$ is a symmetric positive semidefinite matrix, because:

$ x^T A x = (a_{12}+a_{13}) x_{1}^2 + (a_{12}+a_{23}) x_{2}^2 + (a_{13}+a_{23}) x_{3}^2 - 2( a_{12} x_1 x_2 + a_{13} x_1 x_3 + a_{23} x_2 x_3 ) \\ = a_{12}(x_1 - x_2)^2 + a_{13}(x_1 - x_3)^2 + a_{23}(x_2 - x_3)^2 \geq 0 $

On the other hand:

Let $B = A + D = \left[ \matrix{a_{12}+a_{13} & -a_{12} & -a_{13} \\ -a_{12} & a_{12}+a_{23} & -a_{23} \\ -a_{13} & -a_{23} & a_{13}+a_{23} } \right] + \left[ \matrix{d_{11} & & \\ & d_{22} & \\ & & d_{33} } \right]$,

where $d_{ii} \in \mathbb{R}$, that is, $D$ is a diagonal matrix with positive and negative real numbers.

What are the limits of $d_{ii}$ so that B is still a positive semidefinite matrix?

Answer 1

By Sylvester's criterion, $A+D$ is positive semidefinite if and only if all principal minors of $A+D$ are nonnegative. In other words, $A+D$ is PSD iff \begin{aligned} &d_1+a_{12}+a_{13}\ge0,\\ &d_2+a_{12}+a_{23}\ge0,\\ &d_3+a_{13}+a_{23}\ge0,\\ &(d_1+a_{12}+a_{13})(d_2+a_{12}+a_{23})\ge a_{12}^2,\\ &(d_1+a_{12}+a_{13})(d_3+a_{13}+a_{23})\ge a_{13}^2,\\ &(d_2+a_{12}+a_{23})(d_3+a_{13}+a_{23})\ge a_{23}^2\\ \end{aligned} and \begin{aligned} &(d_1+a_{12}+a_{13})(d_2+a_{12}+a_{23})(d_3+a_{13}+a_{23})\\ -&a_{23}^2(d_1+a_{12}+a_{13}) -a_{13}^2(d_2+a_{12}+a_{23}) -a_{12}^2(d_3+a_{13}+a_{23}) -2a_{12}a_{13}a_{23} \ge0. \end{aligned} The region bounded by these surfaces is typically not a translated octant of $\mathbb R^3_+$. Therefore, we cannot find a vector $(d_1',d_2',d_3')$ such that $A+D$ is positive semidefinite if and only if $(d_1,d_2,d_3)\ge(d_1',d_2',d_3')$.

To illustrate, consider the analogous case where $A$ is $2\times2$. If $A$ is nonzero, by scaling $A$, we may assume that $$ A=\pmatrix{1&-1\\ -1&1}. $$ In this case, if $D=\operatorname{diag}(d_1,d_2)$, then $A+D$ is positive semidefinite if and only if $d_1+1\ge0,\ d_2+1\ge0$ and $(d_1+1)(d_2+1)\ge1$. That is, the feasible region of $(d_1,d_2)$ is the region above the upper right branch of the hyperbola $(d_1+1)(d_2+1)\ge1$. The hyperbola simply hasn't any "bottom left corner" $(d_1',d_2')$ that is entrywise less than or equal to all $(d_1,d_2)$ in the feasible region.

Answer 2

Note that $A$ is positive semidefinite is not positive definite. In other words, $A$ is positive semidefinite and singular.

First, note that if all three $d_{ii}$ are positive, then $A + D$ will necessarily fail to be positive semidefinite.

So, we must suppose that at least on of these is zero. Without loss of generality, suppose that $d_{33} = 0$. If both $d_{11},d_{22}$ are non-zero, then we find that $A + D$ can only be positive semidefinite if $A$ is diagonal with $a_{33} = 0$. In this case, this only occurs when $A = 0$.

For the remaining case, we must suppose that one of $d_{11},d_{22}$ are zero. Without loss of generality, suppose that $d_{22} = 0$. In other words, we are looking for the maximal value of $d_{11}$ for which $$ A - \pmatrix{d_{11} & 0 & 0\\0 &0 &0\\0 &0&0} $$ is positive semidefinite. As is shown here, for instance, this matrix will be positive definite for $d_{11} \leq 1/A^+_{11}$, where $A^+_{11}$ denotes the $1,1$ entry of the Moore-Penrose pseudoinverse $A^+$ of $A$.

---

As we established above, it is sufficient to consider the case in which at most one of the $d_{ii}$ are non-zero, since $A + D$ will fail to be positive semidefinite otherwise. We compute (via matlab) $$ A^+ = \left(\begin{array}{ccc} \frac{4\,b_{1}+b_{2}+b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)} & -\frac{2\,b_{1}+2\,b_{2}-b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)} & -\frac{2\,b_{1}-b_{2}+2\,b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)}\\ -\frac{2\,b_{1}+2\,b_{2}-b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)} & \frac{b_{1}+4\,b_{2}+b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)} & -\frac{2\,b_{2}-b_{1}+2\,b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)}\\ -\frac{2\,b_{1}-b_{2}+2\,b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)} & -\frac{2\,b_{2}-b_{1}+2\,b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)} & \frac{b_{1}+b_{2}+4\,b_{3}}{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)} \end{array}\right) \\ = \frac{1}{9(b_1b_2 + b_1 b_3 + b_2 b_3)}\sum_{i=1}^3b_i\,(-2e_i + e_{i+1} + e_{i+2})(-2e_i + e_{i+1} + e_{i+2})^T, $$ where in the above we take $b_{1} = a_{23}, b_2 = a_{13},b_3 = a_{12}$. In the second line, $e_i$ denotes the $i$th standard basis vector and addition in the indices is modulo $3$.

We see then, for instance, that the maximal $d_{11}$ for which $A + D$ is positive semidefinite is given by $$ d_{11} = \frac{9\,\left(b_{1}\,b_{2}+b_{1}\,b_{3}+b_{2}\,b_{3}\right)}{4\,b_{1}+b_{2}+b_{3}}. $$ Similar conditions hold for $d_{22},d_{33}$.