Given a (real) positive semi-definite matrix $\underline M$ (with all elements of the principal diagonal equal to $1$) and a transformation $T:\underline A\to \underline A + \alpha \underline D$, with $\alpha \in (0,1)$ and $\underline D$ a hollow matrix with all entries one and principal diagonal $0$ (see *), find the biggest $\alpha$ allowed so that $T\underline M$ is again positive semi-definite.

I am not sure if a closed form analytical solution to this problem could even exist. However, here are some ideas that I had in mind.

**An upper bound that always ensures PSD:**

Let $n=\text{dim}(\underline D)$ and note that $D$ corresponds exactly to the adjacency matrix of the complete graph with $n$-vertices ($1$ denotes a connection and $0$ not). The spectrum of the graph is $\{(-1)^n, (n-1)\}$. Therefore the eigenvalues of $\alpha \underline D$ are $\{ -\alpha,(n-1)\alpha\}$. For PSD we must ensure that all the eigenvalues of $\underline M + \alpha \underline D$ are non-negative, which is the case if the smallest eigenvalue of $\underline M$ is greater than or equal to the "most negative" eigenvalues of $\alpha \underline D$. It then follows:

If $\lambda_{min}\geq \alpha$ then $T\underline M$ is positive semi-definite.

**A naïve attempt**

Since $T\underline M$ is square, the idea is to use *Gershgorin circle theorem* to find the intervals that bound the spectrum. Recalling that $M_{ii} = M_{jj} = 1$ for $i\neq j \in 1:n$, we have that

$$\lambda_i\in I\left(1, \sum_{j\neq i}\vert M_{ij} + \alpha\vert\right).$$ Further, we can impose the restriction to have all eigenvalues lie in a positive interval (i.e. the "left endpoint" must be non-negative): $$ \alpha_{max} = \max\bigcap_{i=1}^n \left\{\alpha \in (0,1): \sum_{j\neq i}\vert M_{ij} + \alpha\vert \leq 1\right\}.$$ However, this makes sense only on the specific case that $\underline M$ is diagonally dominant.

**Empirically**

Running some simulations I have noticed that if all the entries of $\underline M$ are positive, then $\alpha_{max} = \lambda_{\min} + \epsilon$ (for some very small $\epsilon$ - most likely due to some noise). As below

which is not the case if I allow entries to change sign:

in the above plot ($1$ denotes positive semi-definiteness, $0$ not)

(*) For a $3\times 3$ \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}