Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, \begin{equation} l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\ -w_{ij} & \mbox{otherwise},\end{cases} \end{equation} ie, off-diagonal entries, which are negative, are summing, in absolute value, to $1$ which resides on the diagonal. Note that the diagonal entries are the only positive entries. From the Gershgorin theorem it follows that the spectra of $L$ is within the range $[0, 2]$, but it is possible to obtain a tighter bound, ie, $[0, 2)$.

Now, suppose a pseudo-Laplacian $K$ is given, defined similarly as $L$, but with $w'_{ij}$ corresponding to arbitrary numbers summing, in absolute value, to diagonal entries $k_{ii}$, $\forall i$, \begin{equation} k_{ij}=\begin{cases} \sum_{i,~ i\neq j} w'_{ij} &\mbox{if } i=j \\ -w'_{ij} & \mbox{otherwise}.\end{cases} \end{equation} So, for both $L$ and $K$, the off-diagonal entries are negative ($w_{ij}$ and $w'_{ij}$ are positive) Let $D=diag(K)$. Can it be shown that the spectrum of $D^{-1}K$ is within the range $[0, 2)$?

My primary intention was to derive a connection between $K$ and $L$, and to then establish spectrum equivalence. Note that for certain $L'\subset L$, $n>2$, having zero off-diagonal entries, the spectrum range includes $2$, ie, $[0, 2]$. A connection between $K$ and $L$ would therefore help establishing a bound on $D^{-1}K$, with $K$ possibly having some zero off-diagonal entries.

share|cite|improve this question
Hey, but $D^{-1}K$ is itself already Laplacian, no? – Berci Oct 11 '12 at 13:50
@Berci Is $D^{-1}K$ a symmetric matrix? – user506901 Oct 11 '12 at 14:07
aand.. does the Gershgorin argument hold only for symmetric matrix? – Berci Oct 11 '12 at 16:09
@Berci what are the bounds? $[0,2]$, or $[0, 2)$ ? – user506901 Oct 11 '12 at 16:17
I don't know. But.. so.. is the question you are interested in is that can $D^{-1}K$ have eigenvalue with $|\lambda|=2$? – Berci Oct 11 '12 at 16:24
up vote 2 down vote accepted

Remember that the Gerschgorin circle theorem (which is valid for any matrix, not just symmetric) states that all eigenvalues lie within the union of all said circles. Otherwise (if any single row described a particular bound for a particular eigenvalue) then a similarity of row scaling by $1\over n$ and the inverse column scaling by $n$ would effectively be able to tighten that bound completely to the element on the diagonal. That is effectively saying that an eigenvalue is the diagonal element, which of course is absurd. If such $n$ is chosen large, it may diminish the particular circle, but another circle would get larger and the union is not particularly better in the transform.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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