Exercise 3 (20 points):
Assume two d-dimensional real vectors x and y. And denote by xi (yi) the value in the i-th coordinate of x (y). Prove or disprove the following statements:
A distance function that satisfies all the below properties is called a metric
- non-negativity, \(d\left(x,y\right)\ge0\)
- isolation, \(d\left(x,y\right)=0\ \Leftrightarrow\ x=y\)
- symmetry, \(d\left(x,y\right)=d\left(y,x\right)\)
- triangle inequality ,\(d\left(x,z\right)\le d\left(x,y\right)+d\left(y,z\right)\)
Proof:
1. Distance function =\(L_1\left(x,y\right)=\sum_{i=1}^d\left|x_{i-}y_i\right|\) is a metric. (5 points)
i. non-negativity:-
\(Consider\ D\left(x,y\right)\ge0\ \forall\ x,y\ \epsilon\ R\) --------------------- equation 1
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|-x_i+y_i\right|\)
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|-1\right|\left|x_i-y_i\right|\) (because \(\left|x-y\right|=\ \ \left|-1\right|\cdot\left|y-x\right|\))
\(\Rightarrow\ D\left(-x,-y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
Using Equation 1 we can say that \(\ D\left(-x,-y\right)\ge0\)
Alternate Proof: The formula consists of a sum of a modulus (|x-y|)which would always be positive for all values of x and y because modulus of a number is always positive.
ii. Isolation
\(d\left(x,y\right)=0\ \Leftrightarrow\ x=y\)
\(Given\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
Considering x=y
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|x_i-x_i\right|\) (because x=y)
\(\Rightarrow\ D\left(x,y\right)=\sum_{i=1}^d\left|0\right|=0\)
iii. Symmetry
\(d\left(x,y\right)=d\left(y,x\right)\)
\(D\left(x,y\right)=\sum_{i=1}^d\left|x_i-y_i\right|\)
\(D\left(y,x\right)=\sum_{i=1}^d\left|y_i-x_i\right|\)
if \(x-y\ge0\) then \(y-x\le0\) | if \(x-y\le0\) then \(y-x\ge0\)
\(\Rightarrow\left|x-y\right|=x-y\) and \(\Rightarrow\left|y-x\right|=x-y\) | \(\Rightarrow\left|x-y\right|=y-x\) and \(\Rightarrow\left|y-x\right|=y-x\)
\(\Rightarrow\sum_{i=1}^d\left|x_i-y_i\right|=\sum_{i=1}^d\left|y_i-x_i\right|\) | \(\Rightarrow\sum_{i=1}^d\left|x_i-y_i\right|=\sum_{i=1}^d\left|y_i-x_i\right|\)
Therefore,
\(D\left(x,y\right)=D\left(y,x\right)\)
iv. triangle inequality ,
\(d\left(x,z\right)\le d\left(x,y\right)+d\left(y,z\right)\)
\(\left|x-z\right|\le\left|x-y\right|+\left|y-z\right|\)
Using triangle inequality for absolute values
Thus \(d\left(x,z\right)\le d\left(x,y\right)+d\left(y,z\right)\)
Since all 4 properties are satisfied by the distance function it is a metric.
2. . Distance function =\(L_2\left(x,y\right)=\sqrt{\sum_{i=1}^d\left(x_{i-}y_i\right)^2}\) is a metric. (5 points)
i. non-negativity:-
\(D\left(x,y\right)=\sqrt{\sum_{i=1}^d\left(x_{i-}y_i\right)^2}\)
Since \(\left(x-y\right)^2\ \ge0\ \forall\ x,y\ \epsilon\ R\)
\(\Rightarrow\sum_{i=1}^d\left(x_{i-}y_i\right)^2\ge0\) (summation of all positive numbers)
\(\Rightarrow\sqrt{\sum_{i=1}^d\left(x_{i-}y_i\right)^2\ \ }\ \ge0\)
ii. Isolation(definiteness)