How to prove that 2-norm of matrix A is <= infinite norm of matrix A
The matrix $p$-norm is the operator norm: $$ \|A\|_p=\max_{x\neq 0}\frac{\|Ax\|_p}{\|x\|_p}. \tag{1} $$ The fact that $$\tag{2} \|A\|_2=\rho(A^*A)\quad\text{and}\quad\|A\|_{\infty}=\max_i\sum_j|a_{ij}| $$ is just the consequence of (1). The $2$-norm and $\infty$-norm satisfy $$\tag{3} \|x\|_{\infty}\leq\|x\|_2\leq\sqrt{n}\|x\|_{\infty} $$ for any $n$-vector $x$ and the fact that $\|A\|_2\leq\sqrt{n}\|A\|_{\infty}$ follows by plugging (3) to (1): $$ \|A\|_2=\max_{x\neq 0}\frac{\|Ax\|_2}{\|x\|_2}\leq \max_{x\neq 0}\frac{\sqrt{n}\|Ax\|_\infty}{\|x\|_2} \leq \max_{x\neq 0}\frac{\sqrt{n}\|Ax\|_\infty}{\|x\|_{\infty}}=\sqrt{n}\|A\|_{\infty}. $$
Assuming that you know nothing about (1) and take (2) as the definitions (such an approach in a class is a bit odd because it makes showing a lot of things quite complicated), you can proceed as follows:
- You show that the matrix $\infty$-norm is consistent with the vector $\infty$-norm, that is, $$\tag{4}\|Ax\|_\infty\leq\|A\|_\infty\|x\|_\infty$$ holds for all vectors $x$. You can see that this is a trivial consequence of (1) but since you do not know about (1) you need to do it "by hand".
- From (4), you have that $\|A\|_2^2=\rho(A^TA)\leq\|A^TA\|_\infty$. Since there is an eigenvector $x$ and an eigenvalue $\lambda$ of $A^TA$ such that $\lambda=\rho(A^TA)$ (yes, all eigenvalues of $A^TA$ are nonnegative but that is not important here), $A^TAx=\lambda x$ gives us that $\|\lambda x\|_{\infty}=\|A^TAx\|_\infty$ and hence $$ \lambda\|x\|_\infty=\|A^TAx\|_\infty\stackrel{(4)}\leq\|A^TA\|_\infty\|x\|_\infty, $$ which by cancelling the $\|x\|_\infty$ gives $\rho(A^TA)=\lambda\leq\|A^TA\|_\infty$.
- Finally, one must show that $\|A^TA\|_\infty\leq n\|A\|_\infty^2$. This is easy: $$ \begin{split} \|A^TA\|_\infty&=\max_i\sum_j|(A^TA)_{ij}| =\max_i\sum_j\left|\sum_ka_{ik}a_{kj}\right| \leq \max_i\sum_j\sum_k\left|a_{ik}a_{kj}\right| \\& \leq\color{red}{\max_{i,j}|a_{ij}|} \color{blue}{\max_i\sum_j\sum_k\left|a_{ik}\right|}. \end{split} $$ In the last inequality, we bounded $|a_{kj}|$ by the maximum over the absolute values of all entries in $A$ (which is clearly OK). Now the red term can be bounded from above by $\|A\|_{\infty}$, while the blue term equals $n\|A\|_\infty$ (notice the terms in the sum over $j$ no longer depend on $j$). Hence, indeed, $\|A^TA\|_\infty\leq n\|A\|_\infty^2$ which together with the result of Item 2 gives $$ \|A\|_2^2=\rho(A^TA)\leq\|A^TA\|_\infty\leq n\|A\|_\infty^2. $$
I think got it now.
Starting from the top:
Let A be some square n by n matrix.
Let $\vec x = (x_1, x_2, ..., x_n)^T$ where $x \in \mathbb R$ and $n \in \mathbb N^+$
We want to prove that $||A||_2 \le \sqrt{n}||A||_\infty$
Now we know that $||A||_p \equiv ||A\vec x||_p / ||\vec x||_p$
Then the inequality becomes: $||A\vec x||_2 / ||\vec x||_2 \le \sqrt{n}||A\vec x||_\infty / ||\vec x||_\infty$
So lets look at the top:
$||A\vec x||_2 \le \sqrt{n}||A\vec x||_\infty $
Screw root signs:
$(||A\vec x||_2 \le \sqrt{n}||A\vec x||_\infty)^2 $
$||A\vec x||^2_2 \le n||A\vec x||^2_\infty $
Let $A\vec x = \vec b$ since a matrix times a vector is a vector.
We also know that:
$||\vec b||_2 \equiv \sqrt {\Sigma (x^2_1 + x^2_2 + ... x^2_n)}$
Thus $||\vec b||^2_2 \equiv \Sigma (x^2_1 + x^2_2 + ... x^2_n)$
While,
$||\vec b||_\infty \equiv $ $\max_{1\le k\le n}$ $ |x_k|$
Giving us:
$\Sigma (x^2_1 + x^2_2 + ... x^2_n) \le $ $n\max_{1\le k\le n}$ $ |x_k|^2$
Which is clearly true because the sum of all the elements squared of vector x is never going to be larger than the maximum element squared summed n times.
So now for the bottom, my professor had written it a little strangely that
$||\vec x||_2 \ge ||\vec x||_\infty$
Which is true but I got confused as to "how did the inequality get reversed? Because on the board it looked more like:
$ ||A\vec x||_2 \le ||A\vec x||_\infty \over ||\vec x||_2 \ge ||\vec x||_\infty$
Sans the division line because its just me trying to show how it looked through MathJax. C'est le vie.
But knowing that $||\vec x||_2 \ge ||\vec x||_\infty$ is true, then we know by properties of inequalities that this:
$1 \over ||\vec x||_2$ $\le$ $1 \over ||\vec x||_\infty$
Is where the sign switch happens!
Since $||\vec x||_2 \ge ||\vec x||_\infty$ is true and that the RHS is likely larger or equal than the LHS, that when both sides are divided by 1 that the LHS becomes the $ smaller$ number!
Therefore $||A||_2 \le \sqrt{n}||A||_\infty$ is true. QED.