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$?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Shouldn't there be a $d(i,j)^2$ on the right hand side of your equation? $\endgroup$– M. WinterCommented Sep 15, 2021 at 10:51
-
$\begingroup$ I think (offhand, haven't double-checked) that if $\sqrt{d}$ is ultrametric then the corresponding Gram matrix works. $\endgroup$– Steve HuntsmanCommented Sep 15, 2021 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$– Tom SolbergCommented Sep 15, 2021 at 18:36
-
$\begingroup$ @M.Winter thank you! Corrected! $\endgroup$– Tom SolbergCommented Sep 15, 2021 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$– Steve HuntsmanCommented Sep 15, 2021 at 18:45
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
1
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.
answered Sep 19, 2021 at 16:56
-
2$\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$ Commented Sep 21, 2021 at 10:07
$\begingroup$
$\endgroup$
2
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.
answered Sep 14, 2021 at 23:14
-
$\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$ Commented Sep 14, 2021 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$ Commented Sep 14, 2021 at 23:43
$\begingroup$
$\endgroup$
A necessary condition is that the Cayley-Menger determinant has to be non-negative.
answered Sep 15, 2021 at 10:06