Find out whether a matrix is a distance matrix or not I have a $5 \times 5$ symmetric matrix $A$ with zeroes on the diagonal and I am supposed to find whether there exist 5 points in $\mathbb R^4$ such that $A$ is the distance matrix. How can I solve this formally? I am guessing I have to use a Gram matrix but I don't know what to do after that...
Here is the matrix:  $$A= \begin{pmatrix}
0 &1 &2 &2 &2\sqrt 2\\
1& 0 &\sqrt5 &\sqrt5 &3 \\
2 &\sqrt5 &0 &2\sqrt2 &2\\
2 &\sqrt5 & 2\sqrt2 &0 &2\sqrt3\\
2\sqrt2 & 3 &2 &2\sqrt3 &0
\end{pmatrix}.$$
Edit. I got stuck when I tried to use the technique proposed by user1551 on this matrix
$$ \begin{pmatrix}
0& \sqrt5 &  \sqrt5 &  \sqrt5 & \sqrt5 \\
 \sqrt5 & 0&  2\sqrt5 &  2\sqrt2 & 2\\
\sqrt5  &2\sqrt5 & 0 & 2 & 2\sqrt2 \\
 \sqrt5 &  2\sqrt2 & 2 & 0 &2 \sqrt5 &\\
 \sqrt5 & 2 & 2\sqrt2 & 2 \sqrt5 &0\\
\end{pmatrix}.$$
The problem arises when I try to compute $x_3$. I obtained the following system:
$$-2\begin{pmatrix}
 \sqrt5 &  0\\
-\sqrt5 &0 \\
\end{pmatrix}
\begin{pmatrix}
x_{31}\\
x_{32}\\
\end{pmatrix}
=\begin{pmatrix}
10\\
-1\\
\end{pmatrix}.$$
 A: Suppose we want to find $n+1$ vectors $x_0,x_1,\ldots,x_n$ in $\mathbb{R}^n$ such that the distance $d_{ij}$ between every two vectors $x_i,x_j$ is given. By translation, we may assume WLOG that $x_0=0$. Let $X=(x_1,\ldots,x_n)$. Since real orthogonal matrices are isometries, by performing a QR factorization, we may assume WLOG that $X$ is upper triangular. That is, for each $k$, the $(k+1)$-th, $(k+2)$-th, ... up to $n$-th coordinates of the vector $x_k$ are zero. Furthermore, we may assume that $x_{kk}$, the $k$-th coordinate of the vector $x_k$, is nonnegative.
So we may determine $x_k$ inductively. Suppose $x_0,\ldots,x_{k-1}$ are known. We want to find the vector $x_k=(x_{k1},x_{k2},\ldots,x_{kk},0,\ldots,0)^T$ (so that $X^T=(x_{ij})$). By assumption,
\begin{equation}
\sum_{j=1}^k(x_{kj}-x_{ij})^2 = d_{ik}^2\tag{$\dagger$}
\end{equation}
for $i=0,1,\ldots,k-1$. Subtract the equation with $i=0$ from the others and make use of the fact that $x_{ij}=0$ for $j>i$, we get a triangular system of $k-1$ linear equations
$$
2\begin{bmatrix}
x_{11}\\
x_{21}&x_{22}\\
\vdots&&\ddots\\
x_{k-1,1}&x_{k-1,2}&\cdots&x_{k-1,k-1}\\
\end{bmatrix}
\begin{bmatrix}x_{k1}\\x_{k2}\\ \vdots\\x_{k,k-1}\end{bmatrix}
=\begin{bmatrix}
d_{1k}^2-\|x_1\|^2\\
d_{2k}^2-\|x_2\|^2\\
\vdots\\
d_{k-1k}^2-\|x_{k-1}\|^2
\end{bmatrix}
-(d_{0k}^2-\|x_0\|^2)
\begin{bmatrix}1\\1\\ \vdots\\1\\\end{bmatrix}.
$$
Therefore $x_{k1},x_{k2},\ldots,x_{k,k-1}$ can be solved by forward substitution. Now the coefficient $x_{kk}$ can be recovered from ($\dagger$) with $i=0$, i.e. $x_{kk} = \sqrt{d_{0k}^2-\sum_{j=1}^{k-1} x_{kj}^2}$. So, the point $x_k$ exists if and only if the above triangular system is solvable (which is true if $x_{11},\ldots,x_{k-1,k-1}\not=0$) and $d_{0k}^2\ge\sum_{j=1}^{k-1} x_{kj}^2$. For your particular case, the five points can be chosen as $(0,0,0,0)$, $(1,0,0,0)$, $(0,2,0,0)$, $(0,0,2,0)$ and $(0,2,0,2)$.
