Denote by $M_n$ the space of $n \times n$ real matrices. We say a norm on $M_n$ is orthogonal invariant if: $$\|OX \|=\| XO\|=\|X \| \, \, \forall O \in O_n,X \in M_n$$

I am trying to characterize all such norms. Let $\|\cdot \|$ be one. Using singular values decomposition, we get:

$\|X\|=\|U\Sigma V^T\|=\|\Sigma \|$ (when $U,V \in O_n, \Sigma$ is a diagonal with non-negative entries, i.e $U \Sigma V^T$ is a SVD of $X$)

So, if we define $f:\mathbb{R}^n \to \mathbb{R}^{\ge 0}$ by $f(\sigma_1,\dots,\sigma_n)=\|\operatorname{diag}(\sigma_1,\dots,\sigma_n) \|$ we get that $\|\cdot\|$ is uniquely determined by $f$. Note that $f$ must be a norm which is invariant under signed permutations, i.e: $f(\pm x_{\tau(1)},\dots,\pm x_{\tau(n)})=f(x_1,\dots,x_n)$ for every $\tau \in S_n$. (The reason is that $\| \cdot\|$ is invariant under orthogonal multiplication, in particular by signed permutation matrices).

Question: Is it true that any norm on $\mathbb{R}^n$ which is invariant under signed permutations induces an orhtogonal-invariant norm on $M_n$? (in the obvious way as described above). If not, can we characterize which norms are possible?

Added Clarification: Let $f$ be a norm on $\mathbb{R}^n$. The possible candidate for a norm on $M_n$ induced by $f$ is: $\| X\|=\|U\Sigma V^T \|=f(\sigma_1,\dots,\sigma_n)$ where $\Sigma=\operatorname{diag}(\sigma_1,\dots,\sigma_n) $.

The non trivial part seems to be verifying the triangle inequality, since SVD does not behave in a structured way (known to me) w.r.t sums.

Remarks and partial results:

1) Choosing $f$ to be the maximumn norm induces the Euclidean operator norm. (see here).

2) Choosing $f$ to be the standard $p$-norm, one gets the $p-$ Schatten norm.

3) Here is a sufficient condition (which is not necessary) inducing a norm: $$\sum_{i=1}^n z_i \le \sum_{i=1}^n x_i + \sum_{i=1}^n y_i \Rightarrow f(z_1,\dots,z_n) \le f(x_1,\dots,x_n) + f(y_1,\dots,y_n)$$

Any $f$ which satisfies the above condition induces a norm. This follows from Lidskii inequality which says:

$$\sum_{i=1}^n \sigma_i(A+B) \le \sum_{i=1}^n \sigma_i(A) + \sum_{i=1}^n \sigma_i(B) $$

Note this condition is not necessary: The maximum norm does not satisfy it, but induces a norm.


I think the answer is yes. A sign- and permutation- invariant norm defined on $\mathbb C^n$ is called a symmetric gauge function. It is known that every unitarily invariant norm on $M_n(\mathbb C)$ is induced by a symmetric gauge function. See, e.g. theorem 7.4.24 on pp.438-440 of Horn and Johnson (1985), Matrix Analysis, 1/e, Cambridge University Press.

To deal with the triangle inequality, Horn and Johnson considered the dual norm of $f$. Although the theorem focuses on a norm $f$ defined on $\mathbb C^n$, since the dual norm of a norm defined on $\mathbb R^n$ is also a norm on $\mathbb R^n$ and since every real matrix admits a real SVD, apparently their proof can be adapted to the real case almost without modification. Yet, you still need to double-check whether this adaptation really works or not.

  • $\begingroup$ Maybe I am wrong, but I think that choosing the maximum norm, induces the standard operator norm (which is orthogonally-invariant) and not the maximum row sum norm. For instance see here: math.stackexchange.com/questions/586663/… $\endgroup$ – Asaf Shachar Apr 12 '16 at 14:43
  • $\begingroup$ Ok, I think I understand our misunderstanding now. You thought I meant to use the norm on $\mathbb{R}^n$ to induce a norm on the space of matrices in the sense of operator norm. I, However, meant for a different way of inducing as described in the question. (I now have edited the question to indicate this more clearly). So to conclude, your answer is true, and interesting, but it is an answer to a different question. $\endgroup$ – Asaf Shachar Apr 12 '16 at 16:54
  • $\begingroup$ @AsafShachar Thanks for the clarification. Please see my new edit. $\endgroup$ – user1551 Apr 13 '16 at 0:46
  • $\begingroup$ Thanks for your answer! I read the proof you referred to and indeed it seems to me like it's adaptable to the real case. $\endgroup$ – Asaf Shachar Apr 13 '16 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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