The standard Radial Basis Function:
$$K(x_1, x_2) = e^{-(x_1-x_2)^2/2}$$
is known to be positive definite (P.D.). This can be shown by, for example, the Bochner Theorem. By positive definite it is meant that
$$\sum_{i=1}^k \sum_{j=1}^k c_i c_j K(x_i, x_j) \geq 0$$
for any choice of $k \in \mathbb{N}$, $x_1, x_2, \ldots, x_k \in \mathbb{R}^n$ and $c_1, c_2, \ldots, c_k \in \mathbb{R}$.
From the above inequality, it seems obvious that the Hermitian part of the matrix with entries $$K_{ij}=K(x_i, x_j)$$ should have positive eigenvalues. Which brings me to the following problem:
G[x1_, x2_] := Exp[-1/2 (x1 - x2)^2];
list1 = RandomReal[{-10, 10}, 100];
(mat = Outer[G, list1, list1, 1]);
Eigenvalues[1/2 (mat + Transpose[mat])]
The resulting eigenvalues are not all positive. Why is that?
{14.4349, 12.5488, 11.8824, 10.0691, 9.54906, 8.65466, 7.27382, \
5.90905, 4.70692, 3.60972, 2.94933, 2.2864, 1.67143, 1.38664, \
0.926639, 0.694622, 0.479601, 0.346991, 0.218595, 0.144655, \
0.0947855, 0.0693128, 0.0390857, 0.0228503, 0.0137675, 0.0077189, \
0.00423406, 0.00209994, 0.00146088, 0.000639826, 0.000346808, \
0.000175915, 0.000081206, 0.0000427318, 0.0000218744, 0.000010557,
5.11307*10^-6, 2.03378*10^-6, 1.00012*10^-6, 4.39773*10^-7,
2.10151*10^-7, 7.53904*10^-8, 3.44437*10^-8, 1.22666*10^-8,
4.87432*10^-9, 2.15116*10^-9, 7.33137*10^-10, 4.1995*10^-10,
1.24422*10^-10, 4.71167*10^-11, 1.48485*10^-11, 6.61021*10^-12,
2.78995*10^-12, 9.61269*10^-13, 2.65273*10^-13, 8.56566*10^-14,
3.34234*10^-14, 1.14188*10^-14, 4.38365*10^-15, -2.17014*10^-15,
2.05478*10^-15, 1.69751*10^-15, -1.34612*10^-15, 1.32415*10^-15,
1.17034*10^-15, -1.09847*10^-15, 9.08927*10^-16,
8.03778*10^-16, -7.81348*10^-16, -6.84237*10^-16,
6.31285*10^-16, -5.8266*10^-16, 5.71942*10^-16, -4.67633*10^-16,
4.53221*10^-16, 4.25156*10^-16,
4.17792*10^-16, -3.92773*10^-16, -3.64044*10^-16, 3.39323*10^-16,
3.18269*10^-16, -3.06691*10^-16, 2.9718*10^-16, -2.78096*10^-16,
2.6519*10^-16, 2.12749*10^-16, -1.93748*10^-16, -1.81685*10^-16,
1.74396*10^-16, 1.56957*10^-16,
1.50008*10^-16, -1.42644*10^-16, -1.33609*10^-16,
1.29917*10^-16, -1.0308*10^-16, 7.93279*10^-17, -7.7838*10^-17,
4.323*10^-17, -1.54597*10^-17, 6.30094*10^-18}
Chop. If you use numbers with more than machine precision, you will also see that the negative entries become as small as the precision can resolve. $\endgroup$ – Marius Ladegård Meyer Nov 24 '16 at 17:39