# Consistency of matrix norm: $||Ax||_2 \leq ||A||_{Frobenius}||x||_2$

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

• Schwarz inequality – JPi Apr 3 '14 at 17:29
• 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... – Oria Gruber Apr 3 '14 at 17:34
• See the proof of (c) in this answer – user21467 Apr 3 '14 at 18:13
• @StevenTaschuk I think it would be OK to copy and paste your answer here, since it's not a duplciate. – Git Gud Apr 3 '14 at 22:02
• @GitGud OK, will do. – user21467 Apr 3 '14 at 22:27

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