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)?

  • $\begingroup$ 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? $\endgroup$ – user1551 Nov 15 '12 at 10:10
  • $\begingroup$ @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). $\endgroup$ – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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