Prove spectral equivalence of matrices

Question

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_+$.

Answer 1

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.

Answer 2

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