6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Where does this problem come from? Also, have you checked the first couple of cases $n\in\{1,2,3\}$ by hand? $\endgroup$ – Joonas Ilmavirta Nov 4 '14 at 18:11
  • $\begingroup$ @JoonasIlmavirta: I agree with you, I should have written it. Added some explanation for where this question comes from. $\endgroup$ – real Nov 4 '14 at 18:23
  • $\begingroup$ @JoonasIlmavirta: It's a good idea to begin with. Probably by computer program is better than by hand :) $\endgroup$ – real Nov 4 '14 at 18:24
  • 1
    $\begingroup$ I have an association with a basic level research done by Andrzej Ehrenfeucht on the very notion of the metric space. $\endgroup$ – Włodzimierz Holsztyński Nov 4 '14 at 22:46
  • $\begingroup$ You mean this? $\endgroup$ – real Nov 5 '14 at 9:58
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I'm really sorry, I forgot to note that in my question D is symmetric and there are zeroes on the main diagonal. (The assumption that $d(a,b) \geq 0$ was already written though.) $\endgroup$ – real Nov 5 '14 at 5:16
  • $\begingroup$ What do you mean by pairwise different? What do you want to assume to be different? $\endgroup$ – real Nov 5 '14 at 5:19
  • $\begingroup$ Pairwise different terms of the sequence $\ a_1\ldots a_m.\ $ Thank you, @real, for clarifying the assumptions about $\ D$. $\endgroup$ – Włodzimierz Holsztyński Nov 5 '14 at 5:42
  • $\begingroup$ (Indeed, the assumption that $\ d(a\ b)\ge 0\ $ was present already in the original formulation of the Question; I overlooked it at the time.) $\endgroup$ – Włodzimierz Holsztyński Nov 5 '14 at 16:08
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thank you for the great investment in writing this idea. It is very different from the way I try to solve the question. How do you plan to move from $\mathbb{R}$ to counting in $\mathbb{N}$? $\endgroup$ – real Nov 5 '14 at 19:13
  • $\begingroup$ I don't have a straight answer. Thus let me say the possible key word: volume. $\endgroup$ – Włodzimierz Holsztyński Nov 7 '14 at 3:27

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.