5
$\begingroup$

I'm trying to show that $||Ax||_2 \leq ||A||_{F}||x||_2$

where $A$ is an n by n matrix, $x\in \mathbb R^n$, $||x||_2$ is the euclidean norm, and $||A||_F$ is the frobenius norm.

I actually wrote down what $Ax$ is, it is

$Ax =\begin{pmatrix} \sum_{i=1}^n a_{1i}x_i \\\sum_{i=1}^n a_{2i}x_i \\ \vdots \\ \sum_{i=1}^n a_{ni}x_i \end{pmatrix}$

And so:

$||Ax||_2 = \sqrt{\sum_{j=1}^n |\sum_{i=1}^n a_{ji}x_i|^2}$

I need to show that that is smaller than

$\sqrt{\sum_{j=1}^n \sum_{i=1}^n |a_{ij}|^2\sum_{k=1}^n |x_k|^2}$

But this seems very complicated...I'd love a hint in the right direction

$\endgroup$
5
  • $\begingroup$ Schwarz inequality $\endgroup$ – JPi Apr 3 '14 at 17:29
  • $\begingroup$ Could you be a little more specific? Cauchy-Schwarz inequality states $|<x,y>|^2 \leq <x,x><y,y>$. there are 2 vectors there. In my question there is only one. not only that, one norm is euclidean and the other is frobenius... $\endgroup$ – Oria Gruber Apr 3 '14 at 17:34
  • $\begingroup$ See the proof of (c) in this answer $\endgroup$ – user21467 Apr 3 '14 at 18:13
  • $\begingroup$ @StevenTaschuk I think it would be OK to copy and paste your answer here, since it's not a duplciate. $\endgroup$ – Git Gud Apr 3 '14 at 22:02
  • $\begingroup$ @GitGud OK, will do. $\endgroup$ – user21467 Apr 3 '14 at 22:27
7
$\begingroup$

We want to prove $$ \|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).

extracted from a previous answer

$\endgroup$
3
  • $\begingroup$ I up voted the other one, so I won't up vote this one. $\endgroup$ – Git Gud Apr 3 '14 at 22:30
  • $\begingroup$ @GitGud Yeah, no worries. $\endgroup$ – user21467 Apr 3 '14 at 22:31
  • $\begingroup$ Thanks!that was very clear $\endgroup$ – Oria Gruber Apr 4 '14 at 10:55
8
$\begingroup$

Since the matrix norm $\|\cdot\|_2$ is an operator norm, we have $\|Ax\|_2\leq\|A\|_2\|x\|_2$. The rest follows from the fact that $\|A\|_2\leq\|A\|_F$. This is true simply because $$ \|A\|_2^2=\rho(A^TA)=\lambda_{\max}(A^TA)\leq\sum_{i=1}^n\lambda_i(A^TA)\leq\mathrm{trace}(A^TA)=\|A\|_F^2. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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