06 - Distance Functions

Distance Function

Let $X$ be a set

A distance function on $X$ is a function $d:X\times X\to \mathbb{R}$ with (for all $x,y,z\in X$)

1. Positivity:

$$d(x,y)\ge 0\text{ and }d(x,y)=0⟺x=y$$

2. Symmetry:

$$d(x,y)=d(y,x)$$

3. Triangle Inequality:

$$d(x,z)\le d(x,y)+d(y,z)$$

Examples of Distance Functions

Take $X={\mathbb{R}}^n$ then define the following on $X$

$$\begin{array}{rl}{d}_1(v,w)& =\sum _{i=1}^n|v_i-w_i|\\ d_2(v,w)& ={\left(\sum _{i=1}^n(v_i-w_i{)}^2\right)}^{1/2}\\ d_{\infty }(v,w)& =\underset{i\in \{1,2,\cdots ,n\}}{\max }|v_i-w_i|\end{array}$$

Relation of $d_2$ to Euclidean Norm Euclidean Norm $||v|{|}_2$ of a vector $v=(v_1,\cdots ,v_n)\in {\mathbb{R}}^n$ is

$$||v|{|}_2:={\left(\sum _{i=1}^n|v_i{|}^2\right)}^{1/2}=⟨v,v{⟩}^{1/2}$$

where the inner product is defined by

$$⟨v,w⟩=\sum _{i=1}^n{v}_i{w}_i$$

Hence $d_2(v,w)=||v-w|{|}_2$ so the triangle inequality is

$$||u-w|{|}_2\le ||u-v|{|}_2+||v-w|{|}_2$$

Property of Euclidean Norm lemma If $x,y\in {\mathbb{R}}^n$ then

$$||x+y|{|}_2\le ||x|{|}_2+||y|{|}_2$$

Proof

Since $||v|{|}_2\ge 0$ for all $v\in {\mathbb{R}}^n$ then the inequality is equivalent to

$$||x+y|{|}_2^2\le ||x|{|}_2^2+2||x|{|}_2||y|{|}_2+||y|{|}_2^2$$

As $||x+y|{|}_2^2=⟨x+y,x+y⟩=||x|{|}_2^2+2⟨x,y⟩+||y|{|}_2^2$
Then by Cauchy-Schawrz Inequality

$$|⟨x,y⟩|\le ||x|{|}_2||y|{|}_2$$

Hence the result follows by the above inequality