# When does a finite metric induce a matrix norm?

If I have a metric $$d(\cdot,\cdot)$$ on the set $$\{1,\dots,n\}$$, are there well-known necessary or sufficient conditions for the existence of a matrix norm $$Q$$ that induces that metric on the unit vectors $$e_1,\dots,e_n$$? That is, under what conditions can I find $$Q\succeq0$$ such that $$(e_i-e_j)^TQ(e_i-e_j) = d(i,j)^2$$ for all $$i$$ and $$j$$?

• Shouldn't there be a $d(i,j)^2$ on the right hand side of your equation? Sep 15 at 10:51
• I think (offhand, haven't double-checked) that if $\sqrt{d}$ is ultrametric then the corresponding Gram matrix works. Sep 15 at 15:19
• @SteveHuntsman sorry, but isn't $\sqrt{d}$ ultrametric if and only if $d$ is? (Also, I added a squared term, per another comment) Sep 15 at 18:36
• @M.Winter thank you! Corrected! Sep 15 at 18:36
• @TomSolberg- $d$ is an ultrametric iff $d^\alpha$ is a metric for all $\alpha > 0$, but I don't think there's any guarantee about whether or not $d^\alpha$ is an _ultra_metric. Sep 15 at 18:45

## 3 Answers

Not a complete answer, but a sufficient condition.

The equation $$(e_i - e_j)^TQ(e_i - e_j) = d(i,j)^2$$ tells us that $$q_{i,i} + q_{j,j} - 2q_{i,j} = d(i,j)^2$$, so $$q_{i,j} = (q_{i,i} + q_{j,j} - d(i,j)^2)/2$$ for all $$i \neq j$$. This completely determines the off-diagonal entries of $$Q$$ in terms of its diagonal entries, so we are left just with asking whether or not there exist diagonal entries that result in this matrix $$Q$$ being positive semidefinite.

If $$n = 2$$ then we are just asking whether or not there exist $$q_{1,1}, q_{2,2} \geq 0$$ such that $$4q_{1,1}q_{2,2} \geq (q_{1,1} + q_{2,2} - d(1,2)^2)^2$$. Such $$q_{1,1}$$ and $$q_{2,2}$$ always exist.

If $$n \geq 3$$ then you could probably still get something fairly precise out of Sylvester's criterion, but it looks ugly even when $$n = 3$$ so I haven't gone through the calculation. However, you can fairly easily get sufficient conditions by using diagonal dominance. For example, if we define $$D = \max_{i,j}\{d(i,j)^2\}$$ then such a matrix $$Q$$ exists whenever $$\sum_{\stackrel{j=1}{j\neq i}}^nd(i,j)^2 \geq (n-2)D \ \ \text{ for all } \ \ i.$$ Intuitively, this condition says that $$Q$$ exists whenever the $$d(i,j)$$'s are reasonably "flat". The proof of this sufficient condition is simply that, under these conditions, we can choose $$q_{j,j} = D/2$$ for all $$j$$ and see that the resulting matrix $$Q$$ is diagonally dominant and thus positive semidefinite.

• Naively I would think that that sufficiency condition becomes much harder to satisfy as $n$ increases — if we consider the standard Euclidean metric on $[1\ldots n]$ then $\max_i(\sum_{j=1}^nd(i,j))$ is roughly $\frac n2 D$ and the average case is even worse. Certainly not every metric is even nearly Euclidean, but given that the upper bound on the sum is $(n-1)D$, requiring it to be $\geq (n-2)D$ for all $i$ seems like a pretty heavy lift. That said, I don't know how 'likely' it is that a given metric will have a matrix norm inducing it, so maybe this is closer to necessary than it looks... Sep 14 at 23:37
• I agree -- my intuition is that this does pretty poorly for large $n$. I think that the reason for this is that diagonal dominance becomes a worse and worse approximation of positive semidefiniteness (in some loose sense that I don't necessarily know how to make precise) as $n$ increases. Sep 14 at 23:43

A necessary condition is that the Cayley-Menger determinant has to be non-negative.

Your quadratic form $$Q$$ is uniquely defined by $$d$$ on the hyperplane $$H$$ defined by $$\sum x_i=0$$. Further, $$Q|_H\ge 0$$ if and only if your metric space is isometric to a subset of a Eulcidean space.

• This suggests the following algorithm: choose a basis of $H$, compute a matrix representation of $Q_H$ (which should be uniquely determined according to the answer) and check whether this matrix is positive (semi-)definite. yesterday