3
$\begingroup$

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)$$

  • 0
    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.2012-07-10
  • 0
    @OldJohn Yes, I have graphed the corresponding "unit balls", I can probably prove it for $\Bbb R^2$, but that's not the point.2012-07-10
  • 0
    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.2012-07-10

1 Answers 1

3

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 $$

Similar inequalities will establish your first result:

$$ \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 $$

  • 0
    I should have tried doing it myself before asking! Wasn't really challenging. Thanks anyways.2012-07-10