1
$\begingroup$

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

enter image description here

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

enter image description here

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}

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Nov 10, 2022 at 21:03
  • 1
    $\begingroup$ Simulposted to m.se with no notice to either site, math.stackexchange.com/questions/4573715/… $\endgroup$ Nov 10, 2022 at 21:48
  • 1
    $\begingroup$ Didn't you just post this question here yesterday? mathoverflow.net/questions/434235/… $\endgroup$ Nov 10, 2022 at 21:51
  • $\begingroup$ Now you know. But why have you posted it to MO twice? $\endgroup$ Nov 11, 2022 at 7:11

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 11, 2022 at 9:52
  • $\begingroup$ 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. $\endgroup$ Nov 11, 2022 at 22:47
  • $\begingroup$ 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. $\endgroup$ Nov 11, 2022 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.