Bound on the ratio of top 2 eigenvalues

Question

Let $P$ be a $n \times n$ stochastic matrix such that $P_{ij}=\tau$ if $i \neq j$ and $P_{ii} = 1 - (n-1)\tau$ where $0<\tau < \frac{1}{n}$.
It is clear that the largest eigenvalue of $P$ is 1, and the second largest eigenvalue is $(1-n\tau)$, hence $$\frac{\lambda_{2}}{\lambda_{1}} = 1-n\tau \leq 1 - 2\tau.$$ Let $D$ be a $n \times n$ diagonal matrix such that $D_{ii} \geq 1$ for all $i$. Consider the matrix $PD$ and let $\lambda_{1}',\lambda_{2}'$ be the top two eigenvalues. Prove that $$\frac{\lambda_{2}'}{\lambda_{1}'} \leq 1-2\tau.$$ I have verified that it's true for $n=2,3$ by brute force calculations. Also using Horn's inequalities I can find a bound which is much worse. Thanks

Answer 1

I claim that $\lambda_2'/\lambda_1'\leqslant 1-\frac{2\tau}{1-(n-2)\tau}$ which is bit stronger than you ask for. This is sharp as the example $D_{11}=D_{22}=1\gg \max(D_{33},\dots,D_{nn})$ shows.

Of course it is not important that $D_{ii}\geqslant 1$, only that $D_{ii}>0$ (since everything is homogeneous in $D$). We may suppose that all $D_{ii}$'s are distinct, since $\lambda_1'$ and $\lambda_2'$ are continuous with respect to $D$. Denote $D_{ii}=d_i$, $\beta=1-n\tau$, $\rho=\beta/\tau$. Then we should prove that $\lambda_2'/\lambda_1'\leqslant \rho/(\rho+2)$.

Rewriting the eigenvector equation in the form $(\tau J+\beta I)Dx=\lambda x$, for the coordinates $x_i$ of the eigenvector $x$ with eigenvalue $\lambda$ we get $\beta d_ix_i+\tau(\sum_j d_j x_j)=\lambda x_i$. Denote $\mu=\sum d_j x_j$. If $\mu=0$, we get $x_i(\lambda-\beta d_i)=0$ for all $i$, so $\lambda$ must be equal to certain $\beta d_j$ and $x_i=0$ for $i\ne j$. But this contradicts to $\mu=0$. So $\mu\ne 0$, we have $x_i=\tau \mu (\lambda-\beta d_i)^{-1}$ and $$\sum d_i(\lambda-\beta d_i)^{-1}=(\tau \mu)^{-1}\sum d_i x_i=\tau^{-1}.$$ This equation (for $\lambda$) has $n$ roots in total. If $d_1<d_2<\dots<d_n$, by continuity there is unique root between $\beta d_{i-1}$ and $\beta d_i$ and one root on the interval $(\beta d_n,\infty)$.

By homogeneity we may suppose that $\lambda_1'=1$. Then $\beta d_n<1$ and $\lambda_2'\in (\beta d_{n-1},\beta d_n)$. Denote $\beta d_i(1-\beta d_i)^{-1}=\theta_i$, we have $\sum \theta_i=\rho$ and $\beta d_i=\theta_i(1+\theta_i)^{-1}$. Assume on the contrary that $\lambda_2'>\rho/(\rho+2)$, then also $\theta_n/(1+\theta_n)=\beta d_n>\rho/(\rho+2)$, $\theta_n>\rho/2$. Denoting $m=\lambda_2'$ we get $$ \rho=\sum \frac{\beta d_i}{m-\beta d_i}=\sum \frac{\theta_i}{m-(1-m)\theta_i}=- \frac{\theta_n}{m-(1-m)\theta_n}+\sum_{i=1}^{n-1} \frac{\theta_i}{m-(1-m)\theta_i}\leqslant \\ - \frac{\theta_n}{m-(1-m)\theta_n}+\frac{\sum_{i=1}^{n-1} \theta_i}{m-(1-m)\sum_{i=1}^{n-1} \theta_i}= \frac{\theta_n}{m-(1-m)\theta_n}+\frac{\rho -\theta_n}{m-(1-m)(\rho-\theta_n)}=:f(m) $$ (the last denominator is positive since $m/(1-m)>\rho/2>\rho-\theta_n$.) The function $f(m)$ is decreasing between $\alpha:=(\rho-\theta_n)/(1+\rho-\theta_n)$ and $\beta:=\theta_n/(1+\theta_n)$. We have $\alpha<\rho/(\rho+2)<\beta$ and $m\in (\rho/(\rho+2),\beta)$. Therefore $\rho\leqslant f(m)\leqslant f(\rho/(\rho+2))=-(\rho+2)$, a contradiction.