4
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Shouldn't there be a $d(i,j)^2$ on the right hand side of your equation? $\endgroup$
    – M. Winter
    Sep 15 at 10:51
  • $\begingroup$ I think (offhand, haven't double-checked) that if $\sqrt{d}$ is ultrametric then the corresponding Gram matrix works. $\endgroup$ Sep 15 at 15:19
  • $\begingroup$ @SteveHuntsman sorry, but isn't $\sqrt{d}$ ultrametric if and only if $d$ is? (Also, I added a squared term, per another comment) $\endgroup$ Sep 15 at 18:36
  • $\begingroup$ @M.Winter thank you! Corrected! $\endgroup$ Sep 15 at 18:36
  • $\begingroup$ @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. $\endgroup$ Sep 15 at 18:45
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$ Sep 14 at 23:37
  • $\begingroup$ 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. $\endgroup$ Sep 14 at 23:43
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – M. Winter
    yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.