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

Question

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?

Answer 1

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

Answer 2

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.