Frobenius Norm Inequality; Spectral Radius is smaller than Frobenius Norm

Question

Let $A \in \mathbb{R}^{n \times m}$ and $x \in \mathbb{R}^n$. Prove the following inequality. $\left\lVert \cdot \right\rVert_F$ denotes the Frobenius norm and $\left\lVert \cdot \right\rVert_2$ denotes the $p$-norm with $p=2$.

$$\left\lVert Ax \right\rVert_2 \leq \left\lVert A \right\rVert_F \left\lVert x \right\rVert_2$$

---

tl;dr: I'm essentially stuck at this (or similar) inequality:

$$ \lambda_{max} (A^T \cdot A) \leq \left\lVert A^T \cdot A \right\rVert_F$$

while $\lambda_{max}$ is the largest eigenvalue of $A^T \cdot A$. I know that this inequality holds if the norm was a natural norm, but since frobenius norm isn't induced by a vector norm, I'm not sure how to proceed.

---

How I got to this point:

$$\left\lVert Ax \right\rVert_2 \leq \left\lVert A \right\rVert_2 \left\lVert x \right\rVert_2$$

So we have to show:

$$\left\lVert A \right\rVert_2 \leq \left\lVert A \right\rVert_F$$

or

$$\left\lVert A \right\rVert_2^2 \leq \left\lVert A \right\rVert_F^{2}$$

We have:

$$\left\lVert A \right\rVert_2^2 = \lambda_{max}(A^TA) \leq \left\lVert A^T A \right\rVert_F$$

The last inequality is the part I can't prove. If I could show it, we have:

$$\left\lVert A^T A \right\rVert_F \leq \left\lVert A^T \right\rVert_F \left\lVert A \right\rVert_F = \left\lVert A \right\rVert_F^2$$

Which was the thing we wanted to show above.

---

These threads were helpful:

Show that $ \lVert A \rVert_2^2 \leq \lVert A \rVert _1 \lVert A \rVert _ \infty $

The spectral radius of the matrix $A$ is less than or equal any natural norm

Anyways, thank you for your help. It is greatly appreciated.

Answer 1

Recall that the Frobenius norm is also the Schatten $2$-norm, and thus has a characterization in terms of $2$-norm of the singular values.

Letting $B = A^T A$, $$ \lVert B\rVert_F = \sqrt{\operatorname{Tr} B^T B} = \sqrt{\sum_{i=1}^n \lambda_i(B)^2} \geq \sqrt{(\max_{1\leq i\leq n}\lambda_i(B) )^2} = \max_{1\leq i\leq n}\lambda_i(B) $$ where $(\lambda_i(B))_{1\leq i\leq n}$ are the (real) eigenvalues of the symmetric matrix $B$. This shows $$ \lVert A^TA \rVert_F \geq \lambda_\max(A^TA) $$ as desired.

Answer 2

Here's another way: First prove the following

Lemma For two matrices $A,B$ we have $\| A B \|_F \le \| A \|_F \| B \|_F$.

Let $( A B )_{i,j} := (c_{i,j})_{i,j}$ Then we have \begin{align*} \| A B \|_F^2 & \overset{\text{Def}}{=} \sum_{i,j = 1}^{n} | c_{i,j} |^2 = \sum_{i,j = 1}^{n} | \langle a_{i, \ast}, b_{\ast,j} \rangle | \overset{\text{(CS)}}{\le} \sum_{i,j = 1}^{n} \| a_{i, \ast} \|_2^2 \cdot \| b_{\ast,j} \|_2^2 \\ & = \sum_{i,j = 1}^{n} \| a_{i, \ast} \|_2^2 \cdot \sum_{i,j = 1}^{n} \| b_{\ast,j} \|_2^2 = \| A \|_F^2 \cdot \| B \|_F^2, \end{align*} where (CS) means the Cauchy-Schwarz inequality. Now, since the function $x \mapsto \sqrt{x}$ is strictly increasing and monotone, you can take the square root from both sides and the inequality (since it's $\le$ and not $<$ will be preserved).

---

Now, we can prove $\| A x \|_2 \le \| A \|_F \| x \|_2$.

Using the lemma and putting $B = x$ we have $\| x \|_F = \| x \|_2$ (since the vector $x$ has, viewed as Matrix, rank 1). Therefore, we have \begin{align*} \| A x \|_{2} = \| Ax \|_F \overset{\text{(L)}}{\le} \| A \|_F \| x \|_F = \| A \|_F \| x \|_2, \end{align*} where (L) is the inequality from the lemma.