3
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Aren't there plenty of norms with trivial isometry group? $\endgroup$
    – Qiaochu Yuan
    Dec 1, 2010 at 22:50
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel Johnston
    Dec 1, 2010 at 22:56
  • 2
    $\begingroup$ Qiaochu likely refers to trivial in this sense: springerlink.com/content/3k177212070313x5 $\endgroup$
    – Ryan Budney
    Dec 2, 2010 at 0:04
  • 1
    $\begingroup$ @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. $\endgroup$
    – Qiaochu Yuan
    Dec 2, 2010 at 0:07
  • 1
    $\begingroup$ @Nathaniel: start with the unit ball in R^n, pick three points lying slightly outside it, fairly close together, and in general position, and take the convex hull and then the "central closure" (I hope it is clear what I mean by this) of the result. This defines a norm with trivial isometry group which I think should be easily computable: if the points are spaced sufficiently far apart relative to their distance from the ball then one has just stuck some conical caps onto the unit ball, which are easy to work with. $\endgroup$
    – Qiaochu Yuan
    Dec 2, 2010 at 1:53

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.