# Relation between metrics

Let

\eqalign{ & d\left( {x,y} \right) = \mathop {\max }\limits_{1 \leqslant i \leqslant n} \left\{ {\left| {{x_i} - {y_i}} \right|} \right\} \cr & d'\left( {x,y} \right) = \sqrt {\sum\limits_{i = 1}^n {{{\left( {{x_i} - {y_i}} \right)}^2}} } \cr & d''\left( {x,y} \right) = \sum\limits_{i = 1}^n {\left| {{x_i} - {y_i}} \right|} \cr}

for any two points $x,y \in \Bbb R^n$.

How to prove the following holds?

\eqalign{ & d\left( {x,y} \right) \leqslant d'\left( {x,y} \right) \leqslant \sqrt n \cdot d\left( {x,y} \right) \cr & d\left( {x,y} \right) \leqslant d''\left( {x,y} \right) \leqslant n \cdot d\left( {x,y} \right) \cr}

I think I got the second one:

It is trivial that

$$\mathop {\max }\limits_{1 \leqslant i \leqslant n} \left\{ {\left| {{x_i} - {y_i}} \right|} \right\} < \sum\limits_{i = 1}^n {\left| {{x_i} - {y_i}} \right|}$$

Now let $k$ be the integer such that

$$d\left( {x,y} \right) = \left| {{x_k} - {y_k}} \right|$$

Then for each $1 \leq i \leq n$ we have that $$\left| {{x_i} - {y_i}} \right|\leq \left| {{x_k} - {y_k}} \right|$$

So summing from $1$ to $n$ one gets:

$$d''\left( {x,y} \right) \leqslant n \cdot d\left( {x,y} \right)$$

-
As a hint, I would look at what they say in 2 dimensions, and think about comparing lengths of sides of a rectangle with diagonals. I would tackle each inequality individually. –  Old John Jul 10 '12 at 17:44
@OldJohn Yes, I have graphed the corresponding "unit balls", I can probably prove it for $\Bbb R^2$, but that's not the point. –  Pedro Tamaroff Jul 10 '12 at 17:50
But I think that generalising to n dimensions doesn't change too much - just replaces 2 by $n$, or $\sqrt{2}$ with $\sqrt{n}$, from memory. –  Old John Jul 10 '12 at 18:00
For the second result, use: $$\sum_{i=1}^n |x_i-y_i|\le \sum_{i=1}^n \max_i |x_i-y_i|=n\max_i|x_i-y_i|$$ and $$\sum_{i=1}^n |x_i-y_i|\ge |x_j-y_j|, \ \text{for each}\ j$$
$$\sum_{i=1}^n |x_i-y_i|^2\le \sum_{i=1}^n \max_i |x_i-y_i|^2=n(\max_i |x_i-y_i|)^2$$ and $$\sum_{i=1}^n |x_i-y_i|^2\ge |x_j-y_j|^2, \ \text{for each}\ j$$