# How to prove these three norm equivalence problems

Given $A \in R^{m\times n}$, I have these three norm equivalence equations:

1. $\|A\|_2 \le \|A\|_F \le \sqrt {n}\|A\|_2$
2. $\frac {1} {\sqrt n}\|A\|_{\infty} \le \|A\|_2 \le \sqrt {m} \|A\|_{\infty}$
3. $\frac {1} {\sqrt m}\|A\|_1 \le \|A\|_2 \le \sqrt {n} \|A\|_1$

I cannot use the following:

$$||A||_F = \sqrt {Tr(A^TA)}$$

I need to prove each of them. I do not even know where to begin on this so ANY help would be great!

The norms are the matrix norms. You can find more at http://en.wikipedia.org/wiki/Matrix_norm. Essentially the 1 norm is just adding up each element of a column and finding the largest column sum. The infinity norm is the same as 1 norm except you add up the elements in a row and find the largest row sum. The F norm (frobenius norm) is adding up the squares of each element in A and then taking the square root.

-
What exactly are each of these norms? –  Tom Oldfield Dec 4 '12 at 2:56
These are matrix norms: en.wikipedia.org/wiki/Matrix_norm –  echoone Dec 4 '12 at 3:03

1. The key here is to notice that $$\|A\|_F^2=\text{Tr}_n(A^TA).$$ Then $$\|A\|_2^2=\lambda_\max(A^TA)\leq\text{Tr}_n(A^TA)\leq n\lambda_\max(A^TA),$$ so $\||A\|_2\leq\|A\|_F\leq\sqrt n\|A\|_2$.
2. Here, writing $e=(1,\ldots,1)^T\in\mathbb R^n$, $$\|A\|_\infty=\max_i\sum_j|A_{ij}|=\|Ae\|_\infty\leq\|Ae\|_2\leq\|A\|_2\|e\|_2=\sqrt n\|A\|_2$$