Dimensionality of a map -- distance - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:39:54Z http://mathoverflow.net/feeds/question/63291 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63291/dimensionality-of-a-map-distance Dimensionality of a map -- distance fulldecent 2011-04-28T12:11:06Z 2011-04-28T15:53:29Z <p>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.</p> <p><strong>FORMAT</strong> 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):</p> <pre><code> A B C D A 0 1 2 3 B 1 0 1 2 C 2 1 0 1 D 3 2 1 0 </code></pre> <p>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.</p> <p><strong>THE QUESTION</strong> 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?</p> http://mathoverflow.net/questions/63291/dimensionality-of-a-map-distance/63297#63297 Answer by Hagen for Dimensionality of a map -- distance Hagen 2011-04-28T14:03:08Z 2011-04-28T14:03:08Z <p>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.</p> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/63291/dimensionality-of-a-map-distance/63305#63305 Answer by Arnaud for Dimensionality of a map -- distance Arnaud 2011-04-28T15:53:29Z 2011-04-28T15:53:29Z <p>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 : <a href="http://mathworld.wolfram.com/Cayley-MengerDeterminant.html" rel="nofollow">http://mathworld.wolfram.com/Cayley-MengerDeterminant.html</a></p> <p>More generally, you might want to take a look at this : <a href="http://en.wikipedia.org/wiki/Distance_geometry" rel="nofollow">http://en.wikipedia.org/wiki/Distance_geometry</a></p>