2
$\begingroup$

Let $A,D \in \mathbb{R}^{n\times n}$ be two positive definite matrices given by

$$ D = \begin{bmatrix} 1 & -1 & 0 & 0 & \dots & 0\\ -1 & 2 & -1 & 0 & \dots & 0\\ 0 & -1 & 2 & -1 & \dots & 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & 0\\ 0 & \dots & 0 & -1 & 2 & -1\\ 0 & 0 & \dots & 0 & -1 & 1 \end{bmatrix}, \quad A = \begin{bmatrix} c_{1,2} & -c_{1,2} & 0 & 0 & \dots & 0\\ -c_{2,1} & c_{2,1} + c_{2,3} & -c_{2,3} & 0 & \dots & 0\\ 0 & -c_{3,2} & c_{3,2} + c_{3,4} & -c_{3,4} & \dots & 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & 0\\ 0 & \dots & 0 & -c_{n-1,n-2} & c_{n-1,n-2} + c_{n-1,n} & -c_{n-1,n}\\ 0 & 0 & \dots & 0 & -c_{n,n-1} & c_{n,n-1} \end{bmatrix} $$ with $c_{i,j} = c_{j,i} \in (0,c_+]$ for all $i,j=1,\dots,n$ for a $c_+ \in (0,\infty)$.

I would like to prove that independent of the dimension of $n$ $$x^\top A x \le c_+ x^\top D x$$ holds for all $x\in \mathbb{R}^n$. If this is not the case does there exist a counter example?

This is somehow related to that the norms of the induced scalar products of the matrices $A$ and $D$ are equivalent with factor $c_+$.

New contributor
Luna947 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

2 Answers 2

2
$\begingroup$

For $i=1,\dots,n-1$, let $a_i:=c_+-c_{i,i+1}\ge0$. Then, by straightforward calculations with a bit of re-arranging, for $x=(x_1,\dots,x_n)\in\mathbb R^n$ we have $$c_+ x^\top D x-x^\top A x =\sum_{i=1}^{n-1}a_i(x_{i+1}-x_i)^2\ge0.$$

So, your conjectured inequality, $x^\top A x \le c_+ x^\top D x$, is true.

$\endgroup$
1
  • $\begingroup$ Thank you for the answer! I was able to re-calculate your estimations. That totally answered my question. $\endgroup$
    – Luna947
    Jun 23 at 13:02
0
$\begingroup$

This seems a counterexample: $c_+=1$ (which you can assume without loss of generality), $n=2$, $A = \begin{bmatrix}2 & -\varepsilon \\\ -\varepsilon & 2\end{bmatrix}$, $x = \begin{bmatrix}1 \\ 1\end{bmatrix}$ gives $x^*Dx=2, x^*Ax = 4 - 2\varepsilon$, so the inequality is reversed.

This is not just a wrong sign, since $x = \begin{bmatrix}1 \\ -1\end{bmatrix}$ gives an inequality with the opposite sign. There just does not seem to be an inequality of that kind valid for every $x$.

$\endgroup$
2
  • $\begingroup$ Thank you so much for your answer and the counterexample. Obviously, I was too sloppy in formulating the matrix A, so I edited it. I think in this case, unfortunately the your example does not fit. $\endgroup$
    – Luna947
    Jun 23 at 11:25
  • $\begingroup$ OK. Please take some time to review your questions in the future. $\endgroup$ Jun 23 at 13:18

Your Answer

Luna947 is a new contributor. Be nice, and check out our Code of Conduct.

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.