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$?
 A: 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.
A: A necessary condition is that the Cayley-Menger determinant has to be non-negative.
A: 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.
