Realizability of metric matrices

Question

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

Answer 1

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.