How to prove that 2-norm of matrix A is <= infinite norm of matrix A Now a bit of a disclaimer, its been two years since I last took a math class, so I have little to no memory of how to construct or go about formulating proofs. My tutor unfortunately is very and excruciatingly slow at figuring them out and this one the tutor cannot seem to solve.
What I was taught is to start with "What do we want?" and "What do we know?"
What we want:
$||A||_2 \leq \sqrt{n}||A||_\infty$
What we know:
$||A||_2^2$ = $\lambda _\max(A^tA)$
$\sqrt{n}||A||_\infty = \sqrt{n} * max_i | \Sigma a_{ij} y_j |$ Where j= $1 \dots n$. Otherwise the maximum absolute row sum.
Thus:
$\sqrt{n}^2||A||_\infty^2 = n * max_i | \Sigma a_{ij} y_j |^2$ Where j= $1 \dots n$.
Or max row sum squared times n.
I feel like that the square of the max times n is likely going to be bigger than the largest positive eigenvalue of A, but I have no means of showing/knowing this and nothing in the notes indicates how to find the bounds other than maybe Banach-Lemma but I think that's only if A is invertible no? And I don't think that's given.
Was a homework question, but I'm way past due anyways and just working on it to understand it/prepare for the first mid term.
 A: 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.
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.
$$

