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?

  • $\begingroup$ Your last inequality can't always hold. Just take $A,B\not= 0$ so that $AB=0$. $\endgroup$ – xavierm02 Aug 5 '17 at 22:16
  • $\begingroup$ @xavierm02 thank you for your reply! are there any lower bounds for $\| AB \|_\infty$ that can be written explicitly in terms of some function of $A$ and the $\| B\|$? $\endgroup$ – user2457324 Aug 5 '17 at 22:19
  • $\begingroup$ Let me rephrase your question: Is there some $f$ so that $\|AB\|_\infty \ge f(A,\|B\|)$? Suppose that there are some $A,B$ so that $f(A,\|B\|)\not=0$ and $A$ is not invertible. Then we can find some $B'$ so that $AB'=0$ and $\|B'\|=\|B\|$ so that $0=\|AB'\|_\infty\ge f(A,\|B'\|)=f(A,\|B\|)$. Absurd. So a such $f$ can only be non-zero when $A$ is invertible. I guess you could take $f(A,\|B\|)=\inf_{\|B'\|=\|B\|}\|AB'\|_\infty$, i.e., since you can't know which $B$ was used because you only have its norm, you consider the worst possible case. $\endgroup$ – xavierm02 Aug 5 '17 at 22:38

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\|=$$



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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.