In Matrix Analysis by Horn and Johnson (page 320 in 2nd Edition), the definition of the k-norm is as follow: $$\large \|x\|_{[k]} = |x_1| + \cdots\cdots + |x_k|,\text{ where } |x_1|\geq\cdots\geq|x_k|$$

And a property is as follow: $$\large \|\cdot\|_\infty = \|\cdot\|_{[1]}\leq\|\cdot\|_{[2]}\leq\cdots\leq\|\cdot\|_{[n]} = \|\cdot\|_1$$

Although I can verify this property , I am very confused.

$\|\cdot\|_\infty $ = max{ abs of the all elements} and $\|\cdot\|_1$ = {sum of all the elements}

How could they be equivalent? (Though they are equivalent through the proof) I think there is a gap. Any help is appreciable. Thanks!

P.S. You can also explain in matrix language.

  • $\begingroup$ Related to equivalence of $\|\cdot\|_\infty$ and $\|\cdot\|_1$: math.stackexchange.com/questions/25157/… $\endgroup$ – Martin Sleziak Aug 9 '16 at 5:39
  • $\begingroup$ @MartinSleziak In fact , I do not care about the proof. What is the intuition behind the proof( theorem)? I know they are correct $\endgroup$ – stander Qiu Aug 9 '16 at 12:58
  • $\begingroup$ Well, if you are only interested in the two norms ($\|\cdot\|_\infty$ and $\|\cdot\|_1$ it seems more-or-less obvious. The sum of $N$ positive elements is at most $N$-times the maximal of them. And you combine this with triangle inequality. The important thing is that there is only finitely many summands. $\endgroup$ – Martin Sleziak Aug 9 '16 at 13:08
  • $\begingroup$ @MartinSleziak Assume that all the elements are nonnegative. the sum of all the elements is absolutely larger than the maximum. How could they be equivalent? $\endgroup$ – stander Qiu Aug 9 '16 at 13:29
  • $\begingroup$ I am not sure what you mean. $\ell_1$ norm is defined as sum of absolute values. (BTW could you perhaps give a more precise reference than just the title of the book?) If needed, we can continue in this chat, so that we do not leave too many off-topic comments on your question. $\endgroup$ – Martin Sleziak Aug 9 '16 at 13:43

Your Answer

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

Browse other questions tagged or ask your own question.