1
$\begingroup$

Let $f,g:\mathbb{R}^{n\times n}\to \mathbb{R}$ be given by

$$\begin{aligned} f(A) &= \max_{i=1,...,n}i\cdot \sum_{j=1}^{n}|a_{ij}|,\\ g(A) &= n\cdot \max_{i,j=1,...,n}|a_{ij}| \end{aligned}$$

Is g submultiplicative? Are $f,g$ compatible with $\| \cdot \|_1$, given by $\|x\|_1 = \sum_{i=1}^{n}|x_i|$?

How does one go about showing whether these are true or false? Every counterexample I try out seems to fail, even though I know that $g$ is just a variant of the so-called maximum-norm (which is not submultiplicative), still, that doesn't seem to help much.

Thank you very much in advance, I would very much appreciate help with this.

$\endgroup$
2
  • $\begingroup$ I think in the definition of $f$, the $max$ should be taken only over $i$, because you use the $j$ as the summation index again, right? $\endgroup$ Commented Jan 31, 2020 at 17:25
  • $\begingroup$ @StefanEgger Yes, that is true, thanks for pointing that out. $\endgroup$
    – user731634
    Commented Jan 31, 2020 at 17:58

1 Answer 1

0
$\begingroup$

In fact, $g$ is submultiplicative. For $a,b \in \Bbb R^n$, note that $$ |a^Tb| \leq \|a\|_\infty \cdot \|b\|_1 \leq n \cdot \|a\|_\infty \cdot \|b\|_\infty. $$ Now, if $a_i$ is the $i$th row of $A$ and $b_j$ is the $j$th column of $B$, we have $$ n \cdot |(AB)_{i,j}| = n \cdot |a_i^T b_j| \leq (n \cdot \|a_i\|_\infty) \cdot (n \cdot \|b_j\|_\infty) \leq g(A)\cdot g(B). $$ Conclude that we indeed have $g(AB) \leq g(A)g(B)$.


As for compatibility: it should be easy to find a counterexample for $g$. I suspect that $f$ will be compatible; it is probably useful to note that $f(A) = \|DA\|_\infty$. Here, $\|\cdot \|_\infty$ denotes the operator norm induced by the $\infty$-norm, which is to say that $\|M\|_\infty$ is the maximal absolute row-sum. $D$ is the diagonal matrix matrix $D = \operatorname{diag}(1,2,\dots,n)$.

$\endgroup$
1
  • $\begingroup$ Thank you, actually I was aware of the second part of your answer from another question of mine but I'm still struggling with putting that to use since this matrix norm is not induced by the $||\,.||_1$ vector norm. $\endgroup$
    – user731634
    Commented Jan 31, 2020 at 18:02

You must log in to answer this question.