# Problem with a Positive Definite Kernel/Matrix

$$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}

• The ones that are negative are numerically zero. See the docs of 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. Nov 24, 2016 at 17:39