Show that $\|A\|_{\infty} \leq \sqrt n \|A\|_2$

Question

Question:

Let $A \in \Bbb R^{m\times n}$. Show that $$\|A\|_{\infty} \leq \sqrt n \|A\|_2$$

---

Attempt:

First, I tried invoking the SVD (Singular Value Decomposition) of $A$:

$$\|A\|_\infty = \|UDV\|_\infty \leq \|U\|_\infty\|D\|_\infty\|V\|_\infty \leq \sqrt m \|A\|_2\sqrt n$$

since $\|D\|_\infty$ is just the largest singular value of $A$, which is precisely $\|A\|_2$. However, the RHS of the inequality is already too large.

Next, I tried doing

$$n\|A\|_2^2 = n\bigg(\sup_x \frac{\|Ax\|_2}{\|x\|_2}\bigg)^2 \geq n \max_i \bigg(\frac{\|A e_i\|_2}{\|e_i\|_2}\bigg)^2 = n \max_i \sum_{j=1}^m a_{ji}^2$$

but this doesn't work either because the RHS has already gotten too small.

Any hints?

Answer 1

Hint: Let $i^*$ be a row with maximal absolute row sum, i.e. $$\sum_{j = 1}^{n}|A_{i^*,j}| \ge \sum_{j = 1}^{n}|A_{i,j}|$$ for all $i = 1,\ldots,n$. Also, let $v \in \mathbb{R}^n$ be a vector whose entries are $$v_j = \begin{cases}+1 & \text{if} \ A_{i^*,j} \ge 0 \\ -1 & \text{if} \ A_{i^*,j} < 0\end{cases}.$$ Now, what can you say about $\|Av\|_2$?