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} &amp; \text{if} \: j \in \mathcal{N}_i, \\
  1-\sum_{j\in\mathcal{N}_i}w_{ij} &amp; \text{if} \: j=i, \\
  0 &amp; \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&lt;-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&gt;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.
The Metropolis weights are analyzed in this paper http://web.stanford.edu/~boyd/papers/pdf/avg_metropolis.pdf. See Proof of Lemma 1 in Section 3.2
The Metropolis weights are analyzed in this paper http://web.stanford.edu/~boyd/papers/pdf/avg_metropolis.pdf. See Proof of Lemma 1 in Section 3.2