TDSM 10.1

To prove that Euclidean distance is in fact a metric, we should prove these facts:

$$1.\hspace{0.2cm}d(x,y) \geq 0$$

$$2.\hspace{0.2cm}d(x,y) =0\hspace{0.2cm}\text{ if and only if } x=y$$

$$3.\hspace{0.2cm}d(x,y) =d(y,x)\text{ for all } x,y$$

$$4.\hspace{0.2cm}d(x,y) \leq d(x,z) + d(z,y)\text{ for all } x,y,z$$

The Euclidean metric is defined as:

$$d(x,y) = \sqrt{\sum_{i=1}^{D}{\left|x_i-y_i\right|^2}}$$

1. It is clear that $$d(x,y) \geq 0$$

2. $$d(x,x) = \sqrt{\sum_{i=1}^{D}{\left|x_i-x_i\right|^2}} = 0$$ and if $$d(x,x) = 0$$ then sum of some nonnegative terms is 0, so all of them should be zero then for all $$i,x_i=y_i$$ then $$x=y$$

3. $$d(x,y) = \sqrt{\sum_{i=1}^{D}{\left|x_i-y_i\right|^2}} = \sqrt{\sum_{i=1}^{D}{\left|y_i-x_i\right|^2}} = d(y,x)$$

4. To prove this fact, we first prove Cauchy-Schwartz and then using this theorem we can prove this fact.

Cauchy-Schwartz theorem: if $$x=(x_1,…,x_D)$$ and $$y=(y_1,…,y_D)$$ then: $$\left| \sum_{i=1}^{D}x_iy_i\right| \leq (\sum_{i=1}^{D}x_i^2)^{1/2} (\sum_{i=1}^{D}y_i^2)^{1/2}$$

Proof: Since $$\left| \sum_{i=1}^{D}x_iy_i \right| \leq \sum_{i=1}^{D} \left|x_i\right|\left|y_i\right|$$ it is sufficient to prove the inequality for $$x_i,y_i \geq 0$$ . Furthermore, the inequality is obvious if either $$x=0$$ or $$y=0$$ so we assume at least one $$x_i$$ and one $$y_i$$ is nonzero.

For every $$\alpha,\beta\in {\Bbb R}$$ we have:

$$0 \leq \sum_{i=1}^{D}(\alpha x_i-\beta y_i)^2$$

Expanding the square on the right-hand side and rearranging the terms, we get that:

$$2\alpha \beta \sum_{i=1}^{D}x_iy_i \leq \alpha^2 \sum_{i=1}^{D}x_i^2 + \beta^2 \sum_{i=1}^{D}y_i^2$$

we choose:

$$\alpha =(\sum_{i=1}^{D}y_i^2)^{1/2}$$ , $$\beta =(\sum_{i=1}^{D}x_i^2)^{1/2}$$

Then division of the resulting inequality by $$2 \alpha \beta$$ proves the theorem.

we know that $$x⋅y=x_1y_1+⋯+x_Dy_D$$ and $$\left|x\right|=\sqrt{x⋅x}$$ and $$d(x,y)=|x−y|$$

by using Cauchy-Schwartz we have:

$$(x+y)^2=(x+y)(x+y)=\left|x^2\right|+2(xy)+\left|y^2\right|\leq \left| x^2 \right|+ 2\left| xy \right| +\left|y^2\right| \leq \left| x^2 \right|+ 2\left| x \right| \left| y \right| +\left|y^2\right| = (\left| x \right| + \left| y \right|) ^2$$

which results in:

$$x+y \leq \left| x \right| + \left| y \right|$$

now consider 3 points:

$$d(x,y)=\left|x-y\right| = \left|x-z+z-y\right| \leq \left|x-z\right| + \left|z-y\right| = d(x,z)+d(z,y)$$