# How to prove that a function is non-negative definite?

The function I am trying to prove is $$\exp(-2\lvert j-k\rvert)$$.

Here is what I have tried; $$\sum_{j=1}^n \sum_{k=1}^n\ a_j \bar{a_k}\exp(-2\lvert j-k\rvert)$$

=$$\sum_{j=1}^n \sum_{k=1}^n\ a_j \bar{a_k}\exp(-2\lvert j-k\rvert)$$

=$$\sum_{j>k} \ a_j \bar{a_k}\exp(-2j)\exp(2k)+\sum_{k>j} \ a_j \bar{a_k}\exp(2j)\exp(-2k) + \sum_{j=k} \lvert a_j\rvert^2$$

but I am not sure if it is the right path or not.

• I do not understand what you want to prove. Do you claim that $\exp(-2\lvert j-k\rvert)$ is non-negative? Isn't that trivially true? – Gibbs Mar 6 at 13:20
• Since $$e^{-2|\xi|}=\frac1{\pi}\int_{-\infty}^\infty e^{-2i \xi x}\frac{dx}{1+x^2},$$ Bochner's theorem implies that $e^{-2|x|}$ is non-negative definite. – Song Mar 6 at 13:25
• @Gibbs -- Do you know what the definiton of "non-negative definite" is? – uniquesolution Mar 6 at 13:27
• @uniquesolution Probably I misunderstood the question, sorry. – Gibbs Mar 6 at 13:29
• @Song Sorry, I don't know what is the meaning Borel measure, is there other way I can do it? – Davidfufu Mar 6 at 13:38

This answer follows the lines of the proof of Bochner's theorem that I mentioned in the comment. Since $$e^{-2|\xi|}=\frac1{\pi}\int_{-\infty}^\infty e^{-2i \xi t}\frac{dt}{1+t^2},$$ we have \begin{align*} \sum_{j,k}a_j\bar a_ke^{-2|x_j-x_k|}&=\frac1{\pi}\int_{-\infty}^\infty \sum_{j,k}a_j\bar a_ke^{-2i (x_j-x_k) t}\frac{dt}{1+t^2}\\&=\frac1{\pi}\int_{-\infty}^\infty \left|\sum_j a_j e^{-2ix_jt}\right|^2\frac{dt}{1+t^2}\\&\ge 0. \end{align*} So $$x\mapsto e^{-2|x|}$$ is non-negative definite.
Note: What you indeed need to show is $$\sum_{j,k}a_j\bar a_ke^{-2|x_j-x_k|}\ge 0$$ for every $$(a_j)_{j=1}^n$$ and $$(x_j)_{j=1}^n$$. We cannot restrict to $$x_j=j$$.

Terminology: The inequality you're trying to prove actually says that the function $$e^{-2|j|}$$ is positive definite on $$\Bbb Z$$.

I think the "best" proof is by the trivial half of Bochner's Theorem, as in the other answer. But you can also do it directly.

Notation: To save typing I'm going to write $$f(t)=e^{-2|t|}$$and $$\alpha=\sum|a_j|^2.$$

Note that $$\sum_{j,k}a_j\overline{a_k}f(j-k)=\alpha+\left(\sum_{n=-\infty}^{-1}+\sum_{n=1}^\infty\right)f(n)\sum_ja_j\overline{a_{j+n}}.$$

Cauchy-Schwarz shows that $$\left|\sum_ja_j\overline{a_{j+n}}\right|\le\alpha,$$

which gives $$\sum_{j,k}a_j\overline{a_k}f(j-k)\ge\alpha\left(1-2\sum_{n=1}^\infty f(n)\right).$$So you're done if $$1-2\sum_1^\infty f(n)>0,$$which is true if I added the geometriic series correctly.