0

In a book I own, it states:

Let $m_{ij}, i,j=0,1,\dots ,n,$ be nonnegative real numbers with $m_{ij}=m_{ji}$ for all $i,j$ and $m_{ii} = 0$ for all $i$. Then points $\mathbf{p}_0,\mathbf{p}_1,\dots ,\mathbf{p}_n \in \mathbb{R}^n$ with $|| \mathbf{p}_i-\mathbf{p}_j || = m_{ij}$ for all $i,j$ exist if and only if the $n\times n$ matrix $G$ with $$g_{ij} = \frac{1}{2} \left( m_{oi}^2+ m_{0j}^2-m_{ij}^2 \right) $$ is positive semidefinite.

Proof of the theorem. First we check necessity: If $\mathbf{p}_0,\mathbf{p}_1,\dots ,\mathbf{p}_n$ are given points in $\mathbb{R}^n$ and $m_{ij} := ||\mathbf{p_i āˆ’ p_j}||$, then $G$ as in the theorem is positive semidefinite.

For this, we need the cosine theorem, with tells us that $||\mathbf{x-y}||^2 = ||\mathbf{x} ||^2 + ||\mathbf{y} || ^2 - 2\langle \mathbf{x,y} \rangle$ for any two vectors $\mathbf{x, y} \in \mathbb{R} ^n$. Thus, if we define $\mathbf{x_i} := \mathbf{p_iāˆ’p_0}, i = 1, 2, \dots , n$, we get that $\langle \mathbf{x_i,x_j} \rangle = \frac{1}{2}(||\mathbf{x_i} || ^2 + ||\mathbf{x_j} || ^2 - ||\mathbf{x_i-x_j}||^2 ) = g_{ij}$. So $G$ is the Gram matrix of the vectors $\mathbf{x_i}$, we can write $G = X^T X$, and hence $G$ is positive semidefinite.

Conversely, if $G$ is positive semidefinite, we can decompose it as $G = X^T X$ for some $n \times n$ real matrix $X$. Then we let $\mathbf{p_i} \in \mathbb{R} ^n$ be the $i$th column of $X$ for $i = 1, 2,\dots , n$, while $\mathbf{p_0} := 0$. Reversing the above calculation, we arrive at $||\mathbf{p_i āˆ’ p_j} || = m_{ij}$, and the proof is finished.

I understood the proof until the very last sentence, where it states, "Reversing the above calculation." From here, I wasn't sure what it was referring to, and I couldn't figure it out on my own. Can someone elaborate on the last sentence? Thanks in advance.

donguri
  • 320

2 Answers2

1

With this choice of points $\mathbf{p_i}$, we have for $i, j>0$ \begin{equation} g_{ii} = \langle x_i, x_i\rangle = \langle p_i-p_0, p_i-p_0\rangle = ||p_i-p_0||^2 = m_{0i}^2 \end{equation} and \begin{equation} g_{ij} = \langle x_i, x_j\rangle = \frac{1}{2}\left(||x_i||^2 + ||x_j||^2 -||x_i-x_j||^2\right) = \frac{1}{2}\left(m_{0i}^2+ m_{0j}^2-||p_i-p_j||^2\right) \end{equation} This implies $||p_i-p_j||^2 = m_{ij}^2$

Gribouillis
  • 14,188
0

You have to prove a statement like $A \iff B $.

In general, the structure of a proof where the reversing process can be justified is : $$A \iff P_1 \iff P_2 \iff ... \iff B $$ and so you can prove the biconditional just by doing the same operations in reverse($\impliedby$) , starting from the $B$ statement.

Tortar
  • 3,980