So, I am trying to show that for a matrix $A \in \mathbb{R}^{m \times n}$, $||A||_{\infty} \leq \sqrt{n} ||A||_2$.
Starting from $||A||_{\infty} = \max \limits_{||x||_{\infty}=1}||Ax||_{\infty} = \max \limits_{||x||_{\infty}=1}\Big( \max \limits_{i=1, \cdots, m}|\sum_{j=1}^n a_{ij}x_j|\Big) $, I'm trying to connect it to $||A||_2=\max \limits_{||x||_2=1}\Big( \sum_{i=1}^m (\sum_{j=1}^n a_{ij}x_j)^2 \Big)$.
I know that ${||x||_{\infty}=1}$ implies $|x_j| \leq 1$, but I cannot see how to push it toward having a $\sqrt n$ in the RHS. How can I do that? Am I on the right path at all? Thanks.
Let $x = (x_1, \ldots, x_n)$. Since $|x_i| \leq \lVert x \rVert_\infty$ for all $i$, by squaring and adding we get $\lVert x \rVert_2^2 \leq n \lVert x \rVert_\infty^2$, and taking square roots gives $\lVert x \rVert_2 \leq \sqrt{n} \lVert x \rVert_\infty$. Can you take things from here?