Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The question: Consider two norms N1 and N2 on the space of n-by-n complex matrices. N1 and N2 have the same isometry group and computing N1 is NP-HARD. Does it follow that computing N2 is NP-HARD as well?

Motivation for believing the answer is "yes": Consider the induced matrix p-norms. It is known that these norms are efficiently computable if and only if $p = 1,2,\infty$ (http://arxiv.org/abs/0908.1397). Similarly, the isometries of the induced p-norms are known as well (they are derived in this paper) and it turns out that there are three possible isometry groups: one group for $p = 1,\infty$, another group for $p = 2$, and a third group for every other $p \neq 1,2,\infty$.

So for the induced p-norms, the difficulty of computing the norm is directly related to the isometry goup. $p = 1,\infty$ is easiest to compute ($O(n^2)$ time) and they have the same isometry group. Next hardest is operator norm (still efficient: $O(n^3)$ time naively, possibly as low as $O(n^{2+\epsilon})$ time if the conjecture about matrix multiplication is true), which has an isometry group all its own. Finally, the norms for all other values of p share the same isometry group and are NP-HARD.

Similarly, all unitarily-invariant matrix norms are easy to compute (you only need to compute their singular values), and they all share one of two different isometry groups (either the Frobenius norm isometry group or the operator norm isometry group -- this is a result of A. Sourour).

Motivation for wanting an answer: Beyond providing another way of seeing that computing the induced p-norms for $p \neq 1,2,\infty$ is NP-HARD, there is a family of matrix norms in quantum information theory that we are investigating whose isometry groups are all equal. We know that computing one of the norms is NP-HARD, and we would very much like to be able to conclude that the rest of the norms are NP-HARD as well.

share|improve this question
1  
Aren't there plenty of norms with trivial isometry group? –  Qiaochu Yuan Dec 1 '10 at 22:50
    
I assume that by the "trivial isometry group" you mean the isometry group of the Frobenius norm (i.e. the unitaries)? If so, then that's actually the only "common" norm with that isometry group. The operator norm's isometry group is generated by multiplication on the left and right by unitaries and the transpose map (which is smaller than the entire unitary group). The isometries for the induced p-norms are a bit messy to describe, but they too are proper subgroups of the unitary group. –  Nathaniel Johnston Dec 1 '10 at 22:56
    
No, I mean actually trivial. Or is there more to the definition of matrix norm than I thought? –  Qiaochu Yuan Dec 1 '10 at 23:05
2  
Qiaochu likely refers to trivial in this sense: springerlink.com/content/3k177212070313x5 –  Ryan Budney Dec 2 '10 at 0:04
1  
@Yemon: good point. @Nathaniel: a norm on R^n is determined by its unit ball, which (relative to the standard basis of R^n) is constrained only by the properties of being closed, centrally symmetric, and convex. As Yemon Choi points out, the only symmetry required of this convex body is the central symmetry, and otherwise this convex body need not have any other symmetries. It shouldn't be hard to come up with examples from here. –  Qiaochu Yuan Dec 2 '10 at 0:07
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.