Decomposing a matrix as a sum of a diagonal matrix and a lower-rank matrix Can any Hermitian positive semi-definite (PSD) matrix $H$ be written as $D + R$, where $D$ is a PSD diagonal matrix and $R$ is a Hermitian PSD matrix with $\operatorname{rank}(R) < \operatorname{rank}(H)$? If not, what are the restrictions on H such that it is possible?
As a follow-up question: if we have an $H$ for which this is possible, when does the lower-rank matrix $R$ also satisfy the condition that it can be decomposed as $R=R'+D'$ with a lower-rank $R'$? Essentially, I would like to create a "chain" of such decompositions such that in the end I have $H=R_1+D$ with some diagonal $D$ and $\operatorname{rank}(R_1)=1$. When is this possible?
 A: Let $e_1,\dots,e_n$ denote the standard basis. A sufficient condition is that if $H x = e_i$ has a solution for some $i$, then there exists a $t > 0$ such that $H - te_ie_i^T$ will be positive semidefinite of a lower rank.
I believe that this condition is also necessary, but I'm not sure. 

Proof of necessity: (work in progress) Suppose that $H$ is such that $H - D$ is positive semidefinite for some non-zero diagonal $D$.  That is, the matrix
$$
H- \sum_{i=1}^n d_i e_ie_i^T
$$
is positive semidefinite.  So, if $d_k \neq 0$, then $H - d_k e_ke_k^T$ is positive semidefinite.  This means that  for $0 < t < d_k$,
$H - t e_ke_k^T$ is positive semidefinite.  
(Not sure about this step:) we may therefore state that $H - t e_ke_k^T$ is PSD for $t \in [0,t_{max}]$ for some $t_{max}$, and that $H - t_{max}e_ke_k^T$ is necessarily of lower rank.
A: When $H$ is positive-definite, the answer is yes to your first question. If we write $H$ as 
$$
H=\begin{bmatrix}
h_{11} & \begin{matrix} h_{22}&\cdots&h_{nn}\end{matrix}\\
\begin{matrix}h_{21}\\ \vdots\\ h_{n1}\end{matrix} & H'
\end{bmatrix},
$$
then $H'$ is positive definite (thus invertible). If $E_1=E_{11}$ is the matrix unit with the 1,1 entry equal to $1$ and zero elsewhere, then 
\begin{align}
\det(H+tE_1)&=\det\begin{bmatrix}
h_{11}+t & \begin{matrix} h_{22}&\cdots&h_{nn}\end{matrix}\\
\begin{matrix}h_{21}\\ \vdots\\ h_{n1}\end{matrix} & H'
\end{bmatrix}\\ \ \\
&=\det\begin{bmatrix}
h_{11} & \begin{matrix} h_{22}&\cdots&h_{nn}\end{matrix}\\
\begin{matrix}h_{21}\\ \vdots\\ h_{n1}\end{matrix} & H'
\end{bmatrix}+\det\begin{bmatrix}
 t & \begin{matrix} h_{12}&\cdots&h_{nn}\end{matrix}\\
\begin{matrix}0\\ \vdots\\0\end{matrix} & H'
\end{bmatrix}\\ \ \\
&=\det H+t\det H'.
\end{align}
So, choosing $t_1=-\det H/\det H'$ we get that $R=H+tE_1$ has rank at most $n-1$. Thus
$$
H=-t_1E_1 +R
$$
gives the desired decomposition. 
We cannot expect to be able to iterate this. For instance, the poitive definite matrix 
$$
H=\begin{bmatrix} 3&1&1\\ 1&1&0\\1&0&1\end{bmatrix}
$$
can not be written as "diagonal plus rank one". Indeed, a selfadjoint rank-one operator is of the form $vv^*$. If we had $H=D+vv^*$, we would have 
$$
H=\begin{bmatrix} D_{11}+|v_1|^2&v_1\overline{v_2}&v_1\overline{v_3}\\ \overline{v_1}v_2&D_{22}+|v_2|^2&v_2\overline{v_2}\\ \overline{v_1}v_3&\overline{v_2}v_3&D_{33}+|v_3|^2\end{bmatrix}.
$$
The $2,3$ entry forces either $v_2=0$ or $v_3=0$, but this would make either the $1,2$ or $1,3$ entries equal to zero.
And the above shows that the answer to the original question is "no" for general positive-semidefinite $H$: take 
$$
H=\begin{bmatrix} 2&1&1\\ 1&1&0\\1&0&1\end{bmatrix}.
$$
Then $H$ is rank-2 and (with he same argument as above) cannot be written as diagonal plus rank-one. 
