2
$\begingroup$

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.

  • 0
    @Berci I'm trying to get the bound $[0,2)$ on the eigevalues.2012-10-11

1 Answers 1

2

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.