Negative eigenvalues when computing MultiDimensional Scaling given nonnegative distance matrix

I am using the Smile MDS
https://github.com/haifengl/smile/blob/master/core/src/main/java/smile/mds/MDS.java and occasionally running into:

Caused by: java.lang.IllegalArgumentException:
Some of the first 2 eigenvalues are < 0


The data being sent in is a square symmetric distance matrix. I have not put any restrictions on the distance matrix values except they must be nonnegative - which in fact all are between 0 and 1 inclusive.

So two questions:

• under what conditions may such a (nonnegative) matrix result in negative eigenvalues?
• how might I condition the input similarities matrix to avoid the negative values?
• (extra credit): are there other JVM libraries that might help to deal with the existing (arbitrary non-negative) dataset as is?
• You'll have to describe how this implementation works for this question to be answerable. If the software is computing an eigendecomposition of the raw distance matrix, your answer is immediate: distance matrices have 0s on the diagonal. – Sycorax says Reinstate Monica Jul 10 '18 at 17:27

Classical MDS works by using the distance matrix to compute an inner product (Gram) matrix $G$. $G$ contains the dot products between each pair of data points, assuming the distances were Euclidean. It then performs an eigendecomposition of $G$ to embed points into a vector space in a way that that preserves the dot products as well as possible. $G$ can have negative eigenvalues if the original distances were not Euclidean. This can still be ok in some cases. But, if there are many negative eigenvalues, it may indicate that classical MDS is not a good fit for the problem. In this case, nonclassical MDS (of which there are multiple forms) may work better. As Sycorax pointed out, the distance matrix should have zeros on the diagonal.