TDSM 10.1
To prove that Euclidean distance is in fact a metric, we should prove these facts:
1.d(x,y)≥0
2.d(x,y)=0 if and only if x=y
3.d(x,y)=d(y,x) for all x,y
4.d(x,y)≤d(x,z)+d(z,y) for all x,y,z
The Euclidean metric is defined as:
d(x,y)=√D∑i=1|xi−yi|2
1. It is clear that d(x,y)≥0
2. d(x,x)=√D∑i=1|xi−xi|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,xi=yi then x=y
3. d(x,y)=√D∑i=1|xi−yi|2=√D∑i=1|yi−xi|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=(x1,…,xD) and y=(y1,…,yD) then: |D∑i=1xiyi|≤(D∑i=1x2i)1/2(D∑i=1y2i)1/2
Proof: Since |D∑i=1xiyi|≤D∑i=1|xi||yi| it is sufficient to prove the inequality for xi,yi≥0. Furthermore, the inequality is obvious if either x=0 or y=0 so we assume at least one xi and one yi is nonzero.
For every α,β∈R we have:
0≤D∑i=1(αxi−βyi)2
Expanding the square on the right-hand side and rearranging the terms, we get that:
2αβD∑i=1xiyi≤α2D∑i=1x2i+β2D∑i=1y2i
we choose:
α=(D∑i=1y2i)1/2 , β=(D∑i=1x2i)1/2
Then division of the resulting inequality by 2αβ proves the theorem.
we know that x⋅y=x1y1+⋯+xDyD and |x|=√x⋅x and d(x,y)=|x−y|
by using Cauchy-Schwartz we have:
(x+y)2=(x+y)(x+y)=|x2|+2(xy)+|y2|≤|x2|+2|xy|+|y2|≤|x2|+2|x||y|+|y2|=(|x|+|y|)2
which results in:
x+y≤|x|+|y|
now consider 3 points:
d(x,y)=|x−y|=|x−z+z−y|≤|x−z|+|z−y|=d(x,z)+d(z,y)