[Math] How to prove that 2-norm of matrix A is <= infinite norm of matrix A

matricesnormed-spacesnumerical methods

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.

Best Answer

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:

  1. 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".
  2. 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$.
  3. 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. $$
Related Question