proof for matrix norms

How do I prove these two inequalities on matrix norms:

1. $\Vert A \Vert_1 \leq n\Vert A \Vert_\infty,$
2. $\Vert A \Vert_1 \leq \sqrt{n}\cdot\Vert A\Vert_F$ , where A is $m$-by-$n$ real matrix.
-
Please write this in proper Tex. I have no idea what you are asking. There is a live preview... –  Steven Gubkin Mar 2 at 20:25
With the help of a little \Vert, I made the question a bit more readable. @Elnaz, what do you know of these matrix norms? –  Roland Mar 2 at 20:39
I know the definitions; they are provided in the Wikipedia, however with no proofs. –  Elnaz Mar 2 at 20:40
Are you referring to the induced norms or the "entrywise" norms? –  Omnomnomnom Mar 2 at 20:43
I'm referring to the extension of vector norms to the matrix norms; so yes these are induced norms. –  Elnaz Mar 2 at 20:50

(1) Typically, to prove $\|A\|_1 \le C$, you prove $$\|Ax\|_1 \le C\|x\|_1$$ (and then take the sup over $x$ such that $\|x\|_1=1$, or over $x$ such that $\|x\|\ne 0$, whichever you find more convenient). So we want to show $$\|Ax\|_1 \le n\|A\|_\infty \|x\|_1 \tag{a}$$ A typical method of proving an inequality is by a chain of inequalities, like $$\|Ax\|_1 \le \dotsm \le \dotsm \le n\|A\|_\infty \|x\|_1$$ To write such a chain, at some point we'll need to introduce $\|A\|_\infty$ (since it appears at the far right but not on the far left), and to do that, you typically use the fact that $$\|Ax\|_\infty \le \|A\|_\infty \|x\|_\infty \tag{b}$$ So we expect to invoke (b) in our proof of (a). Comparing (b) and (a) suggests the following plan: replace $\|Ax\|_1$ with $\|Ax\|_\infty$ somehow, then invoke (b), then replace $\|x\|_\infty$ with $\|x\|_1$ somehow. Presumably the $n$ will appear along the way. This plan calls for some inequalities relating the vector norms $\|\cdot\|_\infty$ and $\|\cdot\|_1$; I'll just assume here that we remember the inequalities $$\|x\|_\infty \le \|x\|_1 \le n\|x\|_\infty$$ Using these inequalities to carry out our plan yields the following argument: \begin{align*} \|Ax\|_1 &\le n\|Ax\|_\infty &&\text{(replace $\|\cdot\|_1$ with $\|\cdot\|_\infty$)}\\ &\le n\|A\|_\infty\|x\|_\infty &&\text{(invoke (b))}\\ &\le n\|A\|_\infty\|x\|_1 &&\text{(replace $\|\cdot\|_\infty$ with $\|\cdot\|_1$)} \end{align*} That proves (1).
(2) The method used in (1) yields $$\|A\|_1 \le \sqrt n \|A\|_2$$ We'd be done if we could show that $$\|A\|_2\le\|A\|_F \tag{c}$$ Since the norm on the left of (c) is an "induced" norm, we expect, as in (1), to prove (c) by showing $$\|Ax\|_2\le \|A\|_F\|x\|_2$$ Writing this out in coordinates: $$\Big(\sum_{i=1}^m \Big(\sum_{j=1}^n a_{ij} x_j\Big)^2\Big)^{1/2} \le \Big(\sum_{i=1}^m \sum_{j=1}^n a_{ij}^2\Big)^{1/2} \Big(\sum_{j=1}^n x_j^2\Big)^{1/2}$$ Tidy up by squaring everything: $$\sum_{i=1}^m \Big(\sum_{j=1}^n a_{ij} x_j\Big)^2 \le \sum_{i=1}^m \sum_{j=1}^n a_{ij}^2 \sum_{j=1}^n x_j^2$$ Seeing $\sum_{i=1}^m$ on both sides (and noting that it doesn't matter whether we think of $\sum_{j=1}^n x_j^2$ on the RHS as being inside or outside of the $\sum_{i=1}^m$), we might hope to prove this by proving the termwise inequality $$\Big(\sum_{j=1}^n a_{ij} x_j\Big)^2 \le \sum_{j=1}^n a_{ij}^2 \sum_{j=1}^n x_j^2$$ and then summing over $i$. That doesn't always work, but it's the simplest thing that could possibly work, so we try it first. And indeed, now we recognize Cauchy-Schwarz (if we didn't before).