$$d_\infty (x,y) = \max{|x_i - y_i| | i=1,2,...,n}$$ $$d_1 (x,y)= \sum_{i=1}^n |x_i - y_i|$$

$$d_\infty : \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$$ $$d_1: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$$

$$x,y\in \mathbb{R}^n$$

I would like to prove that $d_1(x,y) \leq n d_\infty (x,y)$.


Since $$d_1(x,y) = \sum_{i=1}^n |x_i - y_i|=|x_1 - y_1|+ \dots + |x_n - y_n|\leq \max|x_1 - y_1| +\dots + \max|x_i - y_i |=$$ $$= n\max |x_i - y_i |=nd_{\infty}(x,y).$$

  • 2
    $\begingroup$ This is certainly false, let $(x_i)=(1)$ and $(y_i)=(0)$ the desired inequality leads to $n\leqslant \sqrt{n}$. The equality is true if you replace $d_{\infty}$ by $d_2$. $\endgroup$ – C. Falcon Oct 24 '16 at 22:04
  • $\begingroup$ If you change $d_1$ for the euclidean metric then is true, are you sure you copied the problem correctly? You need to change, as it is by now, $\sqrt n$ by $n$. $\endgroup$ – Masacroso Oct 24 '16 at 22:07
  • $\begingroup$ @Masacroso I believe the professor meant $n$ but incorrectly wrote $\sqrt{n}$. $\endgroup$ – ozarka Oct 24 '16 at 22:16
  • 1
    $\begingroup$ If the problem state that you need to use the Cauchy-Schwarz inequality then the real problem is $d_1(x,y)\le \sqrt n d_2(x,y)$ as @C.Falcon commented. For this case you need this inequality to prove it. $\endgroup$ – Masacroso Oct 24 '16 at 22:18
  • $\begingroup$ Is there a way of proving this without Cauchy-Schwarz inequality? Intuitively I don't see how the sum of non-negative terms would be less than $n \max|x_i - y_i|$ for $i=1,2,...,n$ $\endgroup$ – ozarka Oct 24 '16 at 22:21

As C. Falcon says, you should change $d_{\infty}$ by $d_{2}$. By Cauchy-Schwarz we have $$(\sum_{i=1}^n (|x_i - y_i|\cdot 1))^2\le (\sum_{i=1}^n |x_i - y_i|^2)(1^2+\cdots 1^2).$$

Then $$\sum_{i=1}^n |x_i - y_i|\le \sqrt{n}(\sqrt{\sum_{i=1}^n |x_i - y_i|^2}).$$

Hence $d_{1}(x,y)\le \sqrt{n}d_{2}(x,y)$.

  • $\begingroup$ If I am asked to prove $d_1(x,y) \leq n d_\infty (x,y)$, what would be the approach without using Cauchy-Schwarz. $\endgroup$ – ozarka Oct 24 '16 at 22:23
  • 2
    $\begingroup$ @ozarka hint: $\max\{|x_{i}-y_{i}|\}\ge |x_{i}-y_{i}|$ for $i=1, 2,..., n$. $\endgroup$ – Xam Oct 24 '16 at 22:31
  • $\begingroup$ Thank you for the hint. I think I understand now. Could you verify that my attempt (in the edit above) is correct? $\endgroup$ – ozarka Oct 24 '16 at 22:38
  • 1
    $\begingroup$ Yeah, your attempt is ok but it's $n \max\{|x_{i}-y_{i}|\}$ instead of $n$ for $\max\{|x_{i}-y_{i}|\}$. $\endgroup$ – Xam Oct 24 '16 at 22:42
  • 1
    $\begingroup$ @ozarka it was a problem of formatting, but I've edited it and now should be clear. $\endgroup$ – Xam Oct 24 '16 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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