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})$


1 Answer 1


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})$$

  • $\begingroup$ 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? $\endgroup$
    – vidyarthi
    Jul 20, 2020 at 16:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – Rajesh D
    Jul 20, 2020 at 16:22
  • $\begingroup$ also write $2\cos{\theta} = e^{2\pi i\theta} + e^{-2\pi i\theta}$ $\endgroup$
    – Rajesh D
    Jul 20, 2020 at 17:12
  • $\begingroup$ 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? $\endgroup$
    – vidyarthi
    Jul 20, 2020 at 17:26
  • 1
    $\begingroup$ @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$ $\endgroup$
    – Rajesh D
    Jul 20, 2020 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.