11
$\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?

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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}$.

$\endgroup$
7
  • $\begingroup$ 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}$.) $\endgroup$
    – user17794
    Commented Jan 22, 2012 at 2:32
  • 1
    $\begingroup$ (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.) $\endgroup$ Commented Jan 22, 2012 at 3:34
  • $\begingroup$ You are obviously right! $\endgroup$
    – MichalisN
    Commented Jan 22, 2012 at 8:29
  • $\begingroup$ 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! $\endgroup$
    – MichalisN
    Commented Jan 22, 2012 at 8:30
  • 1
    $\begingroup$ @Jonas Meyer: Thanks :) Some people don't seem to think so unfortunately. $\endgroup$
    – MichalisN
    Commented Jan 22, 2012 at 20:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .