$\frac{1+m_v}{1+m_u}\leq \frac{1+u^T(M+I)^{-1} u}{1+v^T(M+I)^{-1}v} \leq \frac{1+m_u}{1+m_v}$ if $M$ is positive sym. PD & $u,v$ are $0-1$ vectors?

Question

Let $n$ be a positive integer. Let $m_u,m_v \in \{1,...,n-1 \}$.

Let $M$ be a $n \times n$ symmetric positive definite matrix with positive entries.

Let $u$ and $v$ be vectors of length $n$ with entries consisting $n-m_u$ (or $n-m_v$) $0$'s and $m_u $ (or $m_v$) $1$'s. Sort $u$ so that the first $n-m_u$ entires of $u$ are $0$'s and the last $m_u$ entries are $1$'s. Sort $v$ in the same way.

Is the following statement true for all $n$?

1. If $m_v<m_u$, then \begin{align*} \frac{1+m_v}{1+m_u} \leq \frac{1+u^\top(M+I_n)^{-1} u}{1+v^\top(M+I_n)^{-1} v} \leq \frac{1+m_u}{1+m_v} \end{align*}
2. If $m_v>m_u$, then \begin{align*} \frac{1+m_u}{1+m_v} \leq \frac{1+u^\top(M+I_n)^{-1} u}{1+v^\top(M+I_n)^{-1} v} \leq \frac{1+m_v}{1+m_u} \end{align*}

Note

This question was motivated by another question of mine. It contains somewhat lengthly motivation of why I would like to show the inequalities above.

Finding so far

I initially thought a sharper bound by $1$ might be possible, but it was not. Suppose $m_v<m_u$. It is not guaranteed that $u^\top(M+I_n)^{-1} u -v^\top(M+I_n)^{-1} v \geq 0$. For instance, consider the example provided here with the matrix $$M = \begin{bmatrix} 1 & 1 & 1\\ 1 & 100 & 99\\ 1 & 99 & 100\\ \end{bmatrix}, \\ $$ and the vectors $u = (0, 1, 1)$ and $v =(0, 0, 1)$.

This means that the sharper lower bound by $1$: \begin{align*} \frac{1+m_v}{1+m_u} < 1 \leq \frac{1+u^\top(M+I_n)^{-1} u}{1+v^\top(M+I_n)^{-1} v} \end{align*} is not possible. However, the proposed bounds by $\frac{1+m_v}{1+m_u}$ and $\frac{1+m_u}{1+m_v}$ still work with the $M$, $u$, and $v$ in the example above.

Answer 1

It doesn't hold.

Here is a counterexample for the right inequality in the first line.

Let $m_u = m+1$ and $m_v=m$. Let the matrix $M$ be diagonal with $M_{ii} = a$ for all diagonal entries, except for $M_{ii} = b$ for the $(m+1)$-last entry. If positive entries of the matrix are required, all other elements can be filled with extremely small positive numbers. We can show the effect with the diagonal matrix. Based on the obtained effect, a concrete counterexample without the diagonality conditions will be given below.

For the proposed diagonal matrix, the right inequality in $$ \begin{align*} \frac{1+m_v}{1+m_u} \leq \frac{1+u^\top(M+I_n)^{-1} u}{1+v^\top(M+I_n)^{-1} v} \leq \frac{1+m_u}{1+m_v} \end{align*}$$ demands that we need to have $$ \begin{align*} \frac{1+\frac{m}{1+a} + \frac{1}{1+b}}{1+\frac{m}{1+a}} \leq \frac{1+m+1}{1+m} \end{align*}$$ Clearing denominators gives $$ \begin{align*} ({1+\frac{m}{1+a} + \frac{1}{1+b}})(1+m) &\leq ({1+\frac{m}{1+a}}) ({1+m+1})\\ m + \frac{m}{1+a} + \frac{1}{1+b} + m (\frac{m}{1+a} + \frac{1}{1+b}) &\leq m + \frac{m}{1+a} + 1 + \frac{m}{1+a} ( m+1) \\ \frac{1}{1+b} + \frac{m}{1+b} &\leq 1 + \frac{m}{1+a} \\ 1+a + m(1+a) &\leq (1+a)(1+b) + m(1+b) \\ m(a-b) &\leq (1+a)b \end{align*}$$

Now let $a>b$, then the inequality only holds for $$ m \leq \frac{ (1+a)b}{a-b} $$ However, a large enough $m$ can be easily constructed which violates this condition. The RHS doesn't have to be large: as an example, let $a=1000$, $b < 1$, the the RHS approximately equals $b$. So the violation can in those cases even be observed for small $m$.

With these considerations, we can now give a concrete counterexample without the diagonality conditions. Indeed, as we have just seen we have $m<<1$ for $a=1000$, $b << 1$, which will be violated even for $m=1$. This allows to construct the following counterexample: Let $$ M = \begin{bmatrix} 1000 & 0.0001 & 0.0001 \\ 0.0001 & 0.1 & 0.0001 \\ 0.0001 & 0.0001 & 1000 \end{bmatrix}, \\ $$ and as in the other counterexample, $u = (0, 1, 1)$ and $v = (0, 0, 1)$. Then, evaluating the numbers we need to have that

$$ \begin{align*} \frac{1+u^\top(M+I_n)^{-1} u}{1+v^\top(M+I_n)^{-1} v} = \frac{1+0.91}{1+0.001} \leq \frac{1+2}{1+1} = \frac{1+m_u}{1+m_v} \end{align*}$$

which is clearly wrong.