# Tighter bound on a spectrum of a matrix obtained by partial diagonal shift

A matrix $V\in\mathbb{R}^{n\times n}$ is a full symmetric matrix with negative off-diagonal elements summing (in absolute value) to diagonal elements. Suppose that $V$ has all entries, and let $D=diag(V)$. It is known that the spectrum of $D^{-1}V$ is in the range $[0,2)$.

Let matrix $R$ have non-negative elements (so, some of them might be zero), and let $K=V+diag(R)$. If $L=diag(K)$, what can be said about the spectrum of $L^{-1}K$?

According to Gershgorin, if the diagonal entries of $R$ were all positive, the bound is $(0, 2)$. With non-negative diagonal entries of $R$, the best bound according to Gershgoring is $[0, 2]$. Is there a way to obtain a bound $[0, 2)$ for $L^{-1}K$, with non-negative diagonal entries of $R$ (so, some diagonal entries of $R$ may be zero)?

-
I'm a bit confused. Do you want to show that the spectrum of $L^{-1}K$ lies inside a half-closed, half-open interval $[0,2)$ when $R$ is entrywise nonnegative? –  user1551 Nov 15 '12 at 10:10
@user1551 I would like to show that the spectrum of $L^{-1}K$ is within $[0,2)$ when entries of $diag(R)$ are non-negative (so, either positive or zero). –  user506901 Nov 15 '12 at 12:50

Note that $L^{-1}K = (\textrm{diag}(K))^{-1/2}(\textrm{diag}(K))^{-1/2}K(\textrm{diag}(K))^{-1/2}(\textrm{diag}(K))^{1/2}$. As the spectrum of a matrix is invariant under similarity transform, and the positive semi-definiteness of a real symmetric matrix is preserved by matrix congruence, the above equality shows that $L^{-1}K$ has nonnegative eigenvalues, i.e. the spectrum of $L^{-1}K$ is bounded below by $0$.

If $R=0$ and $V=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$, the eigenvalues of $L^{-1}K=K=V$ are exactly $0$ and $2$. So, $2$ is a sharp upper bound for the spectral radius of $L^{-1}K$ and there is no room of improvement.

If $R$ contains some positive diagonal entries, assume WLOG that the last one is positive. Let $A=2\ \textrm{diag}(K)$ and $B=K$. Then $A-B=2\ \textrm{diag}(K)-K=2\ \textrm{diag}(V)-V+\textrm{diag}(R)$. Let $V_{n-1}$ be the $(n-1)\times(n-1)$ submatrix obtained by deleting the last row and last column of $V$. Since

• $2\ \textrm{diag}(V)-V$ is positive semidefinte (as it is diagonally dominant),
• $\textrm{diag}(R)$ is positive semidefinite,
• $2\ \textrm{diag}(V_{n-1})-V_{n-1}$ is positive definite (as it is strictly diagonally dominant) and
• the last diagonal entry of $R$ is positive,

we see that $A-B$ is positive definite. Now, one result in matrix theory says that if $A$ is a positive definite matrix and $B$ is positive semidefinite, then $A-B$ is positive definite if and only if $\rho(A^{-1}B)<1$ (here $\rho(\cdot)$ denotes spectral radius). See, e.g., Theorem 7.7.3 (p.471) of Horn and Johnson (1985), Matrix Analysis, Cambridge University Press, New York. So we have $\rho(A^{-1}B) = \rho\left(\frac12L^{-1}K\right) < 1$. Hence the spectrum of $L^{-1}K$ lies inside $[0,2)$ in this case.

Edit: By a similar argument to the four bullet points in the above, we see that when $R$ has at least one positive diagonal entry, $K = V+\textrm{diag}(R)$ is actually positive definite. Hence the first paragraph of this answer shows that $L^{-1}K$ has positive eigenvalues. In other words, the spectrum of $L^{-1}K$ lies inside $(0,2)$, not just $[0,2)$.

-