Technology and Art
This post lists solutions to many of the exercises in the Distance Metrics section 1.1 of Erwin Kreyszig’s Introductory Functional Analysis with Applications. This is definitely a work in progress, and proofs may be refined or added over time.
Proof:
For the distance metric \(d(x,y)={(x-y)}^2\), we need to prove or disprove the Triangle Inequality:
\[d(x,z) \leq d(x,y) + d(y,z)\]We start with the term \({(x-z)}^2\), as follows:
\[{(x-z)}^2 = {((x-y)+(y-z))}^2 \\ \Rightarrow {(x-z)}^2 = {(x-y)}^2 + {(y-z)}^2 + 2 (x-y) (y-z) \\ \Rightarrow d(x,z) = d(x,y) + d(y,z) + \underbrace{2 (x-y) (y-z)}_\text{positive or negative}\]When the term \(2 (x-y) (y-z)\) is positive:
\[d(x,z) > d(x,y) + d(y,z)\]When the term \(2 (x-y) (y-z)\) is negative or zero:
\[d(x,z) \leq d(x,y) + d(y,z)\]Thus, the Triangle Inequality can only be satisfied for specific values of \(x\), \(y\), and \(z\); hence \(d(x,y)={(x-y)}^2\) is not a valid distance metric.
\[\blacksquare\]Proof:
For the distance metric \(d(x,y)=\sqrt{\vert x-y \vert}\), we need to prove the Triangle Inequality:
\[d(x,z) \leq d(x,y) + d(y,z)\]We start with the basic Triangle Inequality for \(\mathbb{R}\):
\[|x-z| \leq |x-y| + |y-z|\]Adding and subtracting \(2 \sqrt{\vert x-y \vert \vert y-z \vert}\) on the RHS we get:
\[|x-z| \leq |x-y| + |y-z| + 2 \sqrt{\vert x-y \vert \vert y-x \vert} - 2 \sqrt{\vert x-y \vert \vert y-z \vert} \\ \Rightarrow |x-z| \leq {(\sqrt{\vert x-y \vert} + \sqrt{\vert y-z \vert})}^2 - \underbrace{2 \sqrt{\vert x-y \vert \vert y-z \vert}}_\text{positive}\]Setting \(C=2 \sqrt{\vert x-y \vert \vert y-z \vert}>0\), we get:
\[|x-z| \leq {\left(\sqrt{\vert x-y \vert} + \sqrt{\vert y-z \vert}\right)}^2 - C \\ \Rightarrow {\left(\sqrt{\vert x-z \vert}\right)}^2 \leq {\left(\sqrt{\vert x-y \vert} + \sqrt{\vert y-z \vert}\right)}^2 - C \\ \Rightarrow {\left(\sqrt{\vert x-z \vert}\right)}^2 + C \leq {\left(\sqrt{\vert x-y \vert} + \sqrt{\vert y-z \vert}\right)}^2 \\ \Rightarrow {\left(\sqrt{\vert x-z \vert}\right)}^2 \leq {\left(\sqrt{\vert x-y \vert} + \sqrt{\vert y-z \vert}\right)}^2 \\ \Rightarrow \sqrt{\vert x-z \vert} \leq \sqrt{\vert x-y \vert} + \sqrt{\vert y-z \vert} \\ \Rightarrow d(x,z) \leq d(x,y) + d(y,z)\]Hence, this proves the Triangle Inequality, and consequently, \(d(x,y)=\sqrt{\vert x-y \vert}\) is a valid distance metric.
\[\blacksquare\](i) Proof:
Let \(\bar{d}(x,y)=kd(x,y)\) be a candidate metric on \(X\). For it to be a valid distance metric, it must satisfy the four axioms of a metric, i.e.:
\(\bar{d}(x,z) \leq \bar{d}(x,y) + \bar{d}(y,z)\): For this, if we multiply the original, valid Triangle Inequality by \(k\) on both sides, we have the following:
\[kd(x,z) \leq k[d(x,y) + d(y,z)] \\ \Rightarrow kd(x,z) \leq kd(x,y) + kd(y,z) \\ \Rightarrow \bar{d}(x,z) \leq \bar{d}(x,y) + \bar{d}(y,z)\]proving that the Triangle Inequality holds for \(\bar{d}\) for any \(k \in \mathbb{R}\).
Putting all of these together, we get the condition that \(k>0, k \in \mathbb{R}\).
(ii) Proof:
Let \(\bar{d}(x,y)=d(x,y) + k\) be a candidate metric on \(X\). For it to be a valid distance metric, it must satisfy the four axioms of a metric, i.e.:
\(\bar{d}(x,z) \leq \bar{d}(x,y) + \bar{d}(y,z)\): For this, we can note the following:
\[d(x,z) + k \leq k[d(x,y) + d(y,z)] + 2k \\ \Rightarrow d(x,z) + k \leq [d(x,y) + k] + [d(y,z) + k] \\ \Rightarrow \bar{d}(x,z) \leq \bar{d}(x,y) + \bar{d}(y,z)\]proving that the Triangle Inequality holds for \(\bar{d}\) for any \(k \in \mathbb{R}\).
Putting all of these together, we get the condition that \(k=0, k \in \mathbb{R}\).
[TODO]
[TODO]
[TODO]
Proof:
The set of all ordered triples of zeros and ones, forms a sequence of numbers \(X=[0,7], x_i \in X, x_i \in \mathbb{Z}\) in their binary form. Thus, it is evident that the number of triples is \(2^3=8\).
Let \(a,b,c \in {0,1}\), then each number in this set, can be represented as \(x_i=a+2b+4c\). Then the suggested distance metric is:
\[d(x,y)=|a_x-a_y|+|b_x-b_y|+|c_x-c_y|\]Let \(x_1\), \(x_2\), \(x_3\) be defined as follows:
\[x=a_x+2b_x+4c_x \\ y=a_y+2b_y+4c_y \\ z=a_z+2b_z+4c_z\] \[\begin{align*} d(x,z) &= |a_x-a_z|+|b_x-b_z|+|c_x-c_z| \\ &=|a_x-a_y+a_y-a_z|+|b_x-b_y+b_y-b_z|+|c_x-c_y+c_y-c_z| \end{align*}\]Now we have the following inequalities:
\[|a_x-a_y+a_y-a_z| \leq |a_x-a_y|+|a_y-a_z| \\ |b_x-b_y+b_y-b_z| \leq |b_x-b_y|+|b_y-b_z| \\ |c_x-c_y+c_y-c_z| \leq |c_x-c_y|+|c_y-c_z|\]Summing up these inequalities, and noting that the LHS resolves to \(d(x,z)\), we get:
\[d(x,z) \leq |a_x-a_y|+|a_y-a_z| + |b_x-b_y|+|b_y-b_z| + |c_x-c_y|+|c_y-c_z| \\ \Rightarrow d(x,z) \leq (|a_x-a_y|+|b_x-b_y|+|c_x-c_y|) + (|a_y-a_z|+|b_y-b_z|+|c_y-c_z|) \\ \Rightarrow d(x,z) \leq d(x,y) + d(y,z)\]Thus, this proves the Triangle Inequality for the Hamming Distance as a metric.
\[\blacksquare\]We write the two following triangle inequalities. One involves \(x\), \(y\), \(z\). The other one involves \(w\), \(y\), \(z\).
\[d(x,y) \leq d(x,z) + d(z,y)\] \[\begin{equation} d(z,y) \leq d(z,w) + d(w,y) \label{eq:1-1-12-1} \end{equation}\]Adding \(d(x,z)\) to \(\eqref{eq:1-1-12-1}\), we get:
\[d(x,z) + d(z,y) \leq d(x,z) + d(z,w) + d(w,y)\]Thus, we have:
\[d(x,y) \leq d(x,z) + d(z,y) \leq d(x,z) + d(z,w) + d(w,y) \\ \Rightarrow d(x,y) \leq d(x,z) + d(z,w) + d(w,y) \\ \Rightarrow d(x,y) \leq d(x,z) + d(z,w) + d(y,w) \text{(by the Symmetry property of a Distance Metric)}\] \[\begin{equation} d(x,y) - d(z,w) \leq d(x,z) + d(w,y) \label{eq:1-1-12-abs-1} \end{equation}\]We write the two following triangle inequalities. One involves \(x\), \(z\), \(w\). The other one involves \(x\), \(y\), \(w\).
\[d(z,w) \leq d(z,x) + d(x,w)\] \[\begin{equation} d(x,w) \leq d(x,y) + d(y,w) \label{eq:1-1-12-2} \end{equation}\]Adding \(d(z,x)\) to \(\eqref{eq:1-1-12-2}\), we get:
\[d(z,x) + d(x,w) \leq d(z,x) + d(x,y) + d(y,w)\]Thus, we have:
\[d(z,w) \leq d(z,x) + d(x,w) \leq d(z,x) + d(x,y) + d(y,w) \\ \Rightarrow d(z,w) \leq d(z,x) + d(x,y) + d(y,w) \\ \Rightarrow d(z,w) \leq d(x,z) + d(x,y) + d(y,w) \text{(by the Symmetry property of a Distance Metric)}\] \[\begin{equation} d(z,w) - d(x,y) \leq d(z,x) + d(y,w) \label{eq:1-1-12-abs-2} \end{equation}\]Summarising \(\eqref{eq:1-1-12-abs-1}\) and \(\eqref{eq:1-1-12-abs-2}\), we get:
\[d(x,y) - d(z,w) \leq d(x,z) + d(y,w) \\ d(z,w) - d(x,y) \leq d(x,z) + d(y,w) \\ \Rightarrow \mathbf{ |d(x,y) - d(z,w)| \leq d(x,z) + d(y,w) }\] \[\blacksquare\]Proof:
We have to show that:
\[|d(x,z) - d(y,z)| \leq d(x,y)\]We write the following Triangle Inequality:
\[\begin{equation} d(x,z) \leq d(x,y) + d(y,z) \\ \Rightarrow d(x,z) - d(y,z) \leq d(x,y) \label{eq:1-1-13-abs-1} \end{equation}\]The other Triangle Inequality we write is:
\[\begin{equation} d(y,z) \leq d(y,x) + d(x,z) \\ \Rightarrow d(y,z) - d(x,z) \leq d(y,x) \\ \Rightarrow d(y,z) - d(x,z) \leq d(x,y) \text{(by the Symmetry property of a Distance Metric)} \label{eq:1-1-13-abs-2} \end{equation}\]Summarising the results of \(\eqref{eq:1-1-13-abs-1}\) and \(\eqref{eq:1-1-13-abs-2}\), we get:
\[d(x,z) - d(y,z) \leq d(x,y) \\ d(y,z) - d(x,z) \leq d(x,y) \\ \Rightarrow \mathbf{|d(x,z) - d(y,z)| \leq d(x,y)}\] \[\blacksquare\]For reference, the axioms (M1) to (M4) are as follows:
Proof for (M3):
The allowed assumptions are:
Set \(z=y\) in (A2), so that we get:
\[\require{cancel} \begin{equation} d(x,y) \leq d(y,x) + \cancel{d(y,y)} \text{ (by (A1))} \\ \Rightarrow d(x,y) \leq d(y,x) \label{eq:1-1-14-abs-1} \end{equation}\]From (A2), we get \(d(y,x)\) as:
\[\begin{equation} d(y,x) \leq d(z,y) + d(z,x) \label{eq:1-1-14-y-x} \end{equation}\]Set \(z=x\) in \(\eqref{eq:1-1-14-y-x}\) again, so that we get:
\[\begin{equation} d(y,x) \leq d(x,y) + \cancel{d(x,x)} \text{ (by (A1))} \\ \Rightarrow d(y,x) \leq d(x,y) \\ \Rightarrow d(x,y) \geq d(y,x) \label{eq:1-1-14-abs-2} \end{equation}\]Summarising the results of \(\eqref{eq:1-1-14-abs-1}\) and \(\eqref{eq:1-1-14-abs-2}\), we get:
\[d(x,y) \leq d(y,x) \\ d(x,y) \geq d(y,x)\]This implies that:
\[\begin{equation} d(x,y)=d(y,x) \label{eq:1-1-14-symmetry} \end{equation}\] \[\blacksquare\]Proof for (M4):
(M4) should immediately follow from \(\eqref{eq:1-1-14-symmetry}\), since:
\[d(x,y) \leq d(z,x) + d(z,y) \Rightarrow d(x,y) \leq d(x,z) + d(z,y)\] \[\blacksquare\]Proof:
We have to prove that: \(d(x,y) \geq 0\) follows from (M2) and (M4).
From the Triangle Inequality (M4), we have:
\[d(x,y) \leq d(x,z) + d(z,y)\]Set \(x=y\), then we get:
\[d(y,y) \leq d(y,z) + d(z,y) \\ \Rightarrow \underbrace{\cancel{d(y,y)}}_\text{by (M2)} \leq d(y,z) + \underbrace{d(y,z)}_\text{by (M3)} \\ \Rightarrow 2d(y,z) \geq 0 \\ \Rightarrow d(y,z) \geq 0\]This proves (M1).
\[\blacksquare\]