2
$\begingroup$

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

$\endgroup$
2

2 Answers 2

3
$\begingroup$

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

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .