# Bounding the smallest eigenvalue of a matrix generated by a positive definite function

Let $$g:\mathbb{T}\to\mathbb{R}$$ and is given as $$g(x) = \sum\limits_{\eta\in\mathbb{Z}}\frac{1}{1+\gamma \eta^2}\cos{2\pi\eta x}$$

Consider the matrix $$G_{\gamma} = [g(x_i-x_j)]_{1\le i,j\le n}$$

where $$x_1,x_2,...x_n \in (0,1)$$ and pairwise distinct.

Due to Bochner's theorem, $$g(x)$$ is a positive semi definite function and hence $$G_{\gamma}$$ is a psd matrix.

Let $$\lambda_{min}(G_{\gamma})$$ denote the smallest eigenvalue of $$G_{\gamma}$$.

I want to show that $$G_{\gamma}$$ is infact positive definite and as $$\gamma\to\infty$$ $$\lambda_{min}(G_{\gamma}) = \Theta(\frac{1}{\gamma})$$

As a sanity check, I have verified this using numerical computations on some examples.

Motivation : I want to come up with a similar looking formula in a generic dimension, that is for $$\mathbb{T}^m$$. If I am able to prove this for $$m=1$$ dimension, then I will understand the mechanics of it so that might help me to come up with a $$g:\mathbb{T}^m \to \mathbb{R}$$ such that $$\lambda_{min}(G_{\gamma}) = \Theta(\frac{1}{\gamma})$$

Given any $$n$$ distinct points $$\{x_i/x_i\in(0,1)\}$$ which are pairwise distinct. For any $$c_i,i = 1,2,3,...n$$, and not all zeros.

Using the given expression for $$g(x)$$ we can deduce that

$$\sum_{i=1}^n\sum_{j=1}^nc_ic_jg(x_i-x_j) = \sum_{\eta\in\mathbb{Z}} \left(\frac{1}{1+\gamma\eta^2} \left|\sum_{i=1}^n c_i e^{2\pi i \eta x_i}\right|^2 \right)> 0$$

as $$\sum_{i=1}^n c_i e^{2\pi i \eta x_i}$$ does not vanish simultaneously for all $$\eta\in\mathbb{Z}$$ and $$\frac{1}{1+\gamma\eta^2}>0\forall \eta \in\mathbb{Z}$$.

Hence the matrix $$G_{\gamma}$$ is positive definite.

Estimate on $$\lambda_{min}(G_{\gamma})$$ as $$\gamma\to\infty$$

Let $$c = [c_1,c_2,...c_n]$$ be such that $$\|c\|_2 = 1$$. Then $$c^TG_{\gamma}c = \sum_{\eta\in\mathbb{Z}} \left(\frac{1}{1+\gamma\eta^2} \left|\sum_{i=1}^n c_i e^{2\pi i \eta x_i}\right|^2 \right)> 0 .$$ As $$|\sum_{i=1}^n c_i e^{2\pi i \eta x_i}|^2 \le n$$ and we already know $$\sum_{i=1}^n c_i e^{2\pi i \eta x_i}$$ does not vanish simultaneously for all $$\eta\in\mathbb{Z}$$, there exists constants $$K_1$$ and $$K_2$$ such that $$\frac{K_1}{\gamma} \le c^TG_{\gamma}c \le \frac{K_2}{\gamma} \mbox{ }\forall c\in\mathbb{R}^m\ \setminus\{0\}^m \mbox{ and } \|c\|_2 = 1$$

Let $$e(\gamma)$$ be the smallest eigenvector and as $$\|e(\gamma)\|_2 = 1$$ $$\lambda_{min}(G_{\gamma}) = \lambda_{min}(G_{\gamma})e(\gamma)^Te(\gamma) = e(\gamma)^TG_{\gamma}e(\gamma) = \Theta(\frac{1}{\gamma})$$ So

$$\lambda_{min}(G_{\gamma}) = \Theta(\frac{1}{\gamma})$$

• what is $c_i, c_j$ in the sum $\sum_{j=1}^n\sum_{i+1}^nc_ic_jg(x_i-x_j)$? and how did you get the RHS of the sum? Could you eleaborate? – vidyarthi Jul 20 '20 at 16:19
• @vidyarthi : any $c = [c_1,c_2,...c_n] \in \mathbb{R}^n \setminus \{0\}^n$. I will expand the summation later when I get time. Its just an interchange of order of summations and an algebraic manipulation. – Rajesh D Jul 20 '20 at 16:22
• also write $2\cos{\theta} = e^{2\pi i\theta} + e^{-2\pi i\theta}$ – Rajesh D Jul 20 '20 at 17:12
• yes, that is clear, but still, how $$\sum_{i=1}^n\sum_{j=1}^nc_ic_jg(x_i-x_j)=\sum_{i=1}^n\sum_{j=1}^nc_ic_j\sum_{\eta\in\mathbb{Z}}\frac1{1+\gamma\eta^2}cos(x_i-x_j)=2\left(\sum_{\eta\in\mathbb{Z}}\frac1{1+\gamma\eta^2}\left|\sum_{i=1}^nc_ie^{2\pi i\eta x_i}\right|^2\right)$$? Do you have all $c_i,c_j$ positive? – vidyarthi Jul 20 '20 at 17:26
• @vidyarthi no need for positive. You need to work a bit with pen and paper. Hint : $\sum_{i=1}^3\sum_{j=1}^3 c_ic_j = c_1^2 + c_2^2 + c_3^2 + 2c_1c_2 + 2c_2c_3 + 2c_3c_1 = (c_1 + c_2 + c_3)^2$ – Rajesh D Jul 20 '20 at 17:33