# Prove that $x^TA_n x \geq 0$ for all $x$.

Consider the matrix $$A_n \in \mathbb R^{n \times n}$$ whose $$ij$$ entry $$A_n^{ij}$$ is defined as

$$A_n^{ij} = \cases{1 & if i = j \\ \alpha & if \vert i-j\vert = 1 \\ 0 & otherwise.}$$

For which values of $$\vert \alpha \vert < 0.5$$ is the matrix such that $$x^TA_nx \geq 0$$ for all $$x \in \mathbb R^n$$ ?

I tried to compute the eigenvalues and show that they are all greater or equal to $$0$$. However the expression of $$P_n(\lambda ) = \det(A_n-\lambda I)$$ is too complicated to be solved for $$\lambda$$ for larger values of $$n$$. The determinant can be evaluated by using $$P_{n+2}(\lambda) = (1-\lambda)P_{n+1}(\lambda) - \alpha^2 P_{n}(\lambda)$$ with $$P_1 = 1-\lambda$$ and $$P_2 = (1-\lambda)^2- \alpha^2$$.

I also tried (without much success) a more direct approach by trying to directly prove that that $$x^T A_n x \geq 0$$ which is equivalent to

$$2 \alpha \sum_{i = 1}^{n-1} x_i x_{i+1} + \sum_{i = 1}^n x_i^2 \geq 0$$

The critical points of the LHS are in the kernel of $$A$$ however determining if they are minima requires to show that the hessian is positive definite (but the hessian is equal to $$A$$ up to a constant) ...

• I think you want to use Gershgorin's theorem. See here for a similar question. math.stackexchange.com/questions/3150922/…
– Doug
Oct 27, 2023 at 12:56
• The definition of the matrix elements contradict each other. Oct 27, 2023 at 12:58

In your last line, you just have to use Young's inequality which gives $$-2 x_i x_{i+1} \le x_i^2 + x_{i+1}^2$$.

• Could you elaborate on this hint ? I don't see how this solves the problem. Nov 6, 2023 at 13:36
• Just multiply by $\alpha$ and sum over $i$. Your last (desired) inequality follows.
– gerw
Nov 7, 2023 at 15:22

This is a tridiagonal Toeplitz matrix, and the eigenvalues can be computed explicitly. Using the notation from here we have $$a = 1, b = c = \alpha$$ and the eigenvalues are $$a + 2 \sqrt{bc} \cos \left( \frac{k\pi}{n+1}\right) = 1 + 2 |\alpha| \cos \left( \frac{k\pi}{n+1}\right) \, , \, 1 \le k \le n \, .$$

The matrix is positive semidefinite if all eigenvalues are nonnegative, that is if $$2 |\alpha| \cos \left( \frac{\pi}{n+1}\right) \le 1 \, .$$ This is in particular satisfied if $$|\alpha| \le 1/2$$.