# Bipartite metric spaces and positive kernels

Bipartite metric spaces provide simple examples of highly non-Euclidean metric spaces. Let ${A}$ and ${B}$ be two disjoint abstract sets, say, with ${m}$ and ${n}$ points respectively. Define a metric on the union ${A\cup B}$ as follows, where ${a, b, c}$ are some positive numbers:

• The distance between distinct elements of ${A}$ is ${a}$.
• The distance between distinct elements of ${B}$ is ${b}$.
• The distance between two elements from different sets is ${c}$.

The triangle inequality is satisfied provided that ${a, b\le 2c}$. When ${c}$ 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 ${a=b=2c}$ we encounter a bizarre situation: every point of ${B}$ is a “midpoint” between any two distinct points of ${A}$, and vice versa.

A function ${K\colon X\times X \to \mathbb R}$ is called a positive kernel if the matrix ${K(x_i, x_j)_{i, j=1}^n}$ is positive semidefinite for any choice of ${n}$ and ${x_1, \dots, x_n\in X}$. A classical theorem of Schoenberg says that a metric space ${(X, d)}$ is isometric to a subset of a Hilbert space if and only if ${\exp(-\gamma d^2)}$ is a positive kernel for all ${\gamma >0}$. One may ask: is there any function ${f\colon [0, \infty)\to\mathbb R}$ such that ${f\circ d}$ is a positive kernel on ${X}$ for every metric space ${(X, d)}$?

Suppose ${f}$ is such a function. Applying it to the bipartite metric defined above, we find that the following matrix must be positive semidefinite (the case ${m=3}$, ${n=2}$ shown; in general the diagonal blocks have sizes ${m\times m}$ and ${n\times n}$):

${\displaystyle \begin{pmatrix} f(0) & f(a) & f(a) & f(c) & f(c) \\ f(a) & f(0) & f(a) & f(c) & f(c) \\ f(a) & f(a) & f(0) & f(c) & f(c) \\ f(c) & f(c) & f(c) & f(0) & f(b) \\ f(c) & f(c) & f(c) & f(b) & f(0) \end{pmatrix} }$

Test the PSD property against vectors of the form ${(s, s, s, t, t)}$, that is ${m}$ entries equal to some number ${s}$ followed by ${n}$ entries equal to some number ${t}$. The result is the quadratic form ${As^2 + Bt^2 + 2C^2st }$ where ${A = (m^2-m) f(a)+mf(0)}$, ${B = (n^2-n)f(b)+nf(0)}$, and ${C = mnf(c)}$.

For this quadratic form to be positive semidefinite, we need ${A\ge 0}$ and ${C^2\le AB}$ to hold. The inequality ${A\ge 0}$ amounts to ${f(a)\ge 0}$ and ${f(0)\ge 0}$, because ${m}$ can be any positive integer. Simply put, ${f}$ must be nonnegative.

The inequality ${C^2\le AB}$ simplifies to

${ mn f(c)^2 \le ( (m-1) f(a)+f(0)) \cdot ((n-1)f(b)+ f(0)) }$

When ${m=n=1}$ and ${a=b}$, we obtain ${f(c)\le f(0)}$; so, ${f}$ is maximized at ${0}$. Letting ${m, n\to \infty}$ yields ${f(c)^2 \le f(a)f(b)}$. What does this mean?

If ${c=(a+b)/2}$, the inequality ${f(c)^2 \le f(a)f(b)}$ amounts to log-convexity of ${f}$, and there are lots of log-convex functions. But crucially, our only constraint on ${c}$ in the construction of a bipartite metric space is ${c\ge \max(a, b)/2}$. In the special case ${a=b}$ we find that ${f(c)\le f(a)}$ whenever ${c\ge a/2}$ (and ${a>0}$). On one hand, ${f}$ must be nonincreasing because all ${c\ge a}$ are allowed. On the other hand, ${f(a/2)\le f(a)}$ implies that the sequence ${k\mapsto f(2^k)}$ is nondecreasing for ${k\in\mathbb Z}$. These conditions can be satisfied together only if ${f}$ is constant on ${(0, \infty)}$.

And there you have it, a complete description of functions ${f\colon [0, \infty)\to\mathbb R}$ that transform every distance matrix into a positive semidefinite matrix: ${f\equiv c\ge 0}$ on ${(0, \infty)}$, and ${f(0)\ge c}$. It is immediate that such ${f}$ indeed works for all metric spaces, not just bipartite ones.