Matrix Norm Proofs: Dropping the "max" term and denominator

Question

To prove that $||A||_{\infty}≤\sqrt{n}||A||_{2}$, this math.exchange proof does the following:

$$||A(x)||_{\infty}≤ ||A(x)||_{2}≤||A||_{2}||x||_{2}≤||A||_{2}\sqrt{n}||x||_{\infty}$$

Given the definition of matrix norms $$\|A\|_p = \max_{x\neq0}\frac{\|Ax\|_p}{\|x\|_{p}},$$ and if this proof is sufficient, why is it valid to drop the $\max_{x\neq{0}}$ in the proof? Similarly, with dropping the denominators of $||x||_{2}$ and $||x||_{\infty}$?

Answer 1

If you have $$ \left\| Ax\right\|_\infty \le \sqrt{n}\left\| A\right\|_2 \left\| x\right\|_\infty,$$ then for every $x\neq 0$, $$ \frac{\left\| Ax\right\|_\infty}{\left\| x\right\|_\infty } \le \sqrt{n}\left\| A\right\|_2.$$ Since the right hand side of the last inequality doesn't depend on $x$, you can take a special $x=x_0$ such that $$ \frac{\left\| Ax_0\right\|_\infty}{\left\| x_0\right\|_\infty } = \max_{x\neq 0} \frac{\left\| Ax\right\|_\infty}{\left\| x\right\|_\infty }.$$ Using this $x_0$, you have $$ \frac{\left\| Ax_0\right\|_\infty}{\left\| x_0\right\|_\infty } = \max_{x\neq 0} \frac{\left\| Ax\right\|_\infty}{\left\| x\right\|_\infty } = \left\| A\right\|_\infty \le \sqrt{n}\left\| A\right\|_2.$$

Answer 2

This proves that for any $x\neq 0$, $$||Ax||_{\infty}\leq ||A||_2\sqrt{n}||x||_{\infty}$$

Thus, for any $x\neq 0$, $$\frac{||Ax||_{\infty}}{||x||_{\infty}}\leq\sqrt{n}||A||_2$$

This implies that $$\max_{x\neq 0}\frac{||Ax||_{\infty}}{||x||_{\infty}}\leq\sqrt{n}||A||_2$$

Answer 3

By definition of the maximum, for all $x\neq0$ we have $\frac{||Ax||_2}{||x||_2}\leq\max_{x\neq0}\frac{\|Ax\|_2}{\|x\|_{2}}$, from which it is immediate that $$||Ax||_2=||x||_2\cdot\frac{||Ax||_2}{||x||_2}\leq||x||_2\cdot{\max_{x\neq0}}\frac{||Ax||_2}{||x||_2}=||x||_2\cdot||A||_2.$$ Note that by 'dropping' the $\max_{x\neq0}$ term we get an inequality.