Suppose a nonlinear infinitely continous differentiable function $f:\mathbb{D}\mapsto \mathbb{R^+}$, where $\mathbb{D}\subset\left\{X|\text{rank}{X}=2,X\in\mathbb{R}^{3\times 3}\right\}$ is a continous, open, convex set,

How to define a matrix norm $\left\|\cdot\right\|_p$ in $\mathbb{D}$, such that $\forall x_1, x_2\in \mathbb{D}$: $$\lim\limits_{\left\|x_1-x_2\right\|_p\to 0}|f(x_1)-f(x_2)|=0,$$ $$\lim\limits_{\left\|x_1-x_2\right\|_p\to 0}\left\|x_1-x_2\right\|_2=0$$ $$\quad\lim\limits_{\left\|x_1-x_2\right\|_p\to 0}\left\|x_1-x_2\right\|_{\infty}=0,$$ $$\lim\limits_{\left\|x_1-x_2\right\|_p\to 0}\left\|x_1-x_2\right\|_1=0,$$

and the $9\times 1$ vectors $y_1 = x_1(:),y_2=x_2(:)$(use Matlab/Octave operator here) $$\lim\limits_{\left\|x_1-x_2\right\|_p\to 0}\left\|y_1-y_2\right\|_2=0,$$

Must the calculation of such matrix norm be NP-hard?

  • $\begingroup$ I must be missing something here... why doesn't one of the usual matrix norms work? $\endgroup$ Feb 9, 2014 at 15:41
  • $\begingroup$ What's a continuous set? $\endgroup$ Feb 9, 2014 at 17:17
  • $\begingroup$ by continuous, I mean connected $\endgroup$ Feb 10, 2014 at 0:24
  • $\begingroup$ Usual matrix norm does not work because of the first criterion: $|f(x_1)-f(x_2)|$ which is the most critical $\endgroup$ Feb 10, 2014 at 0:25
  • 1
    $\begingroup$ To talk of continuity and differentiability, you have explain what you mean if you don't mean the usual topology on $\mathbb{R}^9$. If you do, then all norms are equivalent. $\endgroup$
    – username
    Feb 11, 2014 at 18:47

1 Answer 1


(This isn't an answer, but I'm not allowed to comment yet and I think this is a worthwhile question, even if it means violating the rules; i'll delete the post when the time comes)

You claim that usual matrix norms do not work because of the $|f(x_1)-f(x_2)|$ criterion, but if $f$ is differentiable, then given any $x_1$ it is Lipschitz in some neighborhood of $x_1$ (with a constant that may depend on $x_1$), and hence $|f(x_1)-f(x_2)|\leq C \|x_1(:)-x_2(:)\|_1$. Did I miss something?

  • $\begingroup$ My puzzle mainly lies in the conflicts between theoretical proof and numerical experiments. Probably because the difference between $x_1$ and $x_2$ has not been small enough? $\endgroup$ Feb 12, 2014 at 6:40
  • $\begingroup$ Do you mean that you did numerical experiments with some norm and the difference didn't seem to go to zero? Assuming you didn't have any bugs, it could be that a) the "norm" you used was degenerate, i.e. wasn't actually a norm, and could be $0$ even when $x_1\neq x_2$, or b) the function you were using was not sufficiently well-behaved to yield stable results at numerical precision. Perhaps you could edit your question with more details about what you were trying out? $\endgroup$
    – martin
    Feb 12, 2014 at 9:06
  • $\begingroup$ I will need time to make it clear whether I made any mistake. Thank you for suggestions. $\endgroup$ Feb 12, 2014 at 9:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.