Submultiplicative matrix norm: Max Norm

Question

Various sources claim that a maximum norm $||A||_{max}=\max_{i,j}|a_{ij}|$ is not submultiplicative, i.e. $||AB||_{max}\not\leq||A||_{max}||B||_{max}$.

Where can I find what norm a,b satisfy $||AB||_{max}\leq||A||_{a}||B||_{b}$?

Answer 1

The inequality $\|AB\|_{\max} \leq \|A\|_{a}\|B\|_{b}$ for all $A$, $B$ can be achieved or destroyed just by rescaling the norms $\|\cdot\|_a$ and $\|\cdot\|_b$. Let's suppose that we're considering $d \times d$ matrices. If we just make sure that the two norms $\|\cdot\|_a$ and $\|\cdot\|_b$ are scaled so that both of them have the property $\|C\|_i \geq \sqrt{d}\|C\|_{max}$ for all $d \times d$ matrices $C$, then the desired inequality follows from the elementary inequality $\|AB\|_{\max} \leq d.\|A\|_{\max}\|B\|_{\max}$. Conversely, if the norms are rescaled so that both of them give norm $\frac{1}{2}$ to the identity matrix, then the inequality clearly cannot hold since $\|Id\|_{max}=1$. The fact that such rescalings exist follows from the fact that norms on a finite-dimensional space are pairwise equivalent.

The point of this is that there are a lot of norms on the space of matrices if we don't make any additional requirements on them. Is this the kind of answer you were looking for? Or do you want the two norms to have additional properties?

edited: there was a typo on the main inequality

Answer 2

The Hilbert-Schmidt norm, $||A||_F= (\sum_{i,j=1}^n a_{i,j}^2)^{1/2}$ is clearly always larger than $||A||_{max}$ and is also submultiplicative.

Hence, $||AB||_{max} \leq ||AB||_F \leq ||A||_F ||B||_F$