How to prove the positive-definiteness of a symmetric Toeplitz matrix like it? Define a symmetric Toeplitz matrix by 
H = 
\begin{bmatrix}
    2k(0) & k(s) & k(2s) & \dots  & k(NS)  \\
    k(s) & 2k(0) & k(s) & \dots  & k((N-1)S) \\
    k(2s) & k(s) & 2k(0) & \dots  & k((N-2)S) \\
    \vdots & \vdots & \vdots & \ddots   \\
    k(Ns) & k((N-1)s) & k((N-2)s) & \dots & 2k(0)
\end{bmatrix} 
k(.) is non-increasing function. e.g k(x) = $e^{-x}$
s, N are known constant. 
How to prove that this matrix is positive-definite? Thanks a lot.
 A: This is not true. Consider the $n\times n$ penta-band symmetric Toeplitz matrix
$$
\pmatrix{
2&1&1\\
1&\ddots&\ddots&\ddots\\
1&\ddots&\ddots&\ddots&\ddots\\
 &\ddots&\ddots&\ddots&\ddots&1\\
 &      &\ddots&\ddots&\ddots&1\\
 &      &      &1&1&2}.
$$
It has positive, negative and zero eigenvalues when $n=11$.
An $n\times n$ matrix $A$ is guaranteed to be positive definite if $a_{ij}=\varphi\left(\|x_i-x_j\|^2\right)$ for some completely monotone function $\varphi:[0,\infty)\to\mathbb R$ (i.e. a function such that $(-1)^m\frac{d^m\varphi}{dx^m}\ge0$ on $(0,\infty)$ for every $m\ge0$) and some set of distinct points $\{x_1,\ldots,x_n\}$ in some Euclidean space $\mathbb R^s$. This is known as Schoenberg interpolation theorem, which is a consequence of Bochner's characterisation of positive definite functions. See chapter 15 of A Course in Approximation Theory by Cheney and Light or sec. 2.5 of this book chapter for more details.
In your case, $\varphi(x)=e^{-\sqrt{x}}$ is known to be completely monotone. So, with this function $\varphi$, $A=H-k(0)I$ is positive definite and so is $H$.
