Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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}$.

share|improve this answer
    
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
    
I apologize, it wasn't immediately obvious. Proofs are my Kryptonite. I just want to be sure that I have this right: the same inequalities for a vector p norm can be used for a matrix p norm? Isn't the definition of the vector p norm different from the matrix p norm? I'm guessing that the fact that the matrix norm is induced by the vector norm takes care of that, but I just want to be sure. –  rioneye Jan 19 '13 at 1:38
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.