Lower bound for smallest eigenvalue of symmetric doubly-stochastic Metropolis-Hasting transition matrix

Question

For my master's thesis research, I stumbled upon a question concerning the Metropolis-Hasting transition matrix $W$.

Context $\quad$ Let me start with some context. I consider connected undirected graphs $G=(V,E)$; here $V=\{1,\ldots, M\}$ and $E$ is the edge set. I denote the neighbor sets by $\mathcal{N}_i$ and the degree of each node by $d_i$. In this context, I consider the Metropolis-Hasting transition matrix $W=[w_{ij}]$, defined 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*} It is known that this matrix is symmetric doubly stochastic, such that we have real eigenvalues $1=\lambda_1>\lambda_2\geq \cdots\geq \lambda_M > -1$.

Question $\quad$ Now, i would like to show a sharper lower bound for $\lambda_M$, namely: $$\lambda_M\geq-\frac{1}{2}.$$

I don't know if this is true actually, but I considered (in Matlab) many randomly produced graphs with $M=100$. I varied the amount of edges from $0.05k_\max$ up to $0.9k_\max$, where $k_\max=\frac{1}{2}(M^2-M)$. In this way I considered over $10\:000$ matrices, and there was no counter example found. Otherwise, if there is a way to find a counter example then that would be helpful as well.

Findings so far $\quad$ I came up with an alternative formulation, using the definition for the field of values. It can be shown that it is equivalent to show that: $$\sum_{i=1}^M\left( \: \sum_{j\in \mathcal{N}_i} \frac{x_i^2 - x_ix_j}{\max\{d_i,d_j\}+1} \right) = \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \frac{3}{2},$$ for any $x = [x_i] \in \mathbb{R}^M$ with $x^Tx =\sum_{i=1}^Mx_i^2=1$. Here the equality sign is not to difficult to prove, but the upper bound is. Does this maybe bring any ideas to mind for somebody? I got stuck here and could really use some help!

---

Edited on June 1, 2016 $\quad$ I am still working on this problem and this is what I am at now. So obviously, I want to relate the problem to relevant graph matrices and in the specific case that $d := d_1 = d_2 = \cdots = d_M$ this is easy. Namely, we can write $W$ as:

$$W = I - \tilde{D}^{-\frac{1}{2}}L\tilde{D}^{-\frac{1}{2}} = I - \tilde{D}^{-1}L, \quad \text{with} \quad \tilde{D} = D + I.$$ In this specific case we simply have $\tilde{D}=(d+1)I$. In all other cases (arbitrary $d_i$), I hope to show that either: $$(i) \quad x^TWx \geq 1 - x^T\tilde{D}^{-\frac{1}{2}}L\tilde{D}^{-\frac{1}{2}}x,$$ or: $$(ii) \quad x^TWx \geq 1 - x^T\tilde{D}^{-1}Lx, \quad$$ for all $x$ with $\sum_{i=1}^Mx_i^2=1$ and $\sum_{i=1}^Mx_i = 0$. This equivalent to showing that either: $$(i) \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \sum_{(i,j)\in E} \left(\frac{x_i}{\sqrt{d_i+1}}-\frac{x_j}{\sqrt{d_j+1}}\right)^2 $$ or: $$(ii) \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} \leq \sum_{(i,j)\in E} \left(\frac{x_i^2-x_ix_j}{d_i+1}+\frac{x_j^2 - x_ix_j}{d_j+1}\right) $$ By the way, you are free to consider edges in $E$ as either $(i,j)$ or $(j,i)$, so you may assume w.l.o.g. that: $$\sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{\max\{d_i,d_j\}+1} = \sum_{(i,j)\in E} \frac{(x_i-x_j)^2}{d_i+1},$$ where $d_i\geq d_j$ for each edge. Unfortunately, element-wise comparison for both (i) and (ii) does not work for any $x$ that satisfies the constraints.

edit some plus and minus signs are corrected

Answer 1

One way of obtaining a simple lower bound (strictly larger than $-1$) is the following: consider the Gershgorin circles $G_i$ given by $$G_i = \left\{z \in \mathbb{C} : |z - W_{ii}| \le R_i \right\}$$ where $R_i$ are the off-diagonal absolute row sums of $W$. Since the elements of $W$ are all non-negative, it follows that $$ R_i = \sum_{j \in \mathcal{N}_i} \frac{1}{\max\{d_i, d_j\} + 1} \le \sum_{j\in\mathcal{N}_i} \frac{1}{d_i + 1} = \frac{d_i}{d_i+1}.$$ Moreover $W_{ii} = 1 - R_i$ from which it follows that $$\lambda \in \bigcup_{i=1}^m [1 - 2R_i, 1] \subset \left[-\frac{d_\text{max} - 1}{d_\text{max} + 1}, 1\right].$$

This bound is not very sharp though. Consider for instance $d_1 =\ldots = d_m = m - 1$, then $W$ has eigenvalues $$\lambda_1 = 1, \lambda_2 = \ldots = \lambda_{m} = 0,$$ however the lower bound tends to $-1$ as $m$ gets larger.

Answer 2

Here is the relief to my question: It is (unfortunately for me) simply not true. As mentioned by Ronn3y, there is always a lower bound of $-\frac{d_\max-1}{d_\min+1}$ but there exists an example for which the the bound is sharp. Consider a complete bipartite graph with two sets of $d$ vertices (so each vertex has a common degree $d=d_\min=d_\max$), then the Metropolis-Hasting matrix is given by: \begin{equation} W = \frac{1}{d+1} \begin{bmatrix} I_d & J_d \\ J_d & I_d \end{bmatrix}, \end{equation} with $I_d, J_d \in \mathbb{R}^{d\times d}$; $I_d$ is the identity matrix and $J_d:=\mathbf{\mathbf{1}_d\mathbf{1}_d^T}$ is the matrix of ones ($\mathbf{1}_d \in \mathbb{R}^d$ is the vector of ones). Then we claim that $\lambda = -\frac{d-1}{d+1}$ is an eigenvalue; first we observe \begin{equation} W - \lambda I = \frac{1}{d+1} \begin{bmatrix} I_d & J_d \\ J_d & I_d \end{bmatrix} + \frac{d-1}{d+1} \begin{bmatrix} I_d & 0_d \\ 0_d & I_d \end{bmatrix} = \frac{1}{d+1} \begin{bmatrix} dI_d & J_d \\ J_d & dI_d \end{bmatrix}. \end{equation} It is straighforward to see that a corresponding eigenvector is given by: \begin{equation} v = \begin{bmatrix} \:\:\mathbf{1}_d \\ -\mathbf{1}_d \end{bmatrix}. \end{equation}