# Finding an analytical upper bound on linear transform of matrix

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}$$

• If $M$ is known to be positive semidefinite, then $TM = M + \alpha J$ where $J$ is all-ones matrix, is rank-one perturbation of $M$ with $\alpha\in(0,1)$. Being sum of positive semidefinite matrices, $TM$ should then always be positive semidefinite. Nov 10, 2022 at 21:03
• Simulposted to m.se with no notice to either site, math.stackexchange.com/questions/4573715/… Nov 10, 2022 at 21:48
• Didn't you just post this question here yesterday? mathoverflow.net/questions/434235/… Nov 10, 2022 at 21:51
• Now you know. But why have you posted it to MO twice? Nov 11, 2022 at 7:11

A result assuming that $$M$$ is positive definite. By continuity, in the optimal $$\alpha$$ the matrix $$M+\alpha D$$ is singular; hence the result is the smallest zero of $$f(\alpha) = \det (M + \alpha D)$$, or, alternatively, of $$g(\alpha) = \det(\frac1{\alpha}I + M^{-1/2}DM^{-1/2})$$. The latter function vanishes when $$\frac{1}{\alpha}$$ is an eigenvalue of $$-M^{-1/2}DM^{-1/2}$$. Hence, $$\alpha = \frac{1}{\lambda_{\max}(-M^{-1/2}DM^{-1/2})}$$. I don't think it can get any more close than this.
• 1. Multiply both sides of $f(\alpha)$ by the non-zero quantity $\det M^{1/2}$. 2. Yes, it is the matrix square root (/not/ elementwise). If you prefer, you can take $B$ such that $M = B^T B$ and multiply on the left by $B^{-T}$ and on the right by $B$ instead and the result is unchanged. 3. Yes, $M^{-1/2}$ is a matrix. Nov 11, 2022 at 9:52
• Sorry -- multiply both sides by $\det M^{-1/2}$, and divide by $\alpha^n$. No determinant lemmas required. As $\alpha>0$ and $\det M^{1/2}\neq 0$, $g(\alpha)$ vanishes only when $f$ does. Nov 11, 2022 at 22:47
• Yes, that works this way, even if that's not clear to me what property you applied to get the last equality. In the version I had in mind, you factor $\frac{1}{\alpha}M+D = M^{1/2}(\frac{1}{\alpha}I + M^{-1/2}DM^{-1/2})M^{1/2}$ and take determinants. Nov 11, 2022 at 23:06