Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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}$.) –  user17794 Jan 22 '12 at 2:32
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.) –  Jonas Meyer Jan 22 '12 at 3:34
    
You are obviously right! –  Michalis Jan 22 '12 at 8:29
    
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! –  Michalis Jan 22 '12 at 8:30
1  
@Jonas Meyer: Thanks :) Some people don't seem to think so unfortunately. –  Michalis Jan 22 '12 at 20:48

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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