# Is there an algorithm to find the minimal number of dimensions, given the distances between points?

Given some finite set $$S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$$ we can define a distance matrix $$D = (d(i,j))_{ij}$$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$

where $$\Vert \cdot \Vert$$ is the euclidean norm.

Is there an algorithm to determine the minimal $$m$$ just from $$D$$ such that there are $$\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$$ with $$d(i,j) = \Vert{y_i -y_j}\Vert$$?

Or equivalently: Given $$D$$ as well as some $$m$$, can we determine whether $$D$$ can stem from $$k$$ points in $$\mathbb R^m$$?

This problem of minimal dimensionality has been studied intensively.

Here is a slightly-edited excerpt from Learning metrics via discriminant kernels and multidimensional scaling: Toward expected euclidean representation by Zhihua Zhang, Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.

Definition 1 (Gower & Legendre, 1986) An $$m × m$$ matrix $$[a_{ij} ]$$ is Euclidean if $$m$$ points $$P_i$$ $$(i = 1, . . . , m)$$ can be embedded in an Euclidean space such that the Euclidean distance between $$P_i$$ and $$P_j$$ is $$a_{ij}$$.

The following theorem provides the conditions for a matrix to be Euclidean.

Theorem 1 (Gower & Legendre, 1986) The matrix $$[a_{ij}]$$ is Euclidean if and only if $$H^{\text{tr}}BH$$ is positive semi-definite, where $$B$$ is the matrix with elements $${-\frac12}{a_{ij}}^2$$ and $$H = (I − \mathcal 1_ms)$$ is a centering matrix where $$I$$ is the identity matrix, $$\mathcal 1_m$$ is the $$m \times 1$$ vector $$(1, 1, \cdots , 1)$$ and $$s$$ is a $$1\times m$$ vector satisfying $$s\mathcal 1_m = 1$$.

Note that in theorem 1, if the condition is true for one choice of $$s$$ (say $$s=e_i$$, the vector whose entry is 1 at $$i$$-th position and whose entries are 0 otherwise), it is true for every valid choice of $$s$$. That fact is included in Metric and Euclidean properties of dissimilarity coefficients by Gower & Legendre, 1986.

Thanks to theorem 1, we know the minimal $$m$$ such that there are $$\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$$ with $$d(i,j) = \Vert{y_i -y_j}\Vert$$ is one less than the minimum order of non-Eucidean sub-square-matrix of $$[d(i,j)]$$. A simple algorithm to compute that minimum order is to iterate through all submatrix (that allow non-consecutive rows or columns) of $$[d(i,j)]$$, checking whether each submatrix is Euclidean.

For more related information, we can read that article and dig further.

• Thanks that is exactly what I'm looking for! – flawr Jan 29 at 22:15
• Unfortunately this is an instance where the formulation of the theorem does not allow to determine whether it has to hold for one $s$ or every $s$. – flawr Jan 29 at 22:24
• Apparently it is sufficient to hold for just one such $s$: "It is easy to show that if the result is true for one choice of s (say $s = e_i$) it is true for every valid choice of $s$." (from the original "Metric and Euclidean properties of dissimilarity coefficients" by Gower & Legendre,1986) – flawr Jan 29 at 22:24