Sum of unstable diagonal matrix with laplacian

I am trying to solve the following problem that seems trivial at first sight but I don't know where to start for a rigorous approach.

Consider the following matrix $M = A - L$ where $A$ is an unstable, nonsingular diagonal matrix (at least one diagonal entry strictly positive) and $L$ is a Laplacian matrix. For the time being we can assume that the Laplacian is unweighted (i.e. all the weights are equal to a certain positive scalar value $k$).

I would like to show (if true) that $M$ has always at least an eigenvalue greater than 0.

From some numerical examples and simple intuition I would say that the matrix $M$ is always unstable but I am not sure how to prove it. For small values of $k$ one can use the Gershgorin theorem but I don't think this might help me for arbitrary values of $k$.

EDIT: Given the fact that this property is not true in general, do you think there might be a less relaxed result? For example a result relative to $\frac{a_1}{|a_2|}> K$ if $a_{1}>0$ and $a_2=a_3=\dots=a_N <0$?

Solution 1:

The statement is not true. As a counterexample, take $$ A = \pmatrix{1\\&-10\\&&-10}, \quad L = \pmatrix{-2&1&1\\1&-2&1\\1&1&-2}. $$ $M = L-A$ is stable with eigenvalues $-13,-6 \pm 3\sqrt{3}$ (the greatest of its eigenvalues is $3\sqrt{3} - 6 \approx -0.8$).

Here, I consider your specific case where we have $$ A = c \cdot \pmatrix{K\\ & -1 \\&& \ddots\\ &&& -1}, \quad c,K > 0. $$ Notably, $A - L$ will be stable if and only if $L - A$ is positive definite. On the other hand, we can express $L - A$ in the form $$ L - A = L + c I - c(K+1)xx^T, $$ where $x$ is the column-vector $x = (1,0,\dots,0)$. With the Schur complement, we can see that $L-A$ will be positive definite if and only if the matrix $$ Q = \pmatrix{L + cI & \alpha x\\ \alpha x^T & 1} $$ is positive definite, where $\alpha = \sqrt{c(K+1)}$. By considering the other Schur complement of this block matrix, we can see that $Q$ will be positive definite if and only if $$ 1 - c(K+1)x^T(L + c I)^{-1}x > 0 \iff x^T(c^{-1}L + I)x < \frac 1{K+1}. $$ Putting it all together, we see that $A - L$ will be stable if and only if the $1,1$ entry of $(c^{-1}L + I)^{-1}$ is smaller than $1/(K+1)$.