<s>[INST] Sum of a diagonal matrix and a symmetric positive semidefinite matrix 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?
 [/INST] 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.
</s>