# p norm Matrix relationship

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?

-
The $j$ in your definition of $\|A\|_\infty$ is unspecified. Do you mean $\|A\|=\max_{1\le i\le n}\sum_{j=1}^n|a_{ij}|$? – user1551 Jan 18 '13 at 23:40
What is $\lambda_{max}$? I guess it's the largest eigenvalue of $A^tA$? – user108903 Jan 19 '13 at 0:31

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}$.
That assumption is incorrect. I am trying to show $\Vert A \Vert_\infty \leq \sqrt{n}\Vert A \Vert_2$. I have that $\Vert x \Vert_2 \leq \sqrt{m}\Vert x \Vert_\infty$ and $\Vert x \Vert_\infty \leq \Vert x \Vert_2$ for $x \in R^m$ if that helps – rioneye Jan 19 '13 at 1:04
@rioneye You can prove something stronger. You can show that $$\Vert A \Vert_{\infty} \leq \Vert A \Vert_2$$ and that is what I have shown. Clearly, $$\Vert A \Vert_{\infty} \leq \Vert A \Vert_2 \implies \Vert A \Vert_{\infty} \leq \sqrt{n} \Vert A \Vert_2$$ – user17762 Jan 19 '13 at 1:08
@rioneye $$\Vert A \Vert_p = \max_{x} \dfrac{\Vert Ax \Vert_p}{\Vert x \Vert_p}$$ Note that $$\Vert Ax \Vert_{\infty} \leq \Vert Ax \Vert_{2}$$ for all $x$. Use this to show that (in fact, it follows immediately) $$\max_{x} \dfrac{\Vert Ax \Vert_{\infty}}{\Vert x \Vert_{\infty}} \leq \max_{x} \dfrac{\Vert Ax \Vert_2}{\Vert x \Vert_2}$$ – user17762 Jan 19 '13 at 6:01