2
$\begingroup$

Consider a normed vector space $(\mathbb{R}^n,\mathbb{R},||\cdot||_p)$. For any $x\in\mathbb R^n$, we want to show the following:

$$||x||_{\infty}\leq||x||_1\leq n||x||_{\infty}.$$

I remember from metric spaces that we can define $u_i=|x_i-y_i|$ for all $i$ where $x=(x_1,\ldots,x_n)$ and $y=(y_1,\ldots,y_n)$. Hence, we have $||x||_{\infty}=\max\{u_1,\ldots,u_n\}$ and $||x||_1=\sum_{i=1}^{n}u_i$.

By the fact $|x_i-y_i|\leq\max|x_i-y_i|$ for all $i$, we have that $$u_1+\cdots+u_n\leq\max u_1+\cdots+\max u_n$$ which proves the second inequality.

I am not sure how to show the first inequality rigorously. Intuitively it makes sense that the sum of all positive differences of $x$ and $y$ have to be greater than the maximum of one difference.

I'd appreciate any hint or help. Thank you.

$\endgroup$
1
  • 1
    $\begingroup$ Your understanding of the definitions of norms is not correct, check en.wikipedia.org/wiki/Norm_(mathematics)#p-norm, but your reasoning is (almost) correct for the second inequality. Correct it using the right definitions of norms. The first inequality follows because you sum over all $|x_i|$ in $||x||_1$, but only take the largest $|x_i|$ in $||x||_{\infty}$. $\endgroup$
    – B.Swan
    Commented Mar 18, 2019 at 2:50

2 Answers 2

4
$\begingroup$

You are putting a $y$ in the mix that you don't need.

As you say, you have $$ \|x\|_1=\sum_j|x_j|\leq\sum_j\|x\|_\infty=n\|x\|_\infty. $$ Also, if $k$ is such that $\|x\|_\infty=|x_k|$, then $$ \|x\|_\infty=|x_k|\leq\sum_j|x_j|=\|x\|_1. $$

$\endgroup$
4
  • $\begingroup$ What is the justification for $$\sum_j |x_j|\leq\sum_j \| x\|_{\infty}?$$ $\endgroup$
    – M B
    Commented Mar 6, 2020 at 8:05
  • 1
    $\begingroup$ That $\|x_j\|\leq\|x\|_\infty $ by definition. $\endgroup$ Commented Mar 6, 2020 at 14:15
  • $\begingroup$ Did you use the Cauchy-Swartz inequality to get the $n$? I do not understand where this came from. $\endgroup$
    – M B
    Commented Mar 6, 2020 at 23:45
  • 1
    $\begingroup$ It comes from adding $n$ times the same thing. $\endgroup$ Commented Mar 7, 2020 at 0:56
2
$\begingroup$

By definition, $$||x||_{\infty}=\max\{|u_1|,\ldots,|u_n|\} = |u_p|,$$ for some $1 \leq p \leq n$. Clearly, $$|u_p| \leq \sum_1^n |u_i| = ||x||_{1}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .