# $\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?

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, 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. 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.

• You've been asking a lot of similar questions (for instance this one and this one). Perhaps instead of asking about these specific inequalities, it would be more effective to ask about the problem that is motivating you to look for these inequalities. – Omnomnomnom Aug 13 '19 at 15:43
• @Omnomnomnom This question contains my lengthly motivation to show these inequalities. I'm relatively new to this cite and was not sure if I should shorten the original question by just asking the inequalities above or if I should ask a separate question here. What do you suggest? – kx526 Aug 13 '19 at 15:51
• thanks for that. I think that you have taken the right approach, good luck. – Omnomnomnom Aug 13 '19 at 15:53

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.