4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Your last inequality can't always hold. Just take $A,B\not= 0$ so that $AB=0$. $\endgroup$
    – xavierm02
    Commented Aug 5, 2017 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
    Commented Aug 5, 2017 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
    Commented Aug 5, 2017 at 22:38

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .