1
$\begingroup$

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 $$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – kx526 Aug 13 at 0:10
  • 1
    $\begingroup$ @kenex I have edited the answer. As you can see it doesn't really matter since it easily generalises. $\endgroup$ – Niki Di Giano Aug 13 at 0:12
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the comment! Indeed, $m_n, m_v <n$. Sorry for the confusion, I edited my question. $\endgroup$ – kx526 Aug 12 at 23:38
  • 1
    $\begingroup$ 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$. $\endgroup$ – yjnt Aug 12 at 23:40
  • 1
    $\begingroup$ I see. I will edit the question to a weak inequality which I am still interested in showing. Thank you. $\endgroup$ – kx526 Aug 12 at 23:44
  • $\begingroup$ Sorry to bother you again, but would you please help me on this question? $\endgroup$ – kx526 Aug 13 at 17:23
  • $\begingroup$ I saw Niki Di Giano’s answer and he proved that the inequality is false. What is left to prove? $\endgroup$ – yjnt Aug 13 at 17:28
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.