# Is the problem of calculating the induced norm *difficult*?

Is the problem of calculating the induced norm of a linear operator (in a finite or infinite-dimensional space) generally a difficult one ?

And by difficult I mean, that there are no closed formulas or no general procedure that always yields the induced norm.

Of course, for the usual spaces with the usual norms, there are formulas, that makes ones life very, so one can take shortcuts in calculating the induced norm of a operator (instead of trying to use the definition of the induced norm : $$||A||=\sup_{||x||=1} ||Ax||).$$ But is there also a procedure how to calculate $||A||$ for some very weird vector norms, or for some unsual infinitedimensional spaces (since in finite dimensions we can at least use the fact, that every vectors space is isomorphic to $\mathbb{K}^n$ for some $n$) ?

EDIT: I think the user tomasz bst described what I meant. Are there vector norms such that for their induced operator norm it is proven that there isn't a closed expression ?

-
This question is rather vague. First of all, I'm not sure what you mean by "induced norm"; it looks like perhaps you are talking about the operator norm, in which case your displayed equation should have the sup over $\|x\|=1$. Anyway, given the wide variety of linear operators that can exist, and the many ways in which they can be defined, I don't see how one could expect a "general procedure" to exist. – Nate Eldredge Jul 30 '12 at 16:14
@NateEldredge: Induced norm is a fairly standard term. – copper.hat Jul 30 '12 at 16:28
If you have a space where the norm of an element is very hard to calculate, I doubt you can expect to find an easy way to calculate the norm of an arbitrary operator. As stated the question is a bit too vague, but I have no good idea how to improve it... Still, perhaps a more interesting question would be: are there any nice (but pathological) examples of operators whose norm is provably incomputable (even though norm of any specific vector is)? – tomasz Jul 30 '12 at 16:28
@copper.hat: Ok. I usually hear "induced norm" used in the context of "the norm induced by an inner product" and the like, so I was confused. – Nate Eldredge Jul 30 '12 at 16:31
You need to formulate the notion of 'there isn't a closed expression'. The underlying norm may have no 'closed expression'? I would guess that informally most would say there is no way of computing a general closed expression, but to formalize that may take a bit of work (I'm definitely off-piste here). – copper.hat Jul 30 '12 at 16:40

Following on from @tomasz's comment: There are examples of operators whose induced norm is NP-hard to approximate even though the norm in the original vector space can be immediately computed.

Here, we'll work with the real vector space $\ell_p^n$. Consider the problem of computing the norm of a matrix $T: \ell_p^n \to \ell_p^n$, $$\Vert T \Vert_{p \to p} = \sup_{\Vert x \Vert_p =1} \Vert Tx \Vert_p.$$ If $p \in \{1, \infty\}$, then the exact value of this norm is easily computed. If $p=2$, then it can be efficiently approximated (where "efficiently" depends on the size $n$ of the problem and the desired accuracy $\varepsilon$). However, this is not true for other values of $p$ even when we insist that the map satisfies the condition $T_{ij} \in \{-1,0,1\}$.

The following theorem is taken from http://arxiv.org/abs/0908.1397 .

Theorem: For any rational $p ∈ [1,\infty)$ except $p = 1,2$, unless P = NP, there is no algorithm which computes the p-norm of a matrix with entries in $\{−1, 0, 1\}$ to relative error $\varepsilon$ with running time polynomial in $n, 1/\varepsilon$ .

In particular, there should be no "nice", "easy" formula in terms of $T_{ij}$ that immediately tells you the value of the induced norm $\Vert T \Vert_{p \to p}$.

-

Consider the linear operator $T : \mathbb{R} \to \mathbb{R}$ which is identically $0$ if the Riemann hypothesis is true and the identity if the Riemann hypothesis is false. What is the operator norm of $T$?

(In general, the question also depends on what you know about $T$.)

-
Well, I actually meant a slightly different kind of "difficult", where the difficulty of getting the induced norm doesn't reduce to knowing the answer of another (not related) famous conjecture, although your example is certainly valid – pink_pyjamas Jul 31 '12 at 8:20
Yes, this was facetious. I'm just trying to get you to clarify your question. – Qiaochu Yuan Jul 31 '12 at 13:09