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.


Lemma. If $x$ is a vector in $\mathbb R^n$ with at most $r$ nonzero coordinates, then
$$
\|x\|_\infty \le \|x\|_2 \le \sqrt{r}\|x\|_\infty,
$$
where $\|x\|_p := \begin{cases}(\sum_{i=1}^n|x_i|^p)^{1/p},&\mbox{ if }1 \le p < \infty,\\\max_{i=1}^n|x_i|,&\mbox{ else.}\end{cases}$

Proof. Google "equivalence of Lp norms" (e.g https://math.stackexchange.com/a/218129/168758). $\quad\quad\Box$
Now, apply this to the vector of singular values $\sigma := (\sigma_1,\ldots,\sigma_n)$ of $A$, noting that $\|A\|_2 := \|\sigma\|_\infty$ and $\|A\|_F := \|\sigma\|_2$.
