Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
I should have tried doing it myself before asking! Wasn't really challenging. Thanks anyways. –  Pedro Tamaroff Jul 10 '12 at 18:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.