# Showing $u^T M u \geq v^TMv$ when $M$ is symmetric PD and $u,v$ are $0-1$ vectors

Let $$M$$ be a $$n \times n$$ symmetric positive definite matrix. 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, where $$m_u,m_v \in \{1,...,n-1\}$$. 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. Suppose $$m_u>m_v$$. Is the following weak inequality true?

(As shown below by @Niki Di Giano, this is not true) $$u^T M u \geq v^TMv$$

• I don't think you need all that, I think it is true in general for all the matrices with positive entries – Lucio Tanzini Aug 12 '19 at 23:03
• @LucioTanzini That is absolutely true. Sorry, for the actual question, $X$ does not need to have only positive entries. I corrected the question. – kx526 Aug 12 '19 at 23:08

The matrix $$M$$: $$M = \begin{bmatrix} 1 & 0 & 0\\ 0 & 10 & - 9\\ 0 & -9 & 10\\ \end{bmatrix}$$ Yields $$u^T M u = 2$$ and $$v^T M v = 10$$ for the vectors $$u = (0, 1, 1)$$ and $$v =(0, 0, 1)$$ respectively.

• It is required that the number of $1$'s are strictly below $n$. Is it possible to show a counterexample for that case? Thank you. – kx526 Aug 13 '19 at 0:10
• @kenex I have edited the answer. As you can see it doesn't really matter since it easily generalises. – Niki Di Giano Aug 13 '19 at 0:12

Consider : $$M= \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}, u = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} ^T, v = \begin{bmatrix} 0 & 1 & 1 \end{bmatrix} ^T$$

M is positive definite and : $$u^T M u = v^T M v = 2$$ so it's not a strict inequality (is $$m_u \lt n$$ ?). I couldn't find an example where the inequality is not working though.

• Thank you for the comment! Indeed, $m_n, m_v <n$. Sorry for the confusion, I edited my question. – kx526 Aug 12 '19 at 23:38
• I just checked and if you set $m_u =2$ and $m_v = 1$ you also get 2 so it’s still not working for $m_u \lt n$. – yjnt Aug 12 '19 at 23:40
• I see. I will edit the question to a weak inequality which I am still interested in showing. Thank you. – kx526 Aug 12 '19 at 23:44
• Sorry to bother you again, but would you please help me on this question? – kx526 Aug 13 '19 at 17:23
• I saw Niki Di Giano’s answer and he proved that the inequality is false. What is left to prove? – yjnt Aug 13 '19 at 17:28

Another example where the inequality fails:

The matrix $$\begin{bmatrix}3&-2\\-2&3\end{bmatrix}$$ is positive definite. Also, $$\begin{bmatrix}1\\1\end{bmatrix}>\begin{bmatrix}1\\0\end{bmatrix}$$. But $$\begin{bmatrix}1&1\end{bmatrix}\begin{bmatrix}3&-2\\-2&3\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix}=2<3=\begin{bmatrix}1&0\end{bmatrix}\begin{bmatrix}3&-2\\-2&3\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}$$ which violates the inequality.

• Sorry to bother you again, but would you please help me on this question? – kx526 Aug 13 '19 at 17:24