10
$\begingroup$

How does one prove that the spectral norm is less than or equal to the Frobenius norm?

The given definition for the spectral norm of $A$ is the square root of the largest eigenvalue of $A*A$. I don't know how to use that. Is there another definition I could use? We also have $\displaystyle{\max\frac{\|Ax\|_p}{\|x\|_p}}$, but if $p=2$ it's the Frobenius norm, right?

2 Answers 2

5

Any matrix norm induced by a norm on your vector space (over $\mathbb{R}$ or $\mathbb{C}$) that also satisfies $\|A^{*}\|=\|A\|$ will be greater than or equal to the spectral norm. Let $\lambda$ denote the largest singular value of A (the square root of the largest eigenvalue of ($A^*A$) ) and $v$ the corresponding eigenvector. Let $\|A\|$ denote the matrix norm induced by a norm on the vector space: $$ \|A\|^2=\|A^{*}\|\cdot\|A\|\geq\|A^{*}A\|=\max\frac{\|A^{*}Ax\|}{\|x\|}\geq\frac{\|A^{*}Av\|}{\|v\|}=\lambda $$ and so $\|A\|\geq\sqrt{\lambda}$

For the 2-norm you actually have equality, which you can show by singular value decomposition. We can take an orthonormal basis of eigenvectors for $A^*A$ (with respect to the usual scalar product that also induces the 2-norm). Denote this basis by $v_1,\ldots,v_n$ with eigenvalues $\lambda=\lambda_1,\ldots,\lambda_n$. For any vector $x=\sum x_i v_i$ we have $$ \|Ax\|_2^2=\overline{x}^TA^{*}Ax\leq\overline{x}^T\sum\lambda_i x_i v_i=\sum\lambda_i |x_i|^2\leq \lambda \|x\|_2^2 $$ So $\|A\|_2\leq \sqrt{\lambda}$ and both inequalities together show $\|A\|_2=\sqrt{\lambda}$.

  • 1
    (1) But the Frobenius norm is not induced by a norm on your vector space, is it? (2) In your proof that $\|A\|\geq \sqrt{\lambda}$ you assumed that $\|A\|=\|A^*\|$, which is not true for many norms. (E.g., see the example in Tim Duff's answer/comment.)2012-01-22
  • 0
    Thanks, $||A||=||A^{*}||$ is really an implicit assumption. Now that I read you comment I see that I had the wrong definition of Frobenius norm!2012-01-22
  • 0
    This answer still helps, in particular with the question "Is there another definition I could use?" That is why I voted it up.2012-01-22
  • 0
    I think that Michalis` proof only works for self-adjoint matrix norms. This happens to apply in the case of the Frobenius norm, but doesn't hold for all norms (consider the max column-sum norm, $\parallel A \parallel_1 = \displaystyle\max_{1\le j \le n } $ $\displaystyle\sum_{i=1}^n a_{ij}$.)2012-01-22
  • 0
    You are obviously right!2012-01-22
  • 1
    @Jonas Meyer: Thanks :) Some people don't seem to think so unfortunately.2012-01-22
7

The Frobenius norm of $A$ is the squareroot of the sum of all of the eigenvalues (the trace) of $A^*A$, and since all eigenvalues of $A^*A$ are nonnegative, it follows that the largest eigenvalue is less than or equal to the sum of all of the eigenvalues.

If $p=2$ it's the Frobenius norm, right?

No, if $p=2$ that is another characterization of the spectral norm. A proof of this is sketched in Michalis's answer.