I have a matrix $A \in \mathbb{R}^{n \times n}$ and would like to know about the relationship between the $\| A \|_\infty$ (i.e., the maximum element of the matrix) and the operator-induced norm $\| A \|$.
I know that the following upper-bound holds (from Matrix Norm Inequality): $ \| A \|_\infty \leq \sqrt{n} \| A \| $?
But, I am trying to find a lower-bound? (Would the lower-bound possibly be comprised of the minimum singular value times some factor of $n$?)
Also, I need this lower bound to have a norm that has the sub-multiplicative property: given square matrices $A,B \Rightarrow \| A B \|_{\infty} \geq \| A \|_p \| B \|_p $
But, is there an appropriate norm/$p$ that suits this?
Best Answer
Let $A=(a_{ij})$ and $x=(x_i)^t\in\Bbb R^n$. Then
$$\|Ax\|=\sqrt{\sum_i \left(\sum_j a_{ij}x_j\right)^2}\le $$
$$\mbox{(by Cauchy-Schwarz inequality)}$$
$$\sqrt{\sum_i \left(\sum_j a_{ij}^2\right)\left(\sum_j x_{j}^2\right)}=$$
$$\sqrt{\sum_i \left(\sum_j a_{ij}^2\right)}\|x\|\le$$
$$\sqrt{\sum_i \left(\sum_j \|A\|_\infty^2\right)}\|x\|=$$
$$\sqrt{n^2\|A\|_\infty^2}\|x\|=$$
$$n\|A\|_\infty\|x\|.$$
So $$\| A \|/n \le \| A \|_\infty.$$
This bound is tight, for instance, for $A=J$, where $J$ is the $n\times n$ matrix of all ones. Indeed, in this case if $x=(x_i)^t$ then $$\|Ax\|=\sqrt{n}\left|\sum x_i\right|\le$$ $$\mbox{(by the inequality between arythetic and quadratic means)}$$ $$n\sqrt{\sum x_i^2}=n\|x\|.$$ On the other hand, this inequality is tight because $\|A\bar1\|=n\|\bar1\|$, where $\bar 1$ is the n-dimensional vector of all ones.