On Norms

As everyone knows, norm is such a function n(x) from the vector space V to \mathbb{R}, that \forall x, y\in V, a\in\mathbb{R}:

  • n(x)=0 \Rightarrow x=\theta
  • n(ax)= |a| n(x)
  • n(x)+n(y)\geq n(x+y)

Often you have a function, and you have to check whether it’s a norm or not. The first two conditions are usually easy to verify, but the last one – the triangle inequality – often turns out to be more bothersome. But the good news is that it is equivalent to the convexity of the unit ball – a set of all x where \Vert x \Vert \leq 1. Let’s quickly prove this.

If indeed \Vert x+y \Vert \leq \Vert x\Vert+\Vert y \Vert , then we can fix two arbitrary points inside the unit ball, x_1, x_2. We need to prove that \forall \lambda\in [0, 1] vector \lambda x_1+(1-\lambda)x_2 is also inside the unit ball, that is \Vert \lambda x_1+(1-\lambda)x_2 \Vert\leq 1. But because of triangle inequality: \Vert \lambda x_1+(1-\lambda)x_2 \Vert \leq \Vert\lambda x_1\Vert+\Vert (1-\lambda)x_2\Vert =  \lambda\Vert x_1\Vert+(1-\lambda)\Vert x_2\Vert and because we know that x_1, x_2 are inside the unit ball: \lambda\Vert x_1\Vert+(1-\lambda)\Vert x_2\Vert \leq \lambda+(1-\lambda)=1, and the first part of the proof is complete.

On the other hand, if we know that the unit ball is convex and want to prove that \Vert x+y \Vert \leq \Vert x\Vert+\Vert y \Vert for every non-zero x and y,  we shall construct two vectors inside the ball, \frac{x}{\Vert x\Vert} and \frac{y}{\Vert y\Vert}. We know that \forall \lambda\in [0, 1]: \bigg|\bigg| \lambda\frac{x}{\Vert x\Vert}+(1-\lambda)\frac{y}{\Vert y\Vert}\bigg|\bigg| \leq 1.  We can choose any value of \lambda that we want, as long as it’s between 0 and 1. Let’s choose  \lambda:=\frac{\Vert x\Vert}{\Vert x\Vert + \Vert y\Vert} – clearly this expression is non-negative and less than 1. Then 1-\lambda=\frac{\Vert y\Vert}{\Vert x\Vert + \Vert y\Vert}. Now we have: \bigg|\bigg| \frac{x}{\Vert x\Vert}\frac{\Vert x\Vert}{\Vert x\Vert + \Vert y\Vert} +\frac{y}{\Vert y\Vert}\frac{\Vert y\Vert}{\Vert x\Vert + \Vert y\Vert}\bigg|\bigg| \leq 1, and when we simplify, we obtain: \bigg|\bigg| \frac{x}{\Vert x\Vert + \Vert y\Vert} +\frac{y}{\Vert x\Vert + \Vert y\Vert}\bigg|\bigg| \leq 1, which in turn means that \Vert x+y \Vert \leq \Vert x\Vert+\Vert y \Vert , and that is exactly what we wanted to prove.

Now we’re done with the proof. How can we use this little result? Suppose I give you a function and you have to say whether or not it is a norm, but this time instead of checking the triangle inequality you will be checking the convexity of the unit ball. Now, if the vector space you are working in doesn’t have too many dimensions, you can simply plot the ball and see whether or not it is convex. Obviously, this will not constitute the formal proof, but you’ll have a very clear idea of what is that you are supposed to prove and in case the ball turns out to be concave, you’ll be able to quickly construct the counterexample without having to search for it by trial and error. Let’s see how it works in practice.

Here’s a function: n_p(x)=\bigg( \sum_{k=1}^{n}|x_k|^p\bigg)^{1/p}. Is it a norm in \mathbb{R}^n , and when?  (Well, of course you recognize it as a classic l^p norm, but it’ll give me an excuse to post some pretty pictures.)

The frist two conditions are true no matter what. What about the last one?

When p \in (0, 1), assuming n=3, the unit ball looks like this:

It’s clearly concave. To prove it, we can select two points on spikes: x_1:=(1, 0, 0), x_2:=(0, 1, 0), and show that x_1/2+x_2/2=(1/2, 1/2, 0) is outside the ball, because ((1/2)^p+(1/2)^p)^{1/p}>1, when p \in (0, 1).

When p=1, the unit ball turns into an octahedron – a convex set, which tells us that the function might indeed be the norm, and searching for the counterexample would be futile.

From this point, as p increases the unit balls will remain convex.

As p is changing from 1 to 2, the octahedron is becoming increasingly “fat”:

 

At p=2 it will turn into the familiar sphere:

Then the sphere will start to grow corners:

At p=100 it will become virtually indistinguishable from the cube:

This last fact is actually pretty interesting and has some fun consequences. I’ll write more about it in my next post.

Advertisements
This entry was posted in Math and tagged . Bookmark the permalink.

One Response to On Norms

  1. christopherolah says:

    And the triangle inequality suddenly became trivial to check… Thanks for the insight!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s