Getting into Norms: a technical postscript

For mathematicians’ eyes only. The post doesn’t require much theoretical knowledge to understand, but I haven’t given many definitions.

In the last two posts I’ve been talking about an example I made with four-dimensional vectors $a, b, c$ such that $\|a\|_1 > \|b\|_1 > \|c\|_1$ , $\|b\|_{2} > \|c\|_{2} > \|a\|_{2}$ and $\|c\|_{\infty}>\|a\|_{\infty}>\|b\|_{\infty}$ . Finding it was more difficult than I at first expected, so I thought I would write the investigation up, which happily gives me an excuse to introduce a useful inequality.

My first thoughts were to choose something like $c=(10,0,0,0)$ and $a=(6,6,0,0)$ or $a=(4,4,4,0)$ , and then I’d got stuck choosing $b$ . So I decided to try to prove the opposite.

First of all, it’s not possible to create such an example in two dimensions. Let’s focus on selecting $a=(a_1, a_2)$ and $b= (b_1, b_2)$ first. The ordering within each vector is irrelevant, as all three norms under consideration are symmetric (they treat each coordinate equally). Since $\|a\|_{\infty} > \|b\|_{\infty}$ we have $a_1 > b_1$ , and likewise $\|a\|_{1}>\|b\|_{1}$ implies that $a_1 + a_2 > b_1+b_2$ . This means that the sequence $a$ essentially majorizes the sequence $b$ .

Definition. A real sequence $(x_1, x_2, \ldots, x_n)$ ordered such that $x_1 \geq x_2 \geq \cdots \geq x_n$ weakly majorizes a sequence $(y_1, y_2, \ldots, y_n)$ with $y_1 \geq y_2 \geq \cdots \geq y_n$ if each initial partial sum of the first sequence is greater than the second, that is $\sum_{i=1}^k x_i \geq \sum_{i=1}^k y_i$ for each $1 \leq k \leq n$ .

Because of majorization, we can now discover something about the $\ell_2$ norm: the function $x \mapsto x^2$ is easily seen to be strictly convex, and so we may apply a version of Karamata’s inequality!

Karamata’s inequality (alternate form). If a descending real sequence $(x_1 \geq x_2 \geq \cdots \geq x_n)$ weakly majorizes $(y_1 \geq y_2 \geq \cdots \geq y_n)$ , then for any non-decreasing strictly convex function $f$ we will have $f(x_1) + f(x_2) + \cdots + f(x_n) \geq f(y_1) + f(y_2) + \cdots + f(y_n)$ .

Note: the function needs only to be strictly convex and defined on a real interval containing both sequences.

You can remove the ‘non-decreasing’ condition and gain Karamata’s usual inequality, by: deleting all the ‘weakly’s in the definition and theorem above; and by requiring the two full sums to be equal: $\sum_{i=1}^n x_i = \sum_{i=1}^n y_i$ .

Therefore we have $a_1^2 + a_2^2 > b_1^2+b_2^2$ , and so $\|a\|_{2} > \|b\|_{2}$ , the opposite of what we wanted, meaning the inequalities we were trying to prove are not possible in two dimensions.

What about in three dimensions and higher? From the two ‘extreme’ norms, we will still have $a_1>b_1$ and $a_1+a_2+a_3 > b_1+b_2+b_3$ . If we choose $a$ and $b$ such that $a_1 + a_2> b_1+b_2$ , then we can again apply Karamata’s inequality and repeating the two-dimensional work will lead to failure. So that means we must require $a_1 + a_2 < b_1 + b_2$ to have any hope of succeeding.

So I chose $a = (10, 6, 2)$ , and $b = (9, 8, 0)$ . The initial partial sums of $b$ briefly overtake those of $a$ , but fall behind again: ie. stage by stage in the addition, we have 10>9, 16<17, and 18>17. Then, fixing $\|c\|_1=16$ to be the smallest in the $\ell_1$ norm, I cheated and tried a few randomised possibilities for the coordinates of $c$ in Excel, and was quickly rewarded with: $c=(11.4, 2.4, 2.2)$ .

I specifically wanted a four-dimensional example for the post, so I added a final coordinate all equal to 1 on the end of each, which wouldn’t change any of the inequalities, and messed up the ordering of the sequences a bit.

There may be some elementary way of seeing all this, but Karamata’s inequality is neat and allows easy generalisation from the $p=2$ case to non-integer $p$ . This could mean salvation from the guilty temptation to incorrectly interpolate to get inequalities for such $p$ , once you have similar inequalities for the integer powers on either side.

While I’m revisiting old posts, Karamata’s inequality is a generalisation of the more widely known Jensen’s inequality, which is in turn a generalisation of the arithmetic-geometric inequality, which, perhaps surprisingly, contributed to a day of strikes in Britain. The link is a proposed change from RPI to the lower CPI in public sector pensions.

Finally, “Karamata’s inequality” doesn’t quite scan to the tune of the Katamari Damacy theme, but if singing “Na naaa na na na nana nana na na Karamata’s inequality” helps you to remember this useful but perhaps overlooked inequality, does an extra syllable really matter?

About these ads

Getting into Norms: a technical postscript

Leave a Reply Cancel reply

Subscribe via RSS

Twitter Updates

Archives

Blogroll

Functional Analysts

Learning

Learning: Banach spaces

Puzzles

Resources

Round-ups

Technical

Videos (& radio)

Tags

Math Blogging weekly picks

Follow “Out of the Norm”

Getting into Norms: a technical postscript

Share this:

Like this:

Leave a Reply Cancel reply

Subscribe via RSS

Twitter Updates

Archives

Blogroll

Functional Analysts

Learning

Learning: Banach spaces

Puzzles

Resources

Round-ups

Technical

Videos (& radio)

Tags

Math Blogging weekly picks

Follow “Out of the Norm”