Bipartite metric spaces provide simple examples of highly non-Euclidean metric spaces. Let and be two disjoint abstract sets, say, with and points respectively. Define a metric on the union as follows, where are some positive numbers:

- The distance between distinct elements of is .
- The distance between distinct elements of is .
- The distance between two elements from different sets is .

The triangle inequality is satisfied provided that . When is large, the space is not very interesting: it is approximately the union of two simplexes placed at some large distance from each other. On the other hand, when we encounter a bizarre situation: every point of is a “midpoint” between any two distinct points of , and vice versa.

A function is called a **positive kernel** if the matrix is positive semidefinite for any choice of and . A classical theorem of Schoenberg says that a metric space is isometric to a subset of a Hilbert space if and only if is a positive kernel for all . One may ask: is there any function such that is a positive kernel on for every metric space ?

Suppose is such a function. Applying it to the bipartite metric defined above, we find that the following matrix must be positive semidefinite (the case , shown; in general the diagonal blocks have sizes and ):

Test the PSD property against vectors of the form , that is entries equal to some number followed by entries equal to some number . The result is the quadratic form where , , and .

For this quadratic form to be positive semidefinite, we need and to hold. The inequality amounts to and , because can be any positive integer. Simply put, must be nonnegative.

The inequality simplifies to

When and , we obtain ; so, is maximized at . Letting yields . What does this mean?

If , the inequality amounts to log-convexity of , and there are lots of log-convex functions. But crucially, our only constraint on in the construction of a bipartite metric space is . In the special case we find that whenever (and ). On one hand, must be **nonincreasing** because all are allowed. On the other hand, implies that the sequence is **nondecreasing** for . These conditions can be satisfied together only if is constant on .

And there you have it, a complete description of functions that transform every distance matrix into a positive semidefinite matrix: on , and . It is immediate that such indeed works for all metric spaces, not just bipartite ones.