We call an $n\times n$-matrix ${\bf A}\in \text{Mat}(n\times n, \mathbb{R})$ a *metric matrix* if


1. ${\bf A}\_{ii} = 0$ for all $i\in \{1,\ldots,n\}$,
2. ${\bf A}\_{ij} = {\bf A}\_{ji}$ for all $i,j \in \{1,\ldots,n\}$ (that is, ${\bf A}$ is symmetric), and
3. ${\bf A}\_{ik} \leq {\bf A}\_{ij} + {\bf A}\_{jk}$ for all $i,j,k \in \{1,\ldots, n\}$ (that is, the triangle inequality holds).


We say that ${\bf A}\in \text{Mat}(n\times n, \mathbb{R})$ is $\mathbb{R}^k$-*realizable* for some positive integer $k$ if there is a subset $S\subseteq \mathbb{R}^k$ having $n$ elements, and a bijection $\varphi:\{1,\ldots,n\}\to S$ such that
$$\|\varphi(i) - \varphi(j)\| = {\bf A}\_{ij} \text{ for all } i,j\in \{1,\ldots n\}.$$


(Note that $\|\cdot\|$ denotes the Euclidean norm.) So for instance, the following metric matrix ${\bf A}\in \text{Mat}(4\times 4, \mathbb{R})$ is not $\mathbb{R}^2$-realizable, but it is $\mathbb{R}^3$-realizable:


$${\bf A} = \begin{pmatrix}
0 & 1 & 1 & 1\\
1 & 0 & 1 & 1\\
1 & 1 & 0 & 1\\
1 & 1 & 1 & 0\\
\end{pmatrix}$$


**Questions.** (Only the first question needs to be answered for acceptance.)


1. Given an integer $n>1$, is every metric $n\times n$-matrix $\mathbb{R}^{n-1}$-realisable?
2. For every metric matrix ${\bf A}\in \text{Mat}(n\times n, \mathbb{N})$ let its *metric dimension* $\text{mdim}({\bf A})$ denote the smallest positive integer $k$ such that ${\bf A}$ is $\mathbb{R}^k$-realizable. Is the problem of finding $\text{mdim}({\bf A})$ given ${\bf A}\in \text{Mat}(n\times n, \mathbb{N})$ a polynomial-time problem with respect to $n$?



Realizability of metric matrices
In other words, you ask whether every finite metric space may be isometrically embedded to Euclidean space $\mathbb{R}^n$. Not every. A necessary and sufficient condition is given by the non-negativity of the so called [Cayley--Menger determinants](https://en.m.wikipedia.org/wiki/Cayley%E2%80%93Menger_determinant).


