Quadratic form with an absolute lower bound on integer vectors: Conditions for semidefinite matrices

Question

Assume that $X\in \mathrm{PSD}(n)$ is a symmetric, positive semi-definite matrix with real entries and $C>0$ is a positive real number. If $X$ satisfies $$ \forall \alpha\in\mathbb{Z}^n\setminus\{0\},\qquad \alpha^T X \alpha \geq C, $$ then is it true that $X$ is positive definite? That is, if $X$ is lower bounded on integer vectors, is it true that it is lower bounded on whole $\mathbb{R}^n$? Can we give a concrete lower bound for $\lambda_{\min}(X)$ in terms of $C,n$ and $\lambda_{\max}(X)$?

The way I understand, the problem is closely related to approximations of real vectors with rational numbers: Simultaneous version of the Dirichlet's approximation theorem implies that if $v\in\mathbb{R}^n$ is a real vector and $N>0$ is a natural number, then there exists a rational vector $\beta\in\mathbb{Q}^n$ such that $$ \beta=\Big(\,\frac{p_1}{q},\, \frac{p_2}{q},\,\dots,\,\frac{p_n}{q}\,\Big)\; \text{ with }\;1\leq q\leq N\qquad\text{and}\qquad \Vert v-\beta\Vert <\frac{\sqrt{n}}{q N^{1/n}}. $$ Note that $\beta^T X \beta \geq \frac{C}{q^2}\geq \frac{C}{N^2}$. Since $\Vert v-\beta\Vert < \frac{\sqrt{n}}{q N^{1/n}}$ and $\beta^T X\beta\geq \frac{C}{N^2}$, I guess that choosing a large enough $N$ (relative to $\lambda_{\max}(X)$?) should guarantee that $v^T Xv> 0$.

Above, I am not using the sharpest bound so maybe Dirichlet's theorem might be an overkill.

Answer 1

Given $X \succeq 0$ and $C>0$,

$$\color{blue}{\forall \alpha\in\mathbb{Z}^n\setminus\{0\},\, \alpha^T ( X)\alpha \geq C \Rightarrow \, X \succ 0}.$$

Proof. If $X \succeq 0$, but $X \nsucc 0$, then there is a non-zero point $\beta\in\mathbb{R}^n\setminus\{0\}$ such that $\beta^T ( X)\beta=0.$ Thus, $\alpha^T ( X)\alpha$ is zero on the line $\alpha=t\beta, \, t\in\mathbb{R}$. Then, we have (see Lemma 1)

$$\sqrt{C}-0\le \sqrt{\alpha_\delta^T X\alpha_\delta} -\sqrt{(t_\delta\beta)^T X(t_\delta\beta)} \le \sqrt{\lambda_{\max}(X)} \|\alpha_\delta-t_\delta\beta \|_2 \le \sqrt{\lambda_{\max}(X)} \delta $$

where $\alpha_\delta \in\mathbb{Z}^n\setminus\{0\}$ and $t_\delta \in\mathbb{R}$ are chosen such that $\|t_\delta\beta-\alpha_\delta \|_2 \le \delta$, proven to exist in Lemma 2. If $\lambda_{\max}(X)=0$, the above gives a contradiction, and if $\lambda_{\max}(X)>0$, for $\delta < \sqrt{\frac{C}{\lambda_{\max}(X)}}$, we have a contradiction. Consequently the implication holds.

---

Lemma 1. $$\sqrt{\alpha^T X\alpha} -\sqrt{\beta^T ( X)\beta} \le \sqrt{(\alpha-\beta)^T X(\alpha-\beta)} \le \\ \sqrt{\lambda_{\max}(X)} \|\alpha-\beta \|_2 $$

Proof. The left inequality follows from that $\sqrt{\alpha^T X\alpha}$ is a semi-norm for $X \succeq 0$. The right inequality is obtained from the following inequality for a symmetric matrix $X$: $$\lambda_{\min}(X) \alpha^T \alpha \le \alpha^T X\alpha \le \lambda_{\max}(X) \alpha^T\alpha.$$

Lemma 2. Given $\beta \in\mathbb{R}^n\setminus\{0\}$, for any $\delta>0$, there is an integer vector $\alpha_\delta \in\mathbb{Z}^n\setminus\{0\}$ and $t_\delta \in \mathbb R$ such that $$\|\alpha_\delta-t_\delta\beta \|_2 \le \delta;$$ in other words, there are integer vectors that have arbitrarily small Euclidian distances to some points on the line $t\beta, t\in \mathbb R$.

Proof. It follows from the simultaneous version of the Dirichlet's approximation theorem, stated also in the OP, by setting $t_\delta=q$ and $\alpha_\delta=p$ where the rational vector $\frac{1}{q}p$ is obtained to approximate $\beta$ for $N$ satisfying $$\frac{\sqrt{n}}{ N^{1/n}} \le \delta, \frac{1}{ N^{1/n}N} < \|\beta\|_\infty=\max_{i\in[n]}|\beta_i|.$$ The latter is required to guarantee that $p\neq0$.

Answer 2

Suppose for a contradiction that the matrix $X$ is not positive definite. As far as I remember, then there exist natural $m<n$ and linear maps $f_1,\dots,f_m:\mathbb R^n\to\mathbb R$ such that $v^TXv=\sum_{i=1}^m f_i(v)^2$ for each $v\in\mathbb R^n$. Put $$M=\sup \{|f_i(v)|:v\in\mathbb R^n,\,\|v\|\le 1,\,i\in\{1,\dots,m\}\}.$$ Define a map $f:\mathbb R^n\to\mathbb R^m$ such that for each $v\in\mathbb R^n$ and each natural $i\le m$, the $i$th component of the vector $f(v)$ is $f_i(v)$. Pick any positive $c<C$ and put $K_m=\left[0,\sqrt{\frac{c}{m}}\right]^m$. For any natural number $N$ put $I_N=\{-N,-N+1,\dots,N-1,N\}^n\subset\mathbb R^n$. Then $f(N)$ is contained in the cube $J_N=[-MN,MN]^m\subset R^m$. Put $L=\left\lceil 2N\sqrt{\frac{m}{c}}\right\rceil$. Then there exists a subset $A_N$ of $\mathbb R^n$ such that $|A_N|\le (NL)^m$ and $J_N\subset A+K_m$. So if $ (2N+1)^n>(LN)^m$ then by the pigeonhole principle there exist $a\in A_N$ and distinct $\alpha,\alpha'\in I_N$ such that $f(\alpha),f(\alpha')\in a+K_m$. Then $$|f_i(\alpha-\alpha')|=|f(\alpha)_i-f(\alpha')_i|\le\sqrt{\frac{c}{m}}$$ for each natural $i\le m$. Then $\beta=\alpha-\alpha'\in\mathbb Z^n\setminus\{0\}$ and $$\beta^TX\beta=\sum_{i=1}^m f_i(\beta)^2\le m\cdot \frac{c}{m}=c<C,$$ a contradiction.