Dimensionality of a map -- distance

Question

Hello, I am looking for some words to describe what going on here. I'm sure this is not an original thought, so I'd like to read up on more from others who have thought out this topic further.

FORMAT The problem is stated in a square matrix, consider the rows and columns having identical labels (labels are shown below but are not part of the matrix):

  A B C D
A 0 1 2 3
B 1 0 1 2 
C 2 1 0 1
D 3 2 1 0

This matrix represents the distance between each row and column. In this case the dimensionality of the matrix is one, because the labels [1 2 3 4] can be plotted on the number line (say, at 1, 2, 3, 4, respectively) such that the distance between each point exactly matches the matrix.

THE QUESTION What is this called? Is there an algorithm to determine the dimensionality of such a matrix? Is there any sense in thinking of a non-integer number of dimensions? Are there any other interesting questions that can be asked along this line of thought?

Answer 1

Testing whether $n$ points "need" $n-1$ dimensions (in the way you're referring to) using only their distances is done via Cayley-Menger determinants : http://mathworld.wolfram.com/Cayley-MengerDeterminant.html

More generally, you might want to take a look at this : http://en.wikipedia.org/wiki/Distance_geometry

Answer 2

I guess what you want to say is this: one defines a distance function $d$ on the set $\{ A,B,C,D \}$ of four elements through setting $d(A,A)=0$, $d(A,B)=1$, $d(A,C)=2$ and so on. Of course one can put the various values of the distance function into a matrix as you did, but if I understaand your problem correctly this is not the point.

What you call "one-dimensional" is the fact that one can find a map $f: \{A,B,C,D\}\rightarrow\mathbb{R}$ that preserves the distances using the ordinary absolute value in the reals to define the distance between to numbers. So this map satisfies for example $d(A,B)=|f(A)-f(B)|$, and similar for the other point combinations. Of course this is a particular property of the map $d$: if you would define a distance map $e$ through $e(A,B)=1$, $e(B,C)=1$ and $e(A,C)=1$ then you could not find such a map $f$.

One way to generalize this problem is this one: consider a finite metric space $(X,d)$, that is a finite set equipped with a function $d:X\times X\rightarrow\mathbb{R}^{\geq 0}$ satisfying the following properties: $d(x,x)=0$ for all $x\in X$, $d(x,y)=d(y,x)$ for all $x,y\in X$ and $d(x,y)\leq d(x,z)+d(z,y)$ for all $x,y,z\in X$. Does there exist a map $f:X\rightarrow\mathbb{R}^n$ for some $n\in\mathbb{N}$ that preserves the distances taking the euclidean distance in the space $\mathbb{R}^n$. Such problems are treated in the theory of finite metric spaces. They occur naturally in Data Mining or theoretical computer science.