Counting valid coordinates

Question

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in \mathbb{N}$)

edit: You may assume $D$ is symmetric, and there are zeroes on the main diagonal.

A coordinate $t = (t_1,t_2,\dots,t_{n}) \in \mathbb{N}^n$ is said to be "good" if for all $1 \leq a,b \leq n$: $|t_a - t_b| \leq d(a,b)$

We say that two coordinates are equivalent if one could be obtained from the other by adding a constant to all the entries.

How many "good" coordinates are there, given the matrix D? (We don't count equivalent coordinates twice).

Any idea of how to approach this is highly appreciated.

Where does this come from?

Given a graph $G=(V,E)$ (simple and undirected), and a subset $T \subseteq V$ we could get "coordinates" for every node in the graph in the following manner:

For every vertex $v \in V$ we define $coord(v) := (dist(v,a))_{a \in T}$. Here $dist$ is the length of the shortest path in the graph.

In the question above, the matrix $D$ is the set of distances ${dist(a,b)}_{a,b \in T}$. It is interesting to know at what point the coordinates space saturates. (Which means that the set $T$ is too small for the set $G$). One way to find out would be to count the amount of possible coordinates, given the triangle inequalities restrictions.

The formulation above does not take into account the requirement for $t_a + t_b \geq d(a,b)$, however it could be obtained by adding a constant to all the entries.

Example

To make the question more concrete, I include here an example. For the matrix:

0 2 1
2 0 1
1 1 0

We get the list of solutions:

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(0, 2, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(2, 0, 1)

A total of 9 solutions.

Further Progress

I noticed that for a matrix $D$ where $d(i,j) = k$ for $i \neq j$ and $d(i,j)=0$ otherwise we get that the amount of valid coordinates is $(k+1)^n - k^n$.

In the case of $n=3$, If the distances inside $D$ are $a,b,c$, then we could represent them as $a=y+z, b=x+z, c=a+y$, where $x,y,z \geq 0$. This helps us to get rid of the triangle inequalities constraints. Is there an equivalent for cases of $n>4$?

Answer 1

I'll give a partial answer. But one aspect at the time (it'll be cleaner this way). Thus first a simple introductory remark:

I'll feel safer to assume:

$$\forall_{a\ b\, \in\,\{1\ldots n\}}\ \ d(a\ b)\ \ge\ 0\ =\ d(a\ a)$$

Next, under the notation and assumptions of Question, let:

$$\forall_{a\ b\, \in\,\{1\ldots n\}}\ \ d^\circ(a\ b)\ :=\ d(b\ a)$$

Then there exists exactly one maximal pseudo-metrics $\ d_0 :\{1\ldots n\}^2\rightarrow \mathbb R\ $ such that

$$\forall_{a\ b\, \in\,\{1\ldots n\}}\ \ d_0(a\ b)\ =\ \max\,(d(a\ b)\ \,d^\circ\!(a\ b)$$

(A pseudo-metrics is like a metrics except that $\ d(a\ b)\ $ may be $\ 0\ $ even when $\ a\ne b$).   Obviously, the value $\ d_0(a\ b)\ $ is the minimum over all finite sequences of pairwise different points $\ a\!=\!a_0\,\ a_1\,\ \ldots\,\ a_m\!=\!b\ $ of alternating sums:

$$d(a_0\ a_1) + d^\circ(a_1\ a_2) + \ldots$$ and $$d^\circ(a_0\ a_1) + d(a_1\ a_2) + \ldots$$

where the last summand is $\ d(a_{m-1}\ a_m)\ $ or $\ d^\circ(a_{m-1}\ a_m)\ $ respectively. (Of course, the assumption pairwise different helps us or it helps a computer).

A vector is a coordinate with respect to $d\ \ \Leftrightarrow\ \ $ it is a coordinate with respect to $\ d_0$.

This cuts down on the number of possibilities.

Answer 2

The Question considers an $n\times n$-matrix $\ d,\ $ which is in fact a pseudo-matrix in the n-space $\ X:=\{1\ldots n\}.\ $ The goal is to study vectors $\ t\in\mathbb R^n,\ $ called coordinates, which satisfy the condition:

$$\forall_{w\ x\,\in\, X}\ \ |t(w)-t(x)|\le d(w\ x)$$

plus the restriction to the integer values. Even for general real values, I will still call such functions $\ t\ $ (vectors)--coordinates.

Let me consider the special case of an arbitrary metrics $\ d\ $ (rather than a pseudo-metrics), and let it be defined in an arbitrary set $\ X,\ $ so that we consider arbitrary metric spaces $\ (X\ d)\ $ (in full generality). I hope that my notion of metric space $\ Aim(X),\ $ which is closely related to the coordinates, will help the task of finding all coordinates. The reference is: wh, On metric spaces aimed at their subspaces, Prace Matematyczne X (1966), pp.95-100.

First observe that every superspace $\ (Y\ d')\ $ of $\ (X\ d)\ $ is a source of (generalized) coordinates; namely, every function $\ t:=t_y,\ $ defined by:

$$\forall_{x\in X}\ \ t_y(x) := d'(x\ y)$$

is a coordinate.

A large supply of such coordinates can be obtained from a single space $\ Aim(X),\ $defined below. Perhaps the study of all coordinates can be reduced to functions $\ t_y.\ $When possible, it should be rather more convenient to analyze just one space rather than a huge number of the. Here is the definition of $\ Aim(X)$:

Space $\ Aim(X)\ $ is the space of all functions $\ t:X\rightarrow\mathbb R\ $ such that:

$$\forall_{x\in X}\ \sup_{y\in X} |d(x\ y)-t(y)|\ =\ t(x)$$

This condition is equivalent to:

$$\forall_{x\ y\in X}\ t(x)+t(y)\ \ge\ d(x\ y)\ \ge t(x)-t(y)$$

This last version is similar but more restrictive than the coordinate condition.

The space $\ Aim(X)\ $ is equipped with the uniform metrics. This space consists of functions obtained in a way described earlier above from all super-spaces $\ (Y\ d')\ $ which are aimed at $\ X,\ $ meaning that:

$$\forall_{p\ q\in Y}\forall_{\epsilon > 0}\exists_{x\in X}\,\ |d'(p\ x)-d'(q\ x)|+\epsilon\ >\ d'(p\ q)$$

This is what I meat by large supply. Actually, if we identify (isometrically) $\ X\ $ with the subspace of $\ Aim(X)\ $ of all functions $\ t_x\ (x\in X)\ $ such that $\ \forall_{w\in X}\ t_x(w):=d(w\ x),\ $ then space $\ Aim(X)\ $ is aimed at $\ X$, and it is universal in this respect (by the way, it follows that spaces aimed at any fixed space $\ X\ $ cannot be arbitrarily large).

The Question asks about  Any idea of how to approach this,  and at this time this is my idea, a bit raw though. Perhaps the study of all coordinates can be reduced to $\ Aim(X)$.