# Interval bounds for symmetric doubly-stochastic matrices (designed with Metropolis weights).

I'm facing an unusual problem with doubly-stochastic matrices, in the context of some undirected graph. I assume that it is connected, but this is not so important for this problem.

Let me introduce the problem. I assume I have an undirected graph; each agent has degree $d_i$ and a neighbor set $\mathcal{N}_i$. Correspondingly, we define a symmetric doubly-stochastic matrix $W=[w_{ij}]$ by:

\begin{equation*}\label{eq:N} w_{ij} := \left\{ \begin{array}{ll} \frac{1}{\max\{d_i, d_j\}+1} & \text{if} \: j \in \mathcal{N}_i, \\ 1-\sum_{j\in\mathcal{N}_i}w_{ij} & \text{if} \: j=i, \\ 0 & \text{otherwise}. \end{array} \right. \end{equation*} These are the so called Metropolis weights, and it is easy to check that $W$ is indeed symmetric doubly stochastic. It is generally known that the eigenvalues $\lambda$ are in the interval $(-1,1]$ for any doubly-stochastic matrix. But, here comes the thing, I want to show the following:

Prove that the eigenvalues $\lambda$ are in $[-\frac{1}{2},1]$, whether the graph is connected or not.

Now this is an unusual thing to show, I know that. Unfortunately, Gershgorin theorem won't work for me. You may wonder at this point if this may actually be true, well, I checked it with matlab for over $10\:000$ randomly computed graphs with $100$ nodes, either connected or not and with all kinds of amount of edges. There was no case where there was even some eigenvalue $\lambda<-0.4$ ...

A property that might be useful: $$w_{ii}\geq \frac{1}{d_i}\geq \frac{1}{\max\{d_i, d_j\}+1}=w_{ij},$$ for any $j \in \mathcal{N}_i$. Then I hope to show that the matrix $$Q:=W+cI$$ is nonsingular for any $c>0.5$. This would prove the statement. I attempted this by showing that the $LU$-decomposition $LU = Q$ gives a matrix $U$ with a positive diagonal. Something I also observed with the help of Matlab ofcourse. This is exactly were I got stuck and I hope that somebody has some out of the box ideas that can bring me any further.

edit: $LU$-decomposition should be on $Q$ of course.