Why are we defining the norms on certain vector spaces the way they are?

Question

What's the intuition behind defining $\|x\|_{\infty} = \max_{1 \le i \le n}\{|x_i|\}$ on the space of ordered $n$-tuples of complex numbers?

I'm asking because I've been asked to find a norm on the space of complex $m \times n$ matrices that is the analogue of $\|\cdot \|_{\infty}$. I looked around and Wikipedia mentions that $$\|A\|\ _{\infty} = \max_{1 \le i \le m} \sum_{j=1}^n |a_{ij}|.$$

Can someone explain how/why this is the proper analogue and also answer the first question I asked?

Answer 1

Actually your question is the combination of two questions.

About your first question: You certainly know the Euclidean norm, $$\left\|v\right\|_2 = \sqrt{\sum_{k=1}^n \left|v_k\right|^2} = \left(\sum_{k=1}^n \left|v_k\right|^2\right)^{\frac{1}{2}}$$ derived from the Euclidean scalar product. Note that I used absolute value bars here, which are superfluous in real vector spaces, but in complex vector spaces, they are necessary.

Now you see that there appears a number, $2$, here at several places. So a very natural question is: What if I replace that $2$ consistently with another number? Well, it turns out that for any number $\alpha\ge 1$ you indeed again get a norm, $$\left\|v\right\|_\alpha = \left(\sum_{k=1}^n\left|v_k\right|^\alpha\right)^{\frac{1}{\alpha}}$$ Moreover, it turns out that the "lower border" norm $\left\|\cdot\right\|_1$ is sort of a maximal norm: For any norm with $\left\|e_k\right\| = 1$ for all standard basis vectors $e_k$, we have $\left\|v\right\| \le \left\|v\right\|_1$ for any $v\in\mathbb R^n$. Equivalently, the unit ball of the vector-$1$ norm is the convex hull of the set $\{\pm e_k:k=1\ldots n\}$. In three dimensions it's the octahedron whose corners are exactly given by those vectors.

The next natural question is then, whether there's also a norm that's minimal in the same sense that $\left\|\cdot\right\|_1$ is maximal. The obvious place to look is at the "other end" of the vector $\alpha$ norms, that is, $\alpha\to\infty$. And indeed, the limit exists and is $$\left\|v\right\|_\infty := \lim_{\alpha\to\infty} \left\|v\right\|_\alpha = \max\{v_k: K = 1,\ldots,n\}$$

The corresponding unit ball is the convex hull of the set $\{\pm e_1\pm e_2\pm\dots\pm e_n\}$. It is geometrically easy to see that adding any point outside that set would cause one of the unit vectors no longer be on the border of the convex hull. In three dimensions, this is the cube of side length 2 centred at the origin, with the unit vectors at the middle of each face.

Now on your question about the matrix norm.

This is not the analogue to the vector norm. Rather it is the operator norm induced my the $\infty$ norm. That is, it is the norm defined by $$\left\|A\right\|_\infty = \sup\left\{\frac{\left\|Av\right\|_\infty}{\left\|v\right\|_\infty}:v\in\mathbb R^n\setminus\{0\}\right\}$$

Answer 2

In $\mathbb R^n$, the norm $\|\cdot\|_\infty$ is the one whose unit ball is the $n$-dimensional cube $[-1,1]^n$. Thus $\|x\|_\infty$ is how much you have to scale that cube so that $x$ will lie on its surface.

For $\mathbb C^n$, the definition is formally the same, though we might not be happy calling the unit ball a "cube".

For $m\times n$ matrices, I would have said that the simplest analogy would be to consider the matrices as vectors in $\mathbb C^{mn}$. What you've found on Wikipedia is not that, but what Wikipedia calls the induced norm, which arises from thinking of the $m\times n$ matrix as a linear operator from one normed space to another and quantifying how big images are. This operator norm for a matrix $A$ is how much you have to scale the unit ball of the target space so that it just contains the image under $A$ of the unit ball of the domain space.

Answer 3

Let's just think about norms in the plane. The ordinary Euclidean norm is $(x^2 + y^2)^{1/2}$. The unit circle for that norm is the ordinary unit circle. There are other useful norms. One is $|x| + |y|$. Its "unit circle" is the square with vertices $(\pm 1, 0)$ and $(0, \pm 1)$. These norms are part of a family of norms defined by $\|(x,y)\|_p = (|x|^p + |y|^p)^{1/p}$. If you watch $p$ approach infinity the unit circle will approach the square with vertices $(\pm 1, \pm 1)$. That's the unit circle for the $\|\ \|_\infty$ norm.

For pictures, see the wikipedia page http://en.wikipedia.org/wiki/Superellipse

Answer 4

Although it's not really the spirit in which you're asking, there are some senses in which these norms are the ‘only’ possibilities. They are not literally the only possibilities, and, as Studzinski pointed out in a now-deleted comment, all norms on a finite-dimensional space are topologically equivalent, so there is topologically no reason to prefer them to any random norm you can imagine; but you can impose additional conditions that single them out in the space of norms—see, for example, Newman - A characterization of $l_p$ norms on $E_n$.

As Ethan Bolker and Steven Taschuk point out, these norms also have the property that their unit ‘balls’ are visually appealing—which is a subjective thing, so let's just say that they have a reasonably nice collection of symmetries. Focussing on symmetries explains why we tend to prefer the $\ell^2$ norm: because it has the most symmetries! See Li and So - Isometries of $l_p$ norm.

Another paper on the symmetry-theoretic approach to norms, which shares an author with the one linked just above, is Li - Norms, isometries, and isometry groups.