1

Are there sufficient conditions to say that a certain matrix is a distance matrix for a certain set of vectors? For example, for the Euclidean metric or Hamming distance.

Suppose that all vectors are different. Since we consider the distance matrix, its elements must satisfy the following conditions: $$a_{ii} = 0 \quad \forall i\\a_{ij} \neq 0 \quad \forall i \neq j\\ a_{ij} = a_{ji} \quad \forall i,j \\\ a_{ij} \leq a_{ik} + a_{kj} \quad \forall i, j,k$$

These are necessary conditions. But are they sufficient? Can we come up with a matrix that satisfies these conditions, but is not a distance matrix for some set of vectors?

Ilya Fedorov
  • 171
  • These conditions correspond to the defining properties of a https://en.wikipedia.org/wiki/Metric_(mathematics)#Definition, hence are sufficient for the matrix to act as a distance function between the abstract points $x$.

    If we now want these points to be vectors in a vector space, the question is whether the given distance function is induced by some norm in that vector space. Is this what you are trying to ask?

     – avs Mar 15 '19 at 23:01
  • In this context, I identify the points and vectors from $\mathbb{R}^n$. Due to the fact that I consider the matrix of a certain distance, which is a metric, I wrote these properties. Let's fix a specific metric, for example, Hamming distances. The question is, is every matrix satisfying these properties a Hamming distance matrix for some set of vectors? A stronger statement is: is it possible to construct a set of vectors ${v_i}$ using the distance matrix, such that $ a_{ij} = d(v_i, v_j) $? – Ilya Fedorov Mar 15 '19 at 23:28
  • If I had time, I would experiment with 3 vectors in ${\mathbb R}^2$ and a 3-by-3 matrix. – avs Mar 16 '19 at 00:03

1 Answers1

3

For Euclidean distance: an $n\times n$ matrix $M=(M_{ij})$ is expressible as $M_{ij}=\|v_i-v_j\|^2$ for points $v_i$ in some Euclidean or Hilbert space, if $M$ is negative definite when restricted to the subspace of $\mathbb R^n$ of vectors $(x_1,\ldots,x_n)$ for which $\sum_{i=1}^n x_i = 0$. Equivalently, modify $M$ by subtracting row averages and columns averages, and what's left must be negative semidefinite. This is a theorem of Schoenberg (see also; a quick check could not find a wikipedia article on this precise result.)

kimchi lover
  • 24,277