Why is the Frobenius norm of a matrix greater than or equal to the spectral norm? 
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.

The OP defines $\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2$. Let $x$ be a maximiser of $\|Ax\|_2$ on the unit sphere. By completing $\{x\}$ to an orthonormal basis of $\mathbb R^n$, we can obtain an orthogonal matrix $Q$ whose first column is $x$. Therefore $\|Ax\|_2=\|AQe_1\|_2=\|Q^TAQe_1\|_2\le\|Q^TAQ\|_F=\|A\|_F$, where $e_1=(1,0,\ldots,0)^T$.
