# why is frobenius norm of a matrix greater than or equal to the 2 norm?

How can you prove that: $$\|A\|_2 \le \|A\|_F$$ I cannot use: $$\|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 dont 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 dont see how this could help. I dont know how else to compare the two norms though.

-
Let $\Vert A\|_2 = \|Av\|$ for some $v$ with $\|v\| = 1$. Define an orthogonal matrix $U$ for which $v$ is the first column. Compute $\Vert AU\Vert_F$ and show that it is equal to $\Vert A\Vert_F$, then compare it to $\Vert Av\Vert$ by a direct computation. –  Hans Engler Dec 7 '12 at 4:36
@HansEngler I dont exactly understand your answer. How would I compute $||AU||_2$ and if it is equal to $||A||_2$ then how does that prove anything about $||A||_F$? –  user972276 Dec 7 '12 at 4:42
@HansEngler I dont understand how to show $||AU||_F = ||A||_F$. I understand that the first column of AU is just Av and so I can show that $||A||_2 \le ||A||_F$. –  user972276 Dec 7 '12 at 4:50
$\Vert A\Vert_F^2 = trace(AA^T)$. Now compute the same thing for $AU$ and use the fact that $U$ is orthogonal. –  Hans Engler Dec 7 '12 at 12:14

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 $$\|Ax\|_2^2=\|\sum_j c_j\,Ae_j\|_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,$$ 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$.

-
is there a way to do it without using Cauchy-Schwartz? –  user972276 Dec 7 '12 at 4:54
Not that I can think of. In any case I simplified the argument by using the triangle inequality (basically, the previous version had a built-in proof of the triangle inequality, which by the way I don't think you can prove without CS). –  Martin Argerami Dec 7 '12 at 10:58

In fact, the proof from $\left\| \mathbf{A}\right\|_2 =\max_{\left\| \mathbf{x}\right\|_2=1} \left\| \mathbf{Ax} \right\|_2$ to $\left\| \mathbf{A}\right\|_2 = \sqrt{\lambda_{\max}(\mathbf{A}^H \mathbf{A})}$ is straight forward. Assume $\mathbf{A} \in \mathbb{C}^{m \times n}$

$$\left\| \mathbf{A}\right\|_2 =\max_{\left\| \mathbf{x}\right\|_2=1} \left\| \mathbf{Ax} \right\|_2 = \max_{\mathbf{x}^H \mathbf{x}=1} \sqrt{\mathbf{x}^H \mathbf{A}^H \mathbf{Ax}} = \max_{1\leq i \leq n} \sqrt{\lambda_i}$$

We just need to notice that $\mathbf{A}^H \mathbf{Ax}=\lambda \mathbf{x}$, where $\lambda$ is just a scalar.

And then, because the $n\times n$ matrix $\mathbf{A}^H \mathbf{A}$ is positive semidefinite, all of its eigenvalues are not less than zero. Assume $\text{rank}~\mathbf{A}^H \mathbf{A}=r$, we can put the eigenvalues into a decrease order:

$$\lambda_1 \geq \lambda_2 \geq \lambda_r > \lambda_{r+1} = \cdots = \lambda_n = 0.$$

Because for all $\mathbf{X}\in \mathbb{C}^{n\times n}$, $$\text{trace}~\mathbf{X} = \sum\limits_{i=1}^{n} \lambda_i,$$ where $\lambda_i$, $i=1,2,\ldots,n$ are eigenvalues of $\mathbf{X}$; and besides, it's easy to verify $$\left\| \mathbf{A}\right\|_F = \sqrt{\text{trace}~ \mathbf{A}^H \mathbf{A}}.$$

Thus, through $$\sqrt{\lambda_1} \leq \sqrt{\sum_{i=1}^{n} \lambda_i} \leq \sqrt{r \cdot \lambda_1}$$ we have $$\left\| \mathbf{A}\right\|_2 \leq \left\| \mathbf{A}\right\|_F \leq \sqrt{r} \left\| \mathbf{A}\right\|_2$$

-
This proof needs to use a conclusion: when $\mathbf{P}$ is Hermitian, the maximal eigenvalue $\lambda_{\max} = \max_{\left\|x\right\|_2=1} \mathbf{x}^H \mathbf{Px}$. –  Stan Mar 31 at 6:16