How can one prove that $ \|A\|_2 \le \|A\|_F $ without using $ \|A\|_2^2 := \lambda_{\max}(A^TA) $?
It makes sense that the $2$-norm would be less than or equal to the Frobenius norm but I don't know how to prove it. I do know:
$$\|A\|_2 = \max_{\|x\|_2 = 1} {\|Ax\|_2}$$
and I know I can define the Frobenius norm to be:
$$\|A\|_F^2 = \sum_{j=1}^n {\|Ae_j\|_2^2}$$
but I don't see how this could help. I don't know how else to compare the two norms though.
Best Answer
Write $x=\sum_{j=1}^nc_je_j$, for coefficients $c_1,\ldots,c_n$. Suppose that $\|x\|_2=1$, i.e. $\sum_j |c_j|^2=1$. Then \begin{align} \|Ax\|_2^2&=\left\|\sum_j c_j\,Ae_j\right\|_2^2\leq\left(\sum_j|c_j|\,\|Ae_j\|_2\right)^{2}\\ \ \\ &\leq\left(\sum_j|c_j|^2\right)\sum_j\|Ae_j\|_2^2=\sum_j\|Ae_j\|_2^2=\|A\|_F^2, \end{align} where the triangle inequality is used in the first $\leq$ and Cauchy-Schwarz in the second.
As $x$ was arbitrary, we get $\|A\|_2\leq\|A\|_F$.