Consistency of matrix norm — $\| A x \|_2 \leq \| A \|_{F} \| x \|_2$

Question

I'm trying to show that

$$\| A x \|_2 \leq \| A \|_{F} \| x \|_2$$

where $A$ is an $n \times n$ matrix, $x \in \mathbb R^n$, $\| \cdot \|_2$ is the Euclidean norm, and $\| \cdot \|_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 \left|\sum_{i=1}^n a_{ji}x_i \right|^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.

Answer 1

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

Answer 2

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