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.

How would I show that $$d_E = \sqrt{\sum_{i=1}^n(x_i-y_i)^2}$$ and $$d_\infty= \sum_{i=1}^n|x_i-y_i|$$ and $$\sup\{|x_1-y_1|,|x_2-y_2|,...,|x_n-y_n|\}$$ are topologically equivalent on $\mathbb{R}^n$? I can do it for $\mathbb{R}^2$, but I'm not sure how a generalization looks like.

share|improve this question
    
What does topologically equivalent mean, again? That they induce the same topology? –  Mike Miller Mar 31 at 7:52
    
(BTW - I think it should say $(x_i-y_i)^2$ in $d_E$) –  Mike Miller Mar 31 at 7:53
    
yes.. The question would ultimately boil down to find an open ball that can "contain" the other metric. –  Millardo Peacecraft Mar 31 at 7:54
    
Thanks, I just edited the question. –  Millardo Peacecraft Mar 31 at 7:55
1  
Your notation is a bit weird, $d_\infty$ is the $L^1$ distance. –  Najib Idrissi Mar 31 at 8:01

3 Answers 3

For your specific case, nik gives the simplest proof. This is in case you're interested in something more general.

I'm going to prove something stronger: all norms on $\Bbb R^n$ are equivalent. Pick a basis $\{e_1, \dots, e_n\}$ on $\Bbb R_n$, and write for convenience $a_1e_1 + \dots + a_ne_n = (a_1, \dots, a_n)$.

Let $||\cdot||_1$ be a given norm, and $||\cdot||_2$ be the norm given by $||v|| = d_E(v,0)$ in your notation. (This is the Euclidean metric.) Notice that topological equivalence between these two norms is the same as showing that there exist positive reals $a$ and $b$ with $$a||v||_2 \leq ||v||_1 \leq b||v||_2$$ (This equivalence follows from the fact that $\Bbb R^n$ is a vector space; I'll leave that bit to you.)

Now immediately $$||(a_1, \dots , a_n)||_1 \leq \sum_{i=1}^n |a_i| \cdot ||e_i||_1 \leq \left(\sum_{i=1}^n |a_i|\right) \max(||e_1||_1, \dots ||e_n||_1)$$ Let $M=\max(||e_1||_1, \dots ||e_n||_1)$. Then $||v||_1 \leq M\sqrt{n}||v||_2$ by the Cauchy-Schwarz inequality, as mentioned in nik's answer.

To prove the reverse direction, we can't make estimations like before; we have to invoke a teeny bit of topology.

What we just proved is, in addition, that the map $f:\Bbb R^n\rightarrow \Bbb R: v \mapsto ||v||_1$ is continuous (where I mean $\Bbb R^n$ with the topology given by $||\cdot||_2$). Now note that the unit sphere in $(\Bbb R^n, ||\cdot||_2)$ is the sphere, a compact topological space. Now, any continuous function from a compact space to the reals takes on a minimum value (see, for instance, here for a proof.) Let $m$ be the minimum value of the map $v \mapsto ||v||_1$ defined on the unit sphere. So (for $v$ in the unit sphere) $||v||_1 \geq m$, and so for any vector in $\Bbb R^n$, $||v||_1 \geq m||v||_2$. So $$m||v||_2 \leq ||v||_1 \leq M\sqrt{n} ||v||_2$$ So these two norms are equivalent. Since $||\cdot||_1$ was arbitrary, any two norms on $\Bbb R^n$ are equivalent.

share|improve this answer

Use CS inequality we have: $d_E \leq d_\infty \leq n^{0.5}\cdot d_E$. this shows the two metrics are topologically equivalent.

share|improve this answer

Let $D$ be another metric defined by $D(x,y) = \max_i |x_i - y_i|$. Then the following inequalities hold: $$\begin{align} d_E(x,y) & \leq \sqrt{\sum_{i = 1}^n D(x,y)^n} = \sqrt{n} D(x,y) \\ D(x,y) & \overset{(1)}{\leq} d_\infty(x,y) \\ d_\infty(x,y) & \overset{(2)}{\leq} \sqrt{n} d_E(x,y) \end{align}$$

(1) is because the specific $D(x,y) = |x_{i_0} - y_{i_0}|$ appears in the sum that defines $d_\infty$, and all the other terms are nonnegative. (2) is the Cauchy-Schwarz inequality.

From these you can conclude that $d_E \leq \sqrt{n} d_\infty \leq n d_E$. So when you have an open ball for $d_E$, it's included in the open ball of radius $r \sqrt{n}$ for $d_\infty$, and reciprocally.


Only one more inequality is necessary to prove that $D$ is equivalent to the other two: $$d_\infty(x,y) \leq \sum_{i=1}^n D(x,y) = n D(x,y)$$ Because then by inequality $(1)$ it's equivalent to $d_\infty$, which is equivalent to $d_E$.

share|improve this answer
    
I've edited the question. Mind if I pick your brain some more? –  Millardo Peacecraft Mar 31 at 8:43
    
@MillardoPeacecraft: I edited my answer. –  Najib Idrissi Mar 31 at 8:58

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.