Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.
share|improve this question
    
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 Answer 1

(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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.