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.


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


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.