Induced Matrix Norms

Question

I have already proved $\|A\|_\infty \le \|A\|_2$. And I have that

$\|A\| = \sup_{x\ne 0}\frac{\|Ax\|}{\|x\|} $

However I am having difficulty proving that $\|A\|_\infty\le \sqrt{n}\|A\|_2$.

Answer 1

Before we start this proof we need to know that $\|x\|_\infty \le \|x\|_2 \le \sqrt{n}\|x\|_\infty,$ which is a different proof altogether:

Recall that $\|x\|_\infty = max\{|x_1|,|x_2|,\ldots,|x_n|\}$ and that $\|x\|_2 = (|x_1|^2 + |x_2|^2 + \cdots + |x_n|^2)^{1/2}.$ Without loss of generality let $|x_i|$ be the maximum element such that $\|x\|_\infty = |x_i|$. It should be clear that $|x_i| \le (|x_1|^2 + |x_2|^2 + \cdots + |x_i|^2 + \cdots +|x_n|^2)^{1/2},$ you can square both sides to quickly see that it is true. Thus $\|x\|_\infty \le \|x\|_2.$

To show the other side we will show that $\frac{\|x\|_2}{\sqrt{n}} \le \|x\|_\infty.$ $$ \frac{\|x\|_2}{\sqrt{n}} = \sqrt{\frac{1}{n}\left(|x_1|^2 + |x_2|^2 + \cdots + |x_n|^2 \right)}. $$ $ \frac{1}{n}\left(|x_1|^2 + |x_2|^2 + \cdots + |x_n|^2 \right) $ is the average of the squares, denoted $x_{ave}^2.$ Then $\sqrt{x_{ave}^2} = x_{ave}$.

This amount is certainly less than or equal to $x_{max}$, which shows then that $$ \frac{\|x\|_2}{\sqrt{n}} = \sqrt{\frac{1}{n}\left(|x_1|^2 + |x_2|^2 + \cdots + |x_n|^2 \right)} = x_{ave} \le x_{max} = \|x\|_\infty. $$

Now we have shown $\frac{\|x\|_2}{\sqrt{n}} \le \|x\|_\infty, \Rightarrow \|x\|_2 \le \sqrt{n}\|x\|_\infty.$

With this tool we can now prove $\|A\|_{\infty} \le \sqrt{n}\|A\|_2,$ we will show that $\frac{1}{\sqrt{n}}\|A\|_{\infty} \le \|A\|_2.$

Observe that we can write: $$\frac{1}{\sqrt{n}}\|A\|_\infty = sup_{x\,\in\,X}\frac{\|Ax\|_\infty}{\sqrt{n}\|x\|_\infty} \le sup_{x\,\in\,X}\frac{\|Ax\|_\infty}{\|x\|_2} \le sup_{x\,\in\,X}\frac{\|Ax\|_2}{\|x\|_2} = \|A\|_2.$$

Which then tells us that $\|A\|_{\infty} \le \sqrt{n}\|A\|_2,$ as we had hoped.