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.

  • $\begingroup$ seethis recent question and answer: math.stackexchange.com/questions/2762141/… $\endgroup$ – Will Jagy May 5 '18 at 19:00
  • $\begingroup$ Thanks very much! But I don't think they are similar. As k(.) could be some piecewise constant function here. $\endgroup$ – Jin May 5 '18 at 20:13
  • $\begingroup$ 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 $\endgroup$ – Will Jagy May 5 '18 at 20:57
  • $\begingroup$ 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? $\endgroup$ – Jin May 5 '18 at 21:57
  • $\begingroup$ en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia $\endgroup$ – 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$.

  • $\begingroup$ Thank you very much! Question: it must be || xi - xj ||^2 inside k(.) ? Could it be just || xi - xj ||? $\endgroup$ – Jin May 6 '18 at 16:28
  • $\begingroup$ @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)$. $\endgroup$ – user1551 May 6 '18 at 16:41

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.