# 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.

• seethis recent question and answer: math.stackexchange.com/questions/2762141/… – Will Jagy May 5 '18 at 19:00
• Thanks very much! But I don't think they are similar. As k(.) could be some piecewise constant function here. – Jin May 5 '18 at 20:13
• the $s$ does not matter at all. Is $N$ the integer one smaller than the size of the matrix? Oh, and try the 2 by 2 and 3 by 3 sizes to see what happens – Will Jagy May 5 '18 at 20:57
• Yes, N is smaller than the size of the matrix. I saw that question, the thing I don't get is 'With 0<t<1 this means that both M and the original A are positive definite.'. I understand M is positive definite since it is the diagonal matrix with all diagonal entries being positive. But why A is also positive definite? – Jin May 5 '18 at 21:57
• en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia – Will Jagy May 5 '18 at 23:06

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$.
• @Jin Yes, we need to use squared norm, but luckily, $\varphi(x)=e^{-\sqrt{x}}$ is completely monotone, so that $\varphi(x^2)=k(x)$ on $[0,\infty)$. – user1551 May 6 '18 at 16:41