p norm Matrix relationship

Question

I am trying to show that $\Vert A \Vert_\infty \leq \sqrt{n}\Vert A \Vert_2$ given that $A \in \mathbb{R}^{m \times n}$, $\Vert A \Vert_\infty = \max \limits_{1\leq i \leq n} \sum\limits_{j=1}^n \vert a_{ij}\vert$, and $\Vert A \Vert_2 = \sqrt{\lambda_{max}} = \sigma_1$ (the largest singular value). I can show that $$ \frac{\Vert A \Vert_\infty}{\sqrt{n}} \leq \Vert A \Vert_\infty $$ which is obvious. I am having trouble showing that $\Vert A \Vert_\infty$ is related to $\Vert A \Vert_2$ in any way. Is there something I have overlooked?

Answer 1

I assume you want to show $$\Vert A \Vert_{\infty} \leq \Vert A \Vert_2 \leq \sqrt{n} \Vert A \Vert_{\infty}$$ First show that $$\Vert x \Vert_{\infty} \leq \Vert x \Vert_2 \leq \sqrt{n} \Vert x \Vert_{\infty}$$ where $x$ is a vector. Since the matrix norm is induced by vector norm, the result will carry over to matrices as well. Move your cursor over the gray area to see how to prove this.

Note that $$\Vert x \Vert_2^2 = x_1^2 + x_2^2 + x_3^2 + \cdots x_n^2 \geq x_{k,max}^2$$ since $x_{k,max}$ is one element in $\{x_1,x_2,\ldots,x_n\}$ and $$x_1^2 + x_2^2 + x_3^2 + \cdots x_n^2 \leq x_{k,max}^2 + x_{k,max}^2 + \cdots + x_{k,max}^2$$ since each element has to be less than $x_{k,max}$.