Processing math: 7%

Total Internal Reflection

Technology and Art



Code

Cobol REKT
Tape/Z
Plenoxels
Transformer
Basis-Processing
Cataract
COMRADE
Duck-Angular
Exo
IRIS
MuchHeap
Snail-MapReduce
Underline
Lambda-Queuer
jQuery-Jenkins Radiator

Contact

Github
Twitter
LinkedIn

Site Feed

Functional Analysis Exercises 2 : Distance Metrics

Avishek Sen Gupta on 28 September 2021

This post lists solutions to many of the exercises in the Distance Metrics section 1.2 of Erwin Kreyszig’s Introductory Functional Analysis with Applications. This is a work in progress, and proofs may be refined over time.

For reference, the axioms (M1) to (M4) for a distance metric are as follows:

1.2.1. Show that in 1.2-1 we can obtain another metric by replacing 12i with μi>0 such that μi converges.

Proof: The space referred to is the space of all bounded and unbounded sequences.

The candidate metric is defined as:

d(x,y)=i=1μi|xiyi|1+|xiyi|

(M1) d(x,y) is bounded, non-negative, and real.

We know that i=1μi converges, thus if we prove λiμi<mui, we will have proved that i=1λiμi converges, and is thus real, bounded.

Indeed, if we examine d(x,y), we can make the following observation:

d(x,y)=i=1μi|xiyi|1+|xiyi|0λ<1

Thus, d(x,y) is bounded and real. d(x,y) is also nonnegative because 0λ<1 and μi>0.

(M2) d(x,y)=0 if and only if x=y.

This is evident since:

d(x,x)=i=1μi|xixi|1+|xixi|=0

(M3) d(x,y)=d(y,x)

This is easily seen since the modulus sign guarantees that:|xiyi|=|yixi|, and thus d(x,y)=d(y,x).

(M4) d(x,y)d(x,z)+d(z,y)

For convenience of notation, let us denote use the following notation:

A=|xiyi|B=|yizi|C=|ziyi|

We’d like to prove that:

\require{cancel} \frac{A}{1+A} \leq \frac{B}{1+B} + \frac{C}{1+C} \\ = \frac{B+C+2BC}{(1+B)(1+C)} \\ \Rightarrow A(1+B)(1+C) \leq (B+C+2BC)(1+A) \\ \Rightarrow A+\cancel{CA}+\cancel{AB}+\cancel{ABC} \leq B+C+2BC+\cancel{AB}+\cancel{CA}+\cancel{2}ABC \\ \Rightarrow A \leq B+C+2BC+ABC \\ \Rightarrow |x_i-y_i| \leq |x_i-z_i|+|z_i-y_i|+2BC+ABC

Thus, we need to prove that:

|x_i-y_i| \leq |x_i-z_i|+|z_i-y_i|+2BC+ABC

where A,B,C \geq 0.

We already know from the Triangle Inequality that:

\begin{align*} |x_i-y_i| &= |x_i-z_i+z_i-y_i| \\ |x_i-y_i| &\leq |x_i-z_i|+|z_i-y_i| \\ \Rightarrow |x_i-y_i| &\leq |x_i-z_i|+|z_i-y_i|+2BC+ABC \end{align*}

Thus, we have:

\frac{A}{1+A} \leq \frac{B}{1+B} + \frac{C}{1+C}

Multiplying throughout by \mu_i, and summing over i, we have:

\displaystyle\sum_{i=1}^\infty\mu_i\frac{A}{1+A} \leq \sum_{i=1}^\infty\mu_i\frac{B}{1+B} + \sum_{i=1}^\infty\mu_i\frac{C}{1+C} \\ \Rightarrow d(x,y) \leq d(x,z) + d(z,y)

Thus, d(x,y) is a metric.

\blacksquare

1.2.2. Using (6), show that the geometric mean of two positive numbers does not exceed the arithmetic mean.

Proof: From the identity involving conjugate exponents, we know that:

\alpha \beta \leq \frac{\alpha^p}{p} + \frac{\beta^q}{q} \\ \Rightarrow 2\alpha \beta \leq \frac{\alpha^p}{p} + \frac{\beta^q}{q} + \alpha \beta

Set p=2, then we get q=2, so that we get:

2\alpha \beta \leq \frac{\alpha^2}{2} + \frac{\beta^2}{2} + \alpha \beta \\ \Rightarrow 4\alpha \beta \leq \alpha^2 + \beta^2 + 2\alpha \beta \\ \Rightarrow \alpha \beta \leq {\left(\frac{\alpha + \beta}{2}\right)}^2 \\ \Rightarrow \sqrt{\alpha \beta} \leq \frac{\alpha + \beta}{2}

This proves that the Geometric Mean of two numbers cannot exceed their Arithmetic Mean.

\blacksquare

1.2.3. Show that the Cauchy-Schwarz inequality (11) implies

{(|\xi_1| + \cdots + |\xi_n|)}^2 \leq n ({|\xi_1|}^2 + \cdots + {|\xi_n|}^2).

Proof: The Cauchy-Schwarz Inequality is :

\displaystyle\sum_{i=1}^n |x_i y_i| \leq {\left( \displaystyle\sum_{i=1}^n {|x_i|}^2 \right)}^\frac{1}{2} \bullet {\left( \displaystyle\sum_{i=1}^n {|y_i|}^2 \right)}^\frac{1}{2}

Set y_i=1, so that we get:

\displaystyle\sum_{i=1}^n |x_i| \leq {\left( \displaystyle\sum_{i=1}^n {|x_i|}^2 \right)}^\frac{1}{2} \\ \Rightarrow {\left(\displaystyle\sum_{i=1}^n |x_i|\right)}^2 \leq \displaystyle\sum_{i=1}^n {|x_i|}^2 \\ \Rightarrow {(|x_1| + \cdots + |x_n|)}^2 \leq n ({|x_1|}^2 + \cdots + {|x_n|}^2) \blacksquare

1.2.4. (Space \ell^p) Find a sequence which converges to 0, but is not in any space \ell^p, where 1\leq p<+\infty.

Answer:

(x_k)=\frac{1}{n} is the key to creating sequences which converge, but whose corresponding series are not summable. The issue is that you cannot just use (x_k)=\frac{1}{n} because for p>1, we have S_k=\displaystyle\sum {\left(\frac{1}{n}\right)}^p will converge, and obviously we do not want that. The trick is to introduce a numerator which will clearly show divergence of the series (using the Ratio Test for example), but then write the series as the numerator number of \frac{1}{n} terms.

Let us take a simple example: consider the sequence (x_k)=\frac{n+1}{n}. The series is then written as:

x_k=\{2, \frac{3}{2}, \frac{4}{3}, \frac{5}{4}, \frac{6}{5}, \cdots \}

But the above could also be written like so:

y_k=\{\underbrace{\frac{1}{1}, \frac{1}{1}}_{\text{Two }1}, \underbrace{\frac{1}{2}, \frac{1}{2}, \frac{1}{2}}_{\text{Three }\frac{1}{2}}, \underbrace{\frac{1}{3}, \frac{1}{3}, \frac{1}{3}, \frac{1}{3}}_{\text{Four }\frac{1}{3}}, \underbrace{\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}}_{\text{Five }\frac{1}{4}}, \cdots \}

This shows that the limit of this sequence is zero, even though the “parent” series is clearly not summable. Breaking up the terms of a divergent series to create a new sequence which has a finite limit is the key idea here.

However, in the above example, the choice of numerator n+1 does not pass the Ratio Test for divergence, because \frac{x_{k+1}}{x_k}=\frac{n^2+2n}{n^2+2n+1}<1. We will thus need a bigger numerator. An additive factor will not do, because for all K>0, we will get \frac{x_{k+1}}{x_k}=\frac{2n}{n+1}>1, for n>1, which is always going to be the case for our series..

An exponential factor like 2^n will work as the numberator, because then we have \frac{x_{k+1}}{x_k}=\frac{n^2+2n}{n^2+2n+1}<1 Note: (n+1) is not the only choice for a numerator. Anything that is clearly bigger than the denominator should do. 2^n, for example is also a valid choice. The choice will affect how many \frac{1}{n} terms will appear from each term in the original series.

z_k=\{\underbrace{\frac{1}{1}, \frac{1}{1}}_{\text{Two }1}, \underbrace{\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}}_{\text{Four }\frac{1}{2}}, \underbrace{\frac{1}{3}, \frac{1}{3}, \frac{1}{3}, \frac{1}{3}, \frac{1}{3}, \frac{1}{3}, \frac{1}{3}, \frac{1}{3}}_{\text{Eight }\frac{1}{3}}, \cdots \}

z_k is an example of a sequence which converges to zero, but whose series diverges for all p \geq 1.


1.2.5. Find a sequence x which is in \ell^p with p>1 but \require{cancel} x\cancel{\in}\ell^1.

Answer:

(x_i)=\frac{1}{i} converges to 0. \displaystyle\sum_{i=1}^\infty{(\frac{1}{i})}^p diverges to \infty for p\leq 1, and thus violates the condition for a sequence in \ell^p spaces, i.e. \displaystyle\sum_{i=1}^\infty{\vert\xi_i\vert}^p<\infty for p \leq 1.

1.2.6. (Diameter, bounded set) The diameter \delta(A) of a nonempty set A in a metric space (X, d) is defined to be \delta(A) = \sup d(x,y). A is said to be bounded if \delta(A)<\infty. Show that A\subset B implies \delta(A)\leq \delta(B).

Proof:

By the definition of set membership, we can say that if x,y \in A, and A\subset B, then x,y \in B.

Consider the set of all distances in A and B, like so:

\Delta_A={d(x,y): x,y \in A} \\ \Delta_B={d(u,v): u,v \in B}

Since x,y\in A \Rightarrow x,y \in B, all d(x,y):x,y \in A must exist in \Delta_B. Thus, we have:

\Delta_A \subset \Delta_B

Thus, \delta(A)=\sup \Delta_A exists in \Delta_B, i.e.,

\begin{equation} \delta(A) \in \Delta_B \label{eq:diameter-A-in-DeltaB} \end{equation}

By the definition of the diameter of a bounded set, we have:

\begin{equation} \delta_B=\sup \Delta_B \label{eq:diameter-B-sup-DeltaB} \end{equation}

Putting \eqref{eq:diameter-A-in-DeltaB} and \eqref{eq:diameter-B-sup-DeltaB} together, implies that:

\delta(A) \leq \delta(B)

Verbal Reasoning: \delta(A) is a member of B, while \delta(B) is the least upper bound of B, thus \delta(A) has to be less than or, at the most, equal to this least upper bound \delta(B).

\blacksquare

1.2.7. Show that \delta(A)=0 (cf. Prob. 6) if and only if A consists of a single point.

Proof:

We prove the “if” side of the claim first.

Assume A=\{x\}.
Then the set \Delta_A={d(x,x)}.
Therefore \delta(A)=\sup \Delta_A=d(x,x).

By the definition of a distance metric, d(x,x)=0.

Thus, we get:

\delta(A)=0 \blacksquare

For the “only if” side of implication, Let \delta(A)=\sup \Delta_A=0.

By the definition of a distance metric, d(x,y)\geq 0.
Thus, all other elements of \Delta_A have to be zero. This implies there is only one element in \Delta_A={0}.
Therefore, distances between all points x \in A must be zero.

By the definition of a distance metric, d(x,y)=0 if x=y.

Therefore, all points must be equal to each other, i.e., there is only one point in A.

\blacksquare

1.2.8. (Distance between sets) The distance D(A,B) between two nonempty subsets A and B of a metric space (X, d) is defined to be:

D(A,B) = \inf d(a, b).

Show that D does not define a metric on the power set of X. (For this reason we use another symbol, D, but one that still reminds us of d.)

Proof:

Consider A={3,4}, and B={4,5}.
Then, we have:

P(A)=\{\emptyset,\{3\}, \{4\}\, \{3,4\}\} \\ P(B)=\{\emptyset,\{4\}, \{5\}\, \{4,5\}\}

Then D(P(A),P(B))=\inf d(a,b)=0

However, P(A) \neq P(B).

Thus, property (M1) of the distance metric is violated, and D is not a valid distance metric on the power set of X.

\blacksquare

1.2.9. If An A \cap B \neq \emptyset, show that D(A,B) = 0 in Prob. 8. What about the converse?

Proof:

Let \Delta_{XY}=\{d(x,y):x \in A\, y \in B\}

Let A \cap B \neq \emptyset, then there exists at least one element p\in A,B.

Then, d(p,p) \in \Delta_{XY} and d(p,p)=0.

Since a distance metric must be nonnegative, D(A,B)=\inf\Delta_{XY}=0

\blacksquare

The converse is not true. To see why this is not true, remember that the infimum/supremum of a set does not have to belong to that set. Therefore, two sets can have the same infimum/supremum while still having their intersection be the null set.

Thus, consider the set formed by the sequence \{\frac{1}{2^n}\}. Then X=\{\frac{1}{2^n}\} The infimum (and the limit point) of X is 0.

Now consider a second set Y={0}.

Then, let \Delta_{XY} is the set of all distances between X and Y, defined as:

\begin{align*} \Delta_{XY}&=\{d(x,y):x \in A, y \in B\} \\ &=\Bigl\{\frac{1}{2} - 0, \frac{1}{2^2} - 0, \frac{1}{2^3} - 0, \frac{1}{2^4} - 0, ...\Bigr\} \\ &=\Bigl\{\frac{1}{2}, \frac{1}{2^2}, \frac{1}{2^3}, \frac{1}{2^4}, ...\Bigr\} \end{align*}

We know then that:

\lim\limits_{n\rightarrow\infty}\frac{1}{2^n}=0 \\ \Rightarrow \lim\limits_{n\rightarrow\infty}\Delta_{XY}=0 \\

In this case, \Delta_{XY} has no Least Upper Bound. Then, D{X,Y} is:

D(X,Y)=\inf\Delta_{XY}=0 \\

This is a case where D(X,y)=0, even though X\cap Y=\emptyset.
Thus, we see that:

\require{cancel} D(X,Y)=0 \cancel\Rightarrow X\cap Y \neq \emptyset \blacksquare

1.2.10. The distance D(x,B) from a point x to a non-empty subset B of (X,d) is defined to be

D(x,B)= \inf d(x, b)

in agreement with Prob. 8. Show that for any x,y\in X,

|D(x,B) - D(y,B)| \leq d(x, y).

Proof:

We have, from the Triangle Inequality,

\begin{equation} d(x,b) \leq d(x,y) + d(y,b) \\ \Rightarrow d(x,b)-d(y,b) \leq d(x,y) \label{eq:1-2-10-1} \end{equation}

We also have:

\begin{equation} d(y,b) \leq d(y,x) + d(x,b) \\ \Rightarrow d(y,b) \leq d(x,y) + d(x,b) \\ \Rightarrow d(y,b)-d(x,b) \leq d(x,y) \label{eq:1-2-10-2} \end{equation}

From the results of \eqref{eq:1-2-10-1} and \eqref{eq:1-2-10-2}, we get:

|d(x,b)-d(y,b)| \leq d(x,y)

This is true for all d(x,b) and d(y,b), including their infimums, i.e.:

|\inf d(x,b)-\inf d(y,b)| \leq d(x,y) \\ \Rightarrow |D(x,B)-D(y,B)| \leq d(x,y) \blacksquare

1.2.11. If (X,d) is any metric space, show that another metric on X is defined by

\bar{d}(x,y)=\frac{d(x,y)}{1+d(x,y)}

and X is bounded in the metric \bar{d}.

Proof:

The candidate metric is defined as:

\bar{d}(x,y)=\frac{d(x,y)}{1+d(x,y)}

(M1) 0 \leq d(x,y)<\infty, d(x,y)\in \mathbb{R}

d(x,y) is already a metric. Thus, d(x,y) is nonnegative and bounded. Then \bar{d}(x,y) is also nonegative and bounded, by its definition.

(M2) d(x,y)=0 if and only if x=y

This is evident if we set d(x,y)=0 in the definition of \bar{d}(x,y).

(M3) d(x,y)=d(y,x)

Since d(x,y) is symmetric, substituting d(y,x) in the definition of \bar{d}(x,y) shows that it is symmetric also.

(M4) d(x,y) \leq d(x,z) + d(z,y)

For convenience of notation, let us denote use the following notation:

A=d(x,y) \\ B=d(x,z) \\ C=d(z,y)

We’d like to prove that:

\require{cancel} \frac{A}{1+A} \leq \frac{B}{1+B} + \frac{C}{1+C} \\ = \frac{B+C+2BC}{(1+B)(1+C)} \\ \Rightarrow A(1+B)(1+C) \leq (B+C+2BC)(1+A) \\ \Rightarrow A+\cancel{CA}+\cancel{AB}+\cancel{ABC} \leq B+C+2BC+\cancel{AB}+\cancel{CA}+\cancel{2}ABC \\ \Rightarrow A \leq B+C+2BC+ABC \\ \Rightarrow d(x,y) \leq d(x,z)+d(z,y)+2BC+ABC

Thus, we need to prove that:

d(x,y) \leq d(x,z)+d(z,y)+2BC+ABC

where A,B,C \geq 0.

We already know from the Triangle Inequality that:

\begin{align*} d(x,y) &\leq d(x,z)+d(z,y) \\ \Rightarrow d(x,y) &\leq d(x,z)+d(z,y)+2BC+ABC \end{align*}

Thus, we have:

\frac{A}{1+A} \leq \frac{B}{1+B} + \frac{C}{1+C}

Multiplying throughout by \mu_i, and summing over i, we have:

\displaystyle\sum_{i=1}^\infty\mu_i\frac{A}{1+A} \leq \sum_{i=1}^\infty\mu_i\frac{B}{1+B} + \sum_{i=1}^\infty\mu_i\frac{C}{1+C} \\ \Rightarrow \bar{d}(x,y) \leq \bar{d}(x,z) + \bar{d}(z,y)

Thus d(x,y) is a metric.

\blacksquare

1.2.12. Show that the union of two bounded sets A and B in a metric space is a bounded set. (Definition in Prob. 6.)

Let us define three sets of metrics:

\Delta_A=\{d(x,y):x,y \in A\} \\ \Delta_B=\{d(x,y):x,y \in B\} \\ \Delta_{AB}=\{d(x,y):x \in A,y \in B\} \\

Verbally,

Then the set of all distances between points in C=A \cup B is \Delta_C=\Delta_A \cap \Delta_B \cap \Delta_{AB}.

By definition, diameter of C is:

\delta(A \cup B) = \inf \Delta_C

From the axioms of the metric d, we note that \forall d(x,y) \in \Delta_A, \Delta_B, \Delta_{AB}, d(x,y)<\infty.

Then, we can deduce the following:

\delta(A \cup B) = \inf \Delta_C = \inf \{d(x,y): d(x,y) \in \Delta_A, \Delta_B, \Delta_{AB}\} \\ \Rightarrow \delta(A \cup B) < \infty

Hence, the union of two bounded sets is bounded.

\blacksquare

1.2.13. (Product of metric spaces) The Cartesian product X = X_1 \times X_2 of two metric spaces (X_1,d_1) and (X_2,d_2) can be made into a metric space (X,d) in many ways. For instance, show that a metric d is defined by

\bar{d}(x,y)=d_1(x_1,y_1) + d_2(x_2,y_2)

where x=(x_1,x_2), y=(y_1,y_2).

Proof:

The candidate distance metric is:

\bar{d}(x,y)=d_1(x_1,y_1) + d_2(x_2,y_2)

where d_1 and d_2 are already valid distance metrics.

(M1) 0 \leq \bar{d}(x,y)<\infty, \bar{d}(x,y)\in \mathbb{R}

Because d_1 and d_2 are already valid metrics. Thus 0<d_1(x,y)<\infty and 0<d_2(x,y)<\infty.

\therefore 0<\bar{d}(x,y)<\infty

Thus, \bar{d}(x,y) is nonegative and bounded, by its definition.

(M2) \bar{d}(x,y)=0 if and only if x=y

This is evident if we set x=y, then we have d_1(x,x)=d_2(x,x)=0 and thus \bar{d}(x,y)=0.

(M3) \bar{d}(x,y)=\bar{d}(y,x)

Since d_1(x,y) and d_2(x,y) are symmetric, substituting d_1(y,x) and d_2(y,x) in the definition of \bar{d}(x,y) shows that it is symmetric also.

(M4) \bar{d}(x,y) \leq \bar{d}(x,z) + \bar{d}(z,y)

d_1(x_1,y_1) \leq d_1(x_1,z_1) + d_1(z_1, y_1) \\ d_2(x_2,y_2) \leq d_2(x_2,z_2) + d_2(z_2, y_2) \\

Summing the above two identities, we see:

d_1(x_1,y_1) + d_2(x_2,y_2) \leq d_1(x_1,z_1) + d_1(z_1, y_1) + d_2(x_2,z_2) + d_2(z_2, y_2) \\ \Rightarrow \underbrace{d_1(x_1,y_1) + d_2(x_2,y_2)}_{\bar{d}(x_2,z_2)} \leq \underbrace{d_1(x_1,z_1) + d_2(x_2,z_2)}_{\bar{d}(x,z)} + \underbrace{d_1(z_1, y_1) + d_2(z_2, y_2)}_{\bar{d}(z,y)} \\ \Rightarrow \bar{d}(x,y) \leq d_1(x,z) + d_2(z,y)

Hence, \bar{d} is a valid distance metric.

\blacksquare

1.2.14. Show that another metric on X in Prob. 13 is defined by

Proof:

The candidate distance metric is:

\bar{d}(x,y)=\sqrt{ {d_1(x_1,y_1)}^2 + {d_2(x_2,y_2)}^2}

where d_1 and d_2 are already valid distance metrics.

(M1) 0 \leq \bar{d}(x,y)<\infty, \bar{d}(x,y)\in \mathbb{R}

Because d_1 and d_2 are already valid metrics. Thus 0<d_1(x,y)<\infty and 0<d_2(x,y)<\infty.

\therefore 0<\bar{d}(x,y)<\infty

Thus, \bar{d}(x,y) is nonegative and bounded, by its definition.

(M2) \bar{d}(x,y)=0 if and only if x=y

This is evident if we set x=y, then we have d_1(x,x)=d_2(x,x)=0 and thus \bar{d}(x,y)=0.

(M3) \bar{d}(x,y)=\bar{d}(y,x)

Since d_1(x,y) and d_2(x,y) are symmetric, substituting d_1(y,x) and d_2(y,x) in the definition of \bar{d}(x,y) shows that it is symmetric also.

(M4) \bar{d}(x,y) \leq \bar{d}(x,z) + \bar{d}(z,y)

We have:

\begin{equation} {\bar{d}(x,z)}^2={d_1(x_1,z_1)}^2 + {d_2(x_2,z_2)}^2 \label{eq:rhs-1} \end{equation} \begin{equation} {\bar{d}(z,y)}^2={d_1(z_1,y_1)}^2 + {d_2(z_2,y_2)}^2 \label{eq:rhs-2} \end{equation}

We also have the following two identities:

d_1(x_1,y_1) \leq d_1(x_1,z_1) + d_1(z_1,y_1) \\ {d_1(x_1,y_1)}^2 \leq {d_1(x_1,z_1)}^2 + {d_1(z_1,y_1)}^2 + 2d_1(x_1,z_1) d_1(z_1,y_1) \\ d_2(x_2,y_2) \leq d_2(x_2,z_2) + d_2(z_2,y_2) \\ {d_2(x_2,y_2)}^2 \leq {d_2(x_2,z_2)}^2 + {d_2(z_2,y_2)}^2 + 2d_2(x_2,z_2) d_2(z_2,y_2) \\

If we add \eqref{eq:rhs-1} and \eqref{eq:rhs-2}, we get:

{\bar{d}(x,z)}^2 + {\bar{d}(z,y)}^2 = {d_1(x_1,z_1)}^2 + {d_2(x_2,z_2)}^2 + {d_1(z_1,y_1)}^2 + {d_2(z_2,y_2)}^2 + 2d_1(x_1,z_1) d_1(z_1,y_1) + 2d_2(x_2,z_2) d_2(z_2,y_2) \\ {\bar{d}(x,z)}^2 + {\bar{d}(z,y)}^2 = \underbrace{ {d_1(x_1,z_1)}^2 + {d_1(z_1,y_1)}^2}_{\geq {d_1(x_1,y_1)}^2} + \underbrace{ {d_2(x_2,z_2)}^2 + {d_2(z_2,y_2)}^2}_{\geq {d_2(x_2,y_2)}^2} + 2d_1(x_1,z_1) d_1(z_1,y_1) + 2d_2(x_2,z_2) d_2(z_2,y_2) \\ {d_1(x_1,y_1)}^2 + {d_2(x_2,y_2)}^2 \leq {\bar{d}(x,z)}^2 + {\bar{d}(z,y)}^2 + 2d_1(x_1,z_1) d_1(z_1,y_1) + 2d_2(x_2,z_2) d_2(z_2,y_2) \\ {\bar{d}(x,y)}^2 \leq {\bar{d}(x,z)}^2 + {\bar{d}(z,y)}^2 + 2d_1(x_1,z_1) d_1(z_1,y_1) + 2d_2(x_2,z_2) d_2(z_2,y_2)

The last two terms on the right can be written in an indexed form as below:

\begin{equation} {\bar{d}(x,y)}^2 \leq {\bar{d}(x,z)}^2 + {\bar{d}(z,y)}^2 + 2 \displaystyle\sum_{i=1}^2 d_i(x_i,z_i) d_i(z_i,y_i) \label{eq:indexed-form} \end{equation}

Applying the Cauchy-Scharz Inequality to the last term on the RHS, we get:

\begin{align*} \sum_{i=1}^2 d_i(x_i,z_i) d_i(z_i,y_i) &\leq {\left(\sum_{i=1}^2 {d_i(x_i,z_i)}^2\right)}^\frac{1}{2} {\left(\sum_{i=1}^2 {d_i(z_i,y_i)}^2\right)}^\frac{1}{2} \\ &= {\left({d_1(x_1, z_1)}^2 + {d_2(x_2, z_2)}^2\right)}^\frac{1}{2} {\left({d_1(z_1, y_1)}^2 + {d_2(z_2, y_2)}^2\right)}^\frac{1}{2} \\ &= \bar{d}(x,z) \bullet \bar{d}(z,y) \end{align*}

Then, substituting the result above back into \eqref{eq:indexed-form}, we get:

{\bar{d}(x,y)}^2 \leq {\bar{d}(x,z)}^2 + {\bar{d}(z,y)}^2 + 2 \bar{d}(x,z) \bar{d}(z,y) \\ \Rightarrow {\bar{d}(x,y)}^2 \leq {(\bar{d}(x,z) + \bar{d}(z,y))}^2 \\ \Rightarrow \bar{d}(x,y) \leq \bar{d}(x,z) + \bar{d}(z,y)

Thus, \bar{d} is a valid distance metric.

\blacksquare

1.2.15. Show that a third metric on X in Prob. 13 is defined by

\bar{d}(x,y)=\max[d_1(x_1,y_1), d_2(x_2,y_2)]

Proof:

The candidate distance metric is:

\bar{d}(x,y)=\max[d_1(x_1,y_1), d_2(x_2,y_2)]

where d_1 and d_2 are already valid distance metrics.

(M1) 0 \leq \bar{d}(x,y)<\infty, \bar{d}(x,y)\in \mathbb{R}

Because d_1 and d_2 are already valid metrics. Thus 0<d_1(x,y)<\infty and 0<d_2(x,y)<\infty.

\therefore 0<\bar{d}(x,y)<\infty

Thus, \bar{d}(x,y) is nonegative and bounded, by its definition.

(M2) \bar{d}(x,y)=0 if and only if x=y

This is evident if we set x=y, then we have d_1(x,x)=d_2(x,x)=0 and thus \bar{d}(x,y)=0.

(M3) \bar{d}(x,y)=\bar{d}(y,x)

Since d_1(x,y) and d_2(x,y) are symmetric, substituting d_1(y,x) and d_2(y,x) in the definition of \bar{d}(x,y) shows that it is symmetric also.

(M4) \bar{d}(x,y) \leq \bar{d}(x,z) + \bar{d}(z,y)

We have:

\bar{d}(x,y)=\max[d_1(x_1,y_1), d_2(x_2,y_2)] \\ \bar{d}(x,z)=\max[d_1(x_1,z_1), d_2(x_2,z_2)] \\ \bar{d}(z,y)=\max[d_1(z_1,y_1), d_2(z_2,y_2)]

Adding the above gives us:

\begin{equation} \bar{d}(x,y)=\max[d_1(x_1,y_1), d_2(x_2,y_2)] \\ \bar{d}(x,y) \leq \max[d_1(x_1,z_1)+d_1(z_1,y_1), d_2(x_2,z_2)+d_2(z_2,y_2)] \label{eq:1-2-15-max} \end{equation}

We’d like to relate the above to the candidate metric. To do that, we need to find some way to group d_1(x_1,z_1) and d_2(z_2,y_2) together; currently they are stuck in separate “maximum” expressions.

To do this, let us observe that:

\begin{equation} a \leq \max(a,b) \\ c \leq \max(c,d) \\ \Rightarrow a+c \leq \max(a,b) + \max(c,d) \label{eq:1-2-15-a-plus-c} \end{equation}

Similarly:

\begin{equation} b+d \leq \max(a,b) + \max(c,d) \label{eq:1-2-15-b-plus-d} \end{equation}

Thus, if we take the maximum of the left hand side of \eqref{eq:1-2-15-a-plus-c} and \eqref{eq:1-2-15-b-plus-d}, we get:

\max(a+c,b+d) \leq \max(a,b) + \max(c,d)

Substituting the above results back into \eqref{eq:1-2-15-max}, we get:

\begin{equation} \bar{d}(x,y) \leq \max[d_1(x_1,z_1)+d_1(z_1,y_1), d_2(x_2,z_2)+d_2(z_2,y_2)] \\ \leq \max(d_1(x_1,z_1), d_2(x_2,z_2)) + \max(d_1(z_1,y_1), d_2(z_2,y_2)) \label{eq:1-2-15-penultimate} \end{equation}

We note that:

\bar{d}(x,z) + \bar{d}(z,y) = \max[d_1(x_1,z_1), d_2(x_2,z_2)] + \max[d_1(z_1,y_1), d_2(z_2,y_2)]

Substituting the above equality into \eqref{eq:1-2-15-penultimate}, we directly get:

\bar{d}(x,y) \leq \bar{d}(x,z) + \bar{d}(z,y)

Thus, \bar{d} is a valid distance metric.

\blacksquare
tags: Mathematics - Proof - Functional Analysis - Pure Mathematics - Kreyszig