Prove bound on matrix norms

Question

I can't prove the following

\begin{equation} \frac{1}{\sqrt{n}}\|A\|_\infty \leq \|A\|_2 \leq \sqrt{n} \|A\|_\infty, \end{equation}

where $A$ is a square matrix of size $n$.

---

My attempt:

By definition $$|| A|| = \sup_{ ||x||_2=1} ||A x||_2$$

So, I have:

$$\sqrt{\Bigl( \sum_j a_{1j}x_j \Bigr)^2 + \ldots + \Bigl(\sum_j a_{nj}x_j \Bigr)^2} \leq \sqrt{\Bigl(\sum_j |a_{1j}|^2 + \ldots + \sum_j |a_{nj}|^2 \Bigr) \sum_j |x_j|^2}$$

Therefore, taking the supremum over $||x||_2=1$ I bound the last expression with $$\sqrt{\Bigl(\sum_j |a_{1j}|^2 + \ldots + \sum_j |a_{nj}|^2 \Bigr)}$$

Now, I have that $$\sum_j |a_{1j}| \leq \max_{i=1,\ldots,n} \sum_j |a_{ij}| = ||A||_{\infty}$$

Therefore I can buond the last expression with $\sqrt{n ||A||_{\infty}^2}=\sqrt{n} ||A||_{\infty}$, proving the second inequality

This seems right so far, but I can't prove the other inequality: How can I do?

Answer 1

We need a

Lemma. The Cauchy-Schwarz inequality implies that for every $n$-vector $x$ it holds that

$$\| x \|_1^2 \leq \| x \|_2^2n.$$

Now write $A = (A_1, \dots, A_n)^\intercal$, where $A_i$ is the $i$-th row of $A$. By definition of $\| \cdot \|_\infty$ there is an $A_j$ such that

$$ \lVert A\rVert_\infty = \max_{1\leq i\leq n }\lVert A_i\rVert_1 = \lVert A_j\rVert_1 = \sum_{k=1}^n \left|A_{i,j}\right|. $$

Using the Lemma implies

$$\| A \|_\infty^2 = \|A_j\|_1^2 \leq \|A_j\|_2^2 n \leq \sum_{i = 1}^n \|A_i\|_2^2 n = \|A\|_2^2 n. $$

Dividing by $n$ and taking the square root yields the assertion.