# Is this determinant always non-negative?

For any $$(a_1,a_2,\cdots,a_n)\in\mathbb{R}^n$$, a matrix $$A$$ is defined by

$$A_{ij}=\frac1{1+|a_i-a_j|}$$

Is $$\det(A)$$ always non-negative? I did some numerical test and it seems to be true, but I have no idea how to prove it. Thanks!

• I know that it's common to use $|A|$ in basic linear algebra, but this notation can be pretty confusing since it's also used to denote the matrix $(A^*A)^{\frac{1}{2}}$. Commented Aug 4, 2015 at 4:11
• Well it's true for a $2 \times 2$ matrix... Commented Aug 4, 2015 at 4:18
• Let $z_{ij}=1+|a_{i}-a_{j}|$. For $2\times 2$ matrix, you have $$\det(A)=\begin{vmatrix} 1/z_{11} &1/z_{12} \\ 1/z_{21} &1/z_{22} \end{vmatrix}\geq 0\iff z_{11}z_{22}\leq z_{12}z_{21}.$$ If $z_{11}z_{22}\not\leq z_{12}z_{21}$, then $\det(A)$ can't be non-negative. Commented Aug 4, 2015 at 5:55
• @AjmalW you're half correct, except $z_{11} = z_{22} = 1$, and $0 < 1/z_{12}, 1/z_{21} < 1$ so the determinant is always non-negative in the $2 \times 2$ case. Commented Aug 4, 2015 at 6:31
• If you want a result for problems very similar to this and put in a broader context try the first part of Lemma 11.3.2 in: Philip Davis, Interpolation and Approximation. Commented Aug 5, 2015 at 13:30

Here is an analytic proof (which I think I have learnt somewhere else, although not in this form). We first show an algebraic fact:

Theorem 1. Let $$\mathbb{K}$$ be a commutative ring, and let $$n\in\mathbb{N}$$. Let $$p_{1},p_{2},\ldots,p_{n-1}$$ be $$n-1$$ elements of $$\mathbb{K}$$. Let $$q_1, q_2, \ldots, q_{n-1}$$ be $$n-1$$ further elements of $$\mathbb{K}$$. For any $$\left( i,j\right) \in\left\{ 1,2,\ldots,n\right\} ^{2}$$ satisfying $$i\leq j$$, we set \begin{align} a_{i,j}=\prod_{r=i}^{j-1}p_{r}=p_{i}p_{i+1}\cdots p_{j-1}. \end{align} (When $$i=j$$, this product is empty and thus evaluates to $$1$$.) For any $$\left( i,j\right) \in\left\{ 1,2,\ldots,n\right\} ^{2}$$ satisfying $$i>j$$, we set \begin{align} a_{i,j}=\prod_{r=j}^{i-1}q_{r}=q_{j}q_{j+1}\cdots q_{i-1}. \end{align} Let $$A$$ be the $$n\times n$$-matrix $$\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$. We have $$$$\det A=\prod_{r=1}^{n-1}\left( 1 - p_r q_r \right) .$$$$ (We understand the right hand side to be an empty product if $$n$$ is $$0$$ or $$1$$.)

(Example: When $$n=4$$, the matrix $$A$$ in Theorem 1 equals $$\begin{pmatrix} 1 & p_{1} & p_{1}p_{2} & p_{1}p_{2}p_{3}\\ q_{1} & 1 & p_{2} & p_{2}p_{3}\\ q_{1}q_{2} & q_{2} & 1 & p_{3}\\ q_{1}q_{2}q_{3} & q_{2}q_{3} & q_{3} & 1 \end{pmatrix}$$.)

Proof of Theorem 1. First, a notation: If $$N\in\mathbb{N}$$ and $$M\in\mathbb{N}$$, if $$B$$ is an $$N\times M$$-matrix, and if $$p\in\left\{ 1,2,\ldots,N\right\}$$ and $$q\in\left\{ 1,2,\ldots,M\right\}$$, then we let $$B_{\sim p,\sim q}$$ denote the $$\left( N-1\right) \times\left( M-1\right)$$-matrix obtained from the matrix $$B$$ by crossing out the $$p$$-th row and the $$q$$-th column. It is well-known that if $$K$$ is a positive integer, and if the $$K$$-th row of a $$K\times K$$-matrix $$D$$ is zero apart from its last entry, then \begin{align} \det D=d\det\left( D_{\sim K,\sim K}\right) , \label{darij1.eq.1} \tag{1} \end{align} where $$d$$ is the last entry of the $$K$$-th row of $$D$$. (This can be viewed as a particular case of Laplace expansion with respect to the $$K$$-th row).

Now, we shall prove that \begin{align} \det\left( \left( a_{i,j}\right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) =\prod\limits_{r=1}^{k-1}\left( 1 - p_r q_r \right) \label{darij1.eq.2} \tag{2} \end{align} for every $$k\in\left\{ 0,1,\ldots,n\right\}$$.

Indeed, we prove \eqref{darij1.eq.2} by induction over $$k$$: If $$k=0$$ or $$k=1$$, then \eqref{darij1.eq.2} holds by inspection. For the induction step, fix $$K\in\left\{ 2,3,\ldots,n\right\}$$, and assume (as the induction hypothesis) that \eqref{darij1.eq.2} holds for $$k=K-1$$. That is, we assume that \begin{align} \det\left( \left( a_{i,j}\right) _{1\leq i\leq K-1,\ 1\leq j\leq K-1}\right) =\prod\limits_{r=1}^{\left(K-1\right)-1} \left( 1 - p_r q_r \right) . \label{darij1.eq.3} \tag{3} \end{align} Now, if we subtract $$q_{K-1}$$ times the $$\left( K-1\right)$$-th row of the matrix $$\left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}$$ from its $$K$$-th row, then we obtain a new matrix $$C$$. It is easy to see that the $$K$$-th row of the new matrix $$C$$ is zero apart from its last entry, which is $$1-p_{K-1}q_{K-1}$$. Thus, \eqref{darij1.eq.1} (applied to $$D=C$$) yields \begin{align} \det C &=\left( 1-p_{K-1}q_{K-1}\right) \det\left( \underbrace{C_{\sim K,\sim K}}_{=\left( a_{i,j}\right) _{1\leq i\leq K-1,\ 1\leq j\leq K-1} }\right) \\ &=\left( 1-p_{K-1}q_{K-1}\right) \underbrace{\det\left( \left( a_{i,j} \right) _{1\leq i\leq K-1,\ 1\leq j\leq K-1}\right) }_{\substack{=\prod _{r=1}^{\left( K-1\right) -1}\left( 1-p_{r}q_r\right) \\\text{(by \eqref{darij1.eq.3})}}} \\ &=\left( 1-p_{K-1}q_{K-1}\right) \prod_{r=1}^{\left( K-1\right) -1}\left( 1-p_{r}q_r\right) \\ & =\prod_{r=1}^{K-1}\left( 1-p_{r}q_r\right) . \label{darij1.eq.4} \tag{4} \end{align}

But the matrix $$C$$ was obtained from the matrix $$\left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}$$ by subtracting a multiple of a row from another (see the definition of $$C$$); it is known that such a subtraction does not change the determinant of a matrix. Thus, $$\det C=\det\left( \left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}\right)$$. Compared with \eqref{darij1.eq.4}, this yields \begin{align} \det\left( \left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}\right) =\prod_{r=1}^{K-1}\left( 1-p_{r}q_r\right) , \end{align} and therefore \eqref{darij1.eq.2} holds for $$k=K$$. This completes the induction step, so that \eqref{darij1.eq.2} is proven.

Now, applying \eqref{darij1.eq.2} to $$k=n$$, we obtain $$\det\left( \left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) =\prod_{r=1}^{n-1}\left( 1-p_{r} q_r\right)$$. Since $$A=\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$, this rewrites as $$\det A=\prod_{r=1}^{n-1}\left( 1-p_{r}q_r\right)$$. Theorem 1 is proven. $$\blacksquare$$

Corollary 1b. Let $$\mathbb{K}$$ be a commutative ring, and let $$n\in\mathbb{N}$$. Let $$p_{1},p_{2},\ldots,p_{n-1}$$ be $$n-1$$ elements of $$\mathbb{K}$$. For any $$\left( i,j\right) \in\left\{ 1,2,\ldots,n\right\} ^{2}$$ satisfying $$i\leq j$$, we set $$a_{i,j}=\prod_{r=i}^{j-1}p_{r}=p_{i}p_{i+1}\cdots p_{j-1}$$. (When $$i=j$$, this product is empty and thus evaluates to $$1$$.) For any $$\left( i,j\right) \in\left\{ 1,2,\ldots,n\right\} ^{2}$$ satisfying $$i>j$$, we set $$a_{i,j}=a_{j,i}$$ (since $$a_{j,i}$$ has already been defined by the previous sentence). Let $$A$$ be the $$n\times n$$-matrix $$\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$. We have $$$$\det A=\prod_{r=1}^{n-1}\left( 1-p_{r}^{2}\right) .$$$$ (We understand the right hand side to be an empty product if $$n$$ is $$0$$ or $$1$$.)

Proof of Corollary 1b. This follows from Theorem 1, applied to $$q_i = p_i$$. $$\blacksquare$$

Corollary 2. Let $$q_{1},q_{2},\ldots,q_{n}$$ be $$n$$ distinct positive reals. Let $$w\in\left[ 0,1\right)$$. Then, $$\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) >0$$.

Proof of Corollary 2. If we permute the numbers $$q_{1},q_{2},\ldots,q_{n}$$ (among themselves), then the matrix $$\left( w^{\left\vert q_{i} -q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ changes, but its determinant $$\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right)$$ remains unchanged (because the rows of the matrix get permuted, and so do the columns, but both times one and the same permutation is used, so the signs cancel). Hence, we can WLOG assume that $$q_{1} (we can achieve this by a permutation). Assume this, and set $$p_{r}=w^{q_{r+1}-q_{r}}$$ for every $$r\in\left\{ 1,2,\ldots,n-1\right\}$$. Notice that, for every $$r\in\left\{ 1,2,\ldots,n-1\right\}$$, we have $$p_{r}=w^{q_{r+1}-q_{r}}\in\left[ 0,1\right)$$ (since $$w\in\left[ 0,1\right)$$ and $$q_{r+1}-\underbrace{q_{r} }_{0$$).

Set $$\mathbb{K}=\mathbb{R}$$. Define the matrix $$A$$ as in Corollary 1b. Then, it is easy to see that $$A=\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ (since $$q_1 < q_2 < \cdots < q_n$$). But Corollary 1b yields \begin{align} \det A=\prod_{r=1}^{n-1}\underbrace{\left( 1-p_{r}^{2}\right) }_{\substack{>0\\\text{(since }p_{r}\in\left[ 0,1\right) \text{)}}}>0. \end{align} Since $$A=\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$, this rewrites as $$\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) >0$$. Corollary 2 is thus proven. $$\blacksquare$$

Corollary 3. Let $$q_{1},q_{2},\ldots,q_{n}$$ be $$n$$ distinct reals. Let $$w\in\left[ 0,1\right)$$. Then, the $$n\times n$$-matrix $$\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ is positive-definite.

Proof of Corollary 3. Sylvester's criterion for positive definiteness says that a symmetric matrix $$\left( g_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\in\mathbb{R}^{n\times n}$$ is positive-definite if and only if every $$k\in\left\{ 1,2,\ldots,n\right\}$$ satisfies $$\det\left( \left( g_{i,j}\right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) >0$$. We can apply this to $$g_{i,j}=w^{\left\vert q_{i}-q_{j}\right\vert }$$ (since the matrix $$\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ is symmetric), and thus it remains to prove that every $$k\in\left\{ 1,2,\ldots,n\right\}$$ satisfies $$\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) >0$$. But this follows from Corollary 2 (applied to $$k$$ instead of $$n$$). Thus, Corollary 3 is proven. $$\blacksquare$$

Theorem 4. Let $$q_{1},q_{2},\ldots,q_{n}$$ be $$n$$ distinct reals. Then, the $$n\times n$$-matrix $$\left( \dfrac{1}{1+\left\vert q_{i} -q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ is positive-definite.

Proof of Theorem 4. The matrix in question is clearly symmetric. Thus, we only need to prove that $$\sum\limits_{i=1}^{n}\sum\limits_{j=1} ^{n}\dfrac{1}{1+\left\vert q_{i}-q_{j}\right\vert }x_{i}x_{j}>0$$ for every nonzero vector $$\left( x_{1},x_{2},\ldots,x_{n}\right) \in\mathbb{R}^{n}$$.

So fix a nonzero vector $$\left( x_{1},x_{2},\ldots,x_{n}\right) \in\mathbb{R}^{n}$$. For every $$w\in\left[ 0,1\right)$$, we have $$\sum\limits _{i=1}^{n}\sum\limits_{j=1}^{n}w^{\left\vert q_{i}-q_{j}\right\vert }x_{i}x_{j}>0$$ (by Corollary 3). Now, \begin{align} \sum_{i=1}^{n}\sum_{j=1}^{n}\underbrace{\dfrac{1}{1+\left\vert q_{i} -q_{j}\right\vert }}_{\substack{=\int_{0}^{1}w^{\left\vert q_{i} -q_{j}\right\vert }dw\\\text{(since }\left\vert q_{i}-q_{j}\right\vert \geq0\text{)}}}x_{i}x_{j} &=\sum_{i=1}^{n}\sum_{j=1}^{n}\left( \int_{0}^{1}w^{\left\vert q_{i} -q_{j}\right\vert }dw\right) x_{i}x_{j} \\ &=\int_{0}^{1}\underbrace{\left( \sum_{i=1}^{n}\sum_{j=1}^{n}w^{\left\vert q_{i}-q_{j}\right\vert }x_{i}x_{j}\right) }_{>0}dw>0 . \end{align} This is precisely what we wanted to show, and thus Theorem 4 is proven. $$\blacksquare$$

Corollary 5. Let $$q_{1},q_{2},\ldots,q_{n}$$ be $$n$$ reals. Then, the $$n\times n$$-matrix $$\left( \dfrac{1}{1+\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ is positive-semidefinite.

Proof of Corollary 5. Recall that a limit of a convergent sequence of positive-definite matrices is a positive-semidefinite matrix. Hence, Corollary 5 can be derived from Theorem 4 by continuity (because it is always possible to deform our $$n$$ reals $$q_{1},q_{2} ,\ldots,q_{n}$$ into $$n$$ distinct reals). An alternative argument would be using the semidefinite analogue of Sylvester's criterion for positive definiteness. (Be warned, however, that this analogue requires all principal minors to be $$\geq0$$, rather than only the leading principal minors!) Yet another alternative proof proceeds by "lumping" together the rows and the columns corresponding to equal numbers among our $$q_1, q_2, \ldots, q_n$$ and using this to write our matrix $$\left( \dfrac{1}{1+\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$$ in the form $$BCB^T$$, where $$C = \left( \dfrac{1}{1+\left\vert r_{i}-r_{j}\right\vert }\right) _{1\leq i\leq k,\ 1\leq j\leq k}$$ for some distinct reals $$r_1, r_2, \ldots, r_k$$ (namely, the list $$\left(r_1, r_2, \ldots, r_k\right)$$ should be simply the list $$\left(q_1, q_2, \ldots, q_n\right)$$ with all duplicates removed). $$\blacksquare$$

This answer is a suggestion as to how you may prove the result, but does not contain a proof. Instead, I'll show how a similar problem has been answered, and offer pointers to claims that would show your result:

Consider the matrix: $$A_{ij} = \frac{1}{1 + |a_i - a_j|^2}$$ Ultimately we will find that $\det(A)$ is always non-negative. The reason is that $A$ itself is a positive definite matrix. It is in the family of the Rational Quadratic Covariance Function: (aka Student T Kernel)

The rational quadratic covariance between two points separated by d distance units is given by $$C_{RQ}(d) = \Bigg(1+\frac{d^2}{2\alpha k^2}\Bigg)^{-\alpha}$$ In this case $\alpha = 1$, $k = \frac{\sqrt{2}}{2}$.

(From Wikipedia): The Covariance Function of a space process $Z(x)$ is defined by $$C(x, y) = \textrm{Cov}(Z(x), Z(y))$$ For locations $x_1, x_2, \ldots, x_N \in D$ the variance of every linear combination: $$X=\sum_{i=1}^N w_i Z(x_i)$$ can be computed as $$\operatorname{var}(X)=\sum_{i=1}^N \sum_{j=1}^N w_i C(x_i,x_j) w_j$$ A function is a valid covariance function if and only if this variance is non-negative for all possible choices of $N$ and weights $w_1, \ldots, w_N$. A function with this property is called positive definite.

For this particular problem, the $x_i$ in the statement are the $a_i$ in the matrix $A$ defined above, and $C(x_i, x_j) = C_{RQ}(|a_i - a_j|)$. It is well known (see below) that $C_{RQ}$ is positive definite as defined above and so for every linear combination: $$\sum_{i=1}^N \sum_{j=1}^N w_i C_{RQ}(|a_i - a_j|) w_j \geq 0$$ i.e. $A$ is positive definite.

Some references for the above (including the statement that $C_{RQ}$ is positive definite) can be seen at: Gaussian Processes for Machine Learning Rasmussen, Williams 2006 and Classes of Kernels for Machine Learning: A Statistics Perspective Genton 2001.

Now the kernel corresponding to the matrix you are interested in has been referred to as the Generalized T Student Kernel. $$C(x, y) = \frac{1}{1 + |x - y|^d}$$ At that blog, the following "proof" is offered:

The Generalized T-Student Kernel has been proven to be a Mercel Kernel, thus having a positive semi-definite Kernel matrix (Boughorbel, 2004).

The paper referenced is Conditionally Positive Definite Kernels For SVM Based Image Recognition - Boughorbel, Tarel, Boujemaa If this proves to be true, then the determinant of your matrix is indeed non-negative.

• Both documents contain the statement that $C_{RQ}$ is positive definite, but a proof seems to be missing. Commented Aug 4, 2015 at 16:15

We shall prove by mathematical induction that $A$ is positive semidefinite. The base case is trivial. Note that the positive semidefiniteness is preserved if we permute $a_1,\cdots,a_n$ or add the same constant to every $a_i$. So, we may assume that $a_1\ge a_2\ge \cdots\ge a_n=1$. Then $A$ becomes $$A=\left( \begin{array}{cccc} 1 & \dfrac1{1+a_1-a_2} & \cdots & \dfrac1{a_1} \\ \dfrac1{1+a_1-a_2} & 1 & \cdots & \dfrac1{a_2} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac1{a_1} & \dfrac1{a_2} & \cdots & 1 \end{array}\right) =\left(\frac1{1+a_{\min(i,j)}-a_{\max(i,j)}}\right)_{i,j=1,2,\ldots,n}$$ Since $a_{nn}=1>0$, $A$ is PSD iff the Schur complement $S$ of $a_{nn}$ in $A$ in PSD. The Schur complement $S$ is given by \begin{align*} s_{ij} &=\frac1{1+a_{\min(i,j)}-a_{\max(i,j)}}-\frac1{a_ia_j}\\ &=\frac1{1+a_{\min(i,j)}-a_{\max(i,j)}}-\frac1{a_{\min(i,j)}a_{\max(i,j)}}\\ &=\frac1{1+a_{\min(i,j)}-a_{\max(i,j)}}\cdot\frac{a_{\min(i,j)}+1}{a_{\min(i,j)}}\cdot\frac{a_{\max(i,j)}-1}{a_{\max(i,j)}}\\ &=\left(\frac1{1+a_{\min(i,j)}-a_{\max(i,j)}}\right) \left(1-\frac1{a_{\max(i,j)}}\right) \left(1+\frac1{a_{\min(i,j)}}\right). \end{align*} Therefore $S$ is a Hadamard product of three matrices. By induction assumption, the first matrix is PSD. It's easy to verify that the other two are PSD as well. Let $E_k$ denotes the matrix whose $k\times k$ leading principal submatrix contains only ones and all other entries are zero. Since $1-\frac1{a_i}$ is a decreasing sequence, the matrix $\left(1-\frac1{a_{\max(i,j)}}\right)_{i,j=1,2,\ldots,n-1}$ is a nonnegative weighted sum of $E_1,E_2,\ldots,E_{n-1}$. Similarly, as $1+\frac1{a_i}$ is increasing, $\left(1+\frac1{a_{\min(i,j)}}\right)_{i,j=1,2,\ldots,n-1}$ is also a nonnegative weighted sum of PSD matrices (but whose trailing principal submatrices, rather than the leading ones, contain ones). So, by Schur product theorem, $S$ is PSD and hence $A$ is PSD.

• Sorry, I really don't understand this. How are the matrices defined? ($A$ in particular.) And why is the last matrix PSD? Commented Aug 4, 2015 at 20:20
• $A$ is obtained using $a_1\ge a_2\ge \cdots\ge a_n=1$. I've edited my answer to show some missing steps.
– Niko
Commented Aug 4, 2015 at 20:42
• Nice!!! This is a beautiful solution, if marred by lack of detail and unclear notations. For example, your three symmetric matrices at the end would be much clearer if written $\left(\dfrac{1}{1+a_{\min\left(i,j\right)}-a_{\max\left(i,j\right)}}\right)_{1 \le i\leq n-1,\ 1\le j\leq n-1}$, $\left(\dfrac{a_{\max\left(i,j\right)}-1}{a_{\max\left(i,j\right)}}\right)_{1\le i\le n-1,\ 1\le j\le n-1}$ and $\left(\dfrac{a_{\min\left(i,j\right)}+1}{a_{\min\left(i,j\right)}}\right)_{1\le i\le n-1,\ 1\le j\le n-1}$. And if you said that at the first step of the computation of $\det A$, you are using ... Commented Aug 4, 2015 at 21:52
• ... the fact that every $n \times n$-matrix $B = \left(b_{i,j}\right)_{1\le i\le n,\ 1\le j\le n}$ with $b_{n,n}=1$ satisfies $\det B = \det\left(\left(b_{i,j}b_{n,n}-b_{i,n}b_{n,j}\right)_{1\le i\le n-1, \ 1\le j\le n-1}\right)$. Commented Aug 4, 2015 at 21:54
• Thanks for the suggestion (and the great answer)! Sorry for the lack of details but writing matrices in TeX is hard...
– Niko
Commented Aug 4, 2015 at 22:00

The function $f:x\mapsto\frac1{1+x}$ is non-constant and completely monotone on $[0,\infty)$ (i.e. all even-order derivatives of $f$ are nonnegative and all odd-order derivatives of $f$ are nonpositive). Therefore, by Schoenberg's interpolation theorem, the matrix $\left(f(\|a_i-a_j\|_2)\right)_{i,j=1,2,\ldots,n}$ is positive semidefinite, and it is positive definite iff all $a_i$s are distinct.

Since our friend @user1551: reminded us of Schoenberg's beautiful theory, let's see if we can give more details regarding our problem.

First, consider $$a_1$$, $$a_2$$, $$\ldots$$, $$a_n$$ points in a (finite dimensional) Euclidean space. Then the matrix

$$(\exp(-t \|a_i-a_j\|^2)\,)$$ is positive semidefinite for any $$t\ge 0$$. Why is that? We have $$\exp(-t \|a_i-a_j\|^2) = \exp - (t \|a_i\|^2 )\cdot \exp 2 t \langle a_i, a_j \rangle \cdot \exp - (t \|a_j\|^2 )$$

So now it is enough to check that the matrix

$$(\exp 2 t \langle a_i, a_j \rangle \,)_{i,j}$$ is positive semidefinite. This follow from the following:

1. if a matrix $$(\alpha_{ij})$$ is positive semidefinite, then so is $$\exp 2 t( \alpha_{ij})$$

2. the Hadamard product of two positive semidefinite matrices is psd ( this $$+$$ closure under addition plus continuity proves 1) ( we use this to take products of factors that are exponential of terms in the dot product).

Now imagine that we have a function $$F(s)$$ on $$[0, \infty)$$ such that

$$F(s) = \int_{0}^{\infty} e^{- t s} \mu(t) d t$$ for some function $$\mu\colon [0, \infty) \to [0, \infty)$$ ( so $$F$$ is the Laplace transform of the positive function $$\mu(\cdot)$$). Then from the above we conclude that the matrix $$(F(\|a_i-a_j\|^2))_{i,j}$$ is positive semidefinite. To see this one notices that $$(F(\|a_i-a_j\|^2)$$ is the integral of the positive semidefinite matrices $$(\exp( -t\|a_i-a_j\|^2) \, )_{i,j}$$ agains the function $$\mu(t)$$.

Now, for us the function is $$F(s) = \frac{1}{1+ \sqrt{s}}$$. How can we tell that it is the Laplace transform of a positive function? First, let us notice that the function $$G(s)$$ is the L transform of the function $$\mu(t) = exp(-t)$$. Now, it is a fact that if $$G(s)$$ is then $$G(s^\alpha)$$ is for all $$\alpha \in (0,1)$$ ( this follows from two facts:

1. the L transforms of positive functions are exactly the functions $$F$$ such that $$(-1)^n F^{(n)}>0 0$$, that is, completely monotone function ( Bernstein theorem)

2. The function $$s \mapsto s^{\alpha}$$ is completely monotone if $$0< \alpha < 1$$.

3. The composition of completely monotone functions is completely monotone ( this is basic differential calculus and algebra).

Almost there: we know apriori that the matrix

$$(\frac{1}{1 + \|a_i - a_j\|} ){i,j}$$ is positive semidefinite. However, we would like to show that it is in fact positive definite if all the $$a_i$$ are distinct. How to do this? Recall that from the theory discussed above we have

$$\frac{1}{1+ \sqrt{s}} = \int_{0}^{\infty} exp(-t s) \mu(t) dt$$

for some function $$\mu\colon [0, \infty) \to [0, \infty)$$. Now, some more theory tells us an exact form for $$\mu(t)$$ :

$$\mu(t) = \frac{1}{\sqrt{\pi t}} - e^t (1 - \operatorname{Erf}(\sqrt{t}) )$$

The important thing is that $$\mu(\cdot)$$ is not zero anywhere. Using only this, let's show that our matrix is positive definite. We have

$$\sum_{i,j=1}^n \frac{1}{1 + \|a_i - a_j\|} x_i x_j = \int_{0}^{\infty} (\sum_{i,j=1}^n \exp (-t \|a_i-a_j\|^2) x_i x_j )\mu(t) d t$$

Now, for every $$t\ge 0$$, the sum $$\sum_{i,j=1}^n \exp (-t \|a_i-a_j\|^2) x_i x_j\ge 0$$. Moreover, if $$t$$ is large then the dominant term are the groupings with all $$a_i$$ equal. So if the $$a_i$$ are all distinct then for $$t$$ large we have the inside sum approximately $$\sum_{i=1}^n x_i^2>0$$. This, coupled with $$\mu(t) \ne 0$$ ( at least for $$t$$ large) shows the strict positivity. And this implies the determinant is positive.