Bound on ratio between largest eigenvalues of a real symmetric matrix with positive entries

Question

For $p\in (0,1]$, denote by $M_n(p)$ the set of real symmetric $n\times n$ matrices $M$ with positive entries, satisfying $$\min_{1\leq i,j,k,l\leq n}\frac{M_{ij}}{M_{kl}}=p.$$ Let $\{\lambda_j(M)\}^n_{j=1}$ denote eigenvalues of $M$ ordered by absolute value in decreasing order$|\lambda_1(M)|\geq |\lambda_2(M)|\geq\ldots\geq|\lambda_n(M)|$. Find $$ f(p)\equiv\sup_{M\in M_n(p)}|\lambda_2(M)/\lambda_1(M)|,$$ or at least an upper bound for this quantity (expressed in terms of $n,p$).

---

Note: It is easy to see that $f(1)=0$, and $\lim_{p\to 0} f(p)=1$ (take the "nearly" identity matrix, for example). Also, consider the matrix $M=\psi\psi^T$, where $\psi^T=(1,q,q^2,\ldots,q^{n-1}),~q=p^{\frac{1}{2n-2}}$, so that $M\in M_n(p)$ and $|\lambda_2(M)/\lambda_1(M)|=0$, so the lower bound is trivially zero $$ \inf_{M\in M_n(p)}|\lambda_2(M)/\lambda_1(M)|=0.$$ I'm curious if anyone can prove an upper bound that is smaller than 1.

Answer 1

Note that the ratio of the two eigenvalues is invariant by scaling $M$ by a positive factor. Therefore we may modify the definition of $M_n(p)$ to assume that the largest element of every $A\in M_n(p)$ is $1$ and the smallest element is some $p\in(0,1]$. Let $B$ be the leading principal $(n-1)\times(n-1)$ submatrix of $A$. By Cauchy's interlacing inequality, the maximum possible value of $\frac{\rho(B)}{\rho(A)}$ serves as an upper bound of $\frac{|\lambda|_2(A)}{|\lambda|_1(A)}$.

Now, on one hand, since $A$ is nonnegative, for any given $B$, $\rho(A)$ is always minimised when the entries on the last row and the last column of $A$ are minimised, i.e. when the last row and the last column are filled with $p$s. On the other hand, when the last row and the last column are filled with $p$s, $\rho(B)$ is maximised when all entries of $B$ are equal to $1$.

Therefore, $\rho(B)/\rho(A)$ is maximised when $$ A=\pmatrix{1&\cdots&1&p\\ \vdots&&\vdots&\vdots\\ 1&\cdots&1&\vdots\\ p&\cdots&\cdots&p} =pee^T+(1-p)vv^T, $$ where $v=(1,\ldots,1,0)^T$. For this $A$, we have $\rho(B)=n-1$ and $$ \rho(A)=\frac{np+(n-1)q + \sqrt{\left[np-(n-1)q\right]^2 + 4(n-1)^2pq}}{2}, $$ where $q=1-p$. It follows that $$ \frac{|\lambda|_2(A)}{|\lambda|_1(A)} \le\frac{\rho(B)}{\rho(A)} \le\frac{2(n-1)}{np+(n-1)q + \sqrt{\left[np-(n-1)q\right]^2 + 4(n-1)^2pq}}.\tag{1} $$ Since the RHS of $(1)$ is the maximum possible value of $\rho(B)/\rho(A)$, it is always $\le1$. This bound is quite loose, however, because $|\lambda|_2(A)$ can be significantly smaller than $\rho(B)$. In particular, when $p=1$, we have $A=ee^T$ and hence $|\lambda|_2(A)/|\lambda|_1(A)=0$, but the upper bound we obtained in the above is $(n-1)/n$.

To compensate for the poor performance when $p$ is close to $1$, we give another upper bound. Let $A=pee^T+D$, so that $D$ is an entrywise nonnegative symmetric matrix whose maximum element is $1-p$. By Weyl's inequalities, \begin{aligned} \lambda_\min(A) &\ge\lambda_\min(pee^T)+\lambda_\min(D)\ge-\rho(D),\\ \lambda_2^\downarrow(A) &\le\lambda_2^\downarrow(pee^T)+\lambda_\max(D)\le\rho(D). \end{aligned} Since the second largest-sized eigenvalue of $A$ must lie between $\lambda_\min(A)$ and $\lambda_2^\downarrow(pee^T)$, the above two inequalities show that its absolute value must be bounded above by $\rho(D)$. Therefore $$ \frac{|\lambda|_2(A)}{|\lambda|_1(A)} \le\frac{\rho(D)}{\rho(A)} \le\frac{nq}{np} =\frac{q}{p}.\tag{2} $$ So, from $(1)$ and $(2)$ we obtain $$ \frac{|\lambda|_2(A)}{|\lambda|_1(A)} \le\min\left\{ \frac{2(n-1)}{np+(n-1)q + \sqrt{\left[np-(n-1)q\right]^2 + 4(n-1)^2pq}}, \frac{q}{p}\right\}.\tag{3} $$ The bound in $(3)$ is now sharp in the limiting case $p=0$ (with the bound being $1$, which is attained by $A=I$) and in also the case $p=1$ (with the bound being $0$, which is attained by the only member $A=ee^T$ of $M_n(1)$).