How to proof $\lVert AB\rVert_{\infty} \le \lVert A\rVert_{\infty} \lVert B\rVert_{\infty}$

Question

I want to know how to prove $\lVert AB\rVert_{\infty} \le \lVert A\rVert_{\infty} \lVert B\rVert_{\infty}$ for any two matrices $A, B \in \mathbb{C^{n\times n}}$.

I know that $\lVert AB\rVert \le \lVert A\rVert \lVert B\rVert$. It was one of the facts in my lectures and I am not sure how to prove it. Does the proof go from this fact?

And also $\lVert A\rVert_{\infty}=\max\limits_{1 \le i \le m}\sum_{j=1}^n\left\lvert a_{ij} \right\rvert$.

Thanks.

Answer 1

The correct formula is as in the wiki article on matrix norms: $$ \|A\|_\infty:=\max_{1\le i\le n}\sum_{1\le j\le n}|A_{ij}|\ . $$ Taking this as definition, here is a proof for the needed inequality.

The simplest way is to observe that with the above definition we have

Claim: $$ \|A\|_\infty \overset !=\max_{|x|_\infty=1}|Ax|_\infty =\max_{x\ne 0}\frac{|Ax|_\infty}{|x|_\infty}\ . $$ Here, $x$ is from $\Bbb C^n$ and its corresponding norm is $|x|_\infty$ if the maximal value among the modulus of its components.

Proof of the claim: Indeed, each component in $Ax$ is of the shape $\sum_j A_{ij}x_j$ and we have $$ \left|\sum_j A_{ij}x_j\right| \le \sum_j |A_{ij}|\;|x_j| \le \sum_j |A_{ij}|\;|x|_\infty $$ so after taking $\max_i$ we get $$ |Ax|_\infty =\max_i \left|\sum_j A_{ij}x_j\right| \le \underbrace{\max_i\left(\sum_j |A_{ij}|\right)}_{=:\|A\|_\infty}\;|x|_\infty\ . $$ And this gives one inequality in the relation marked with the $(!)$ above, since in $\displaystyle \|A\|_\infty\ge \frac{|Ax|_\infty}{|x|_\infty}$ we take the maximum w.r.t. $x\ne 0$. On the other hand, this inequality holds also in the converse direction, as follows. Let $I$ be the index realizing the maximum in the definition of $\|A\|_\infty$. Take the special $x$ vector with components of modulus one, so that for all $j$ we have $A_{Ij}=|A_{Ij}|$. (We have choices only for the zero entries in this $I$.th line.) Then it is clear that $|x|_\infty=1$ and $$ |Ax|_\infty\ge|\ (Ax)_I\ | =\left|\sum_j A_{Ij}x_j\right|=\left|\ \sum_j |A_{Ij}|\ \right|=\sum_j |A_{Ij}|=\|A\|_\infty\ , $$ giving the other inequality.

$\square$

---

Now we immediately get the "norm inequality" for the map $A\to\|A\|_\infty$: $$ \|AB\|_\infty = \max_{x\ne 0}\frac{|ABx|_\infty}{|x|_\infty} \le \max_{x\ne 0}\frac{\|A\|_\infty\;|Bx|_\infty}{|x|_\infty} = \|A\|_\infty\max_{x\ne 0}\frac{\;|Bx|_\infty}{|x|_\infty} = \|A\|_\infty\;\|B\|_\infty\ . $$ $\square$

---

Note: This is the "structural proof", and applies to all canonically constructed norms for maps between two normed spaces. Take in general the maximum of all quotients of the shape $|Ax|$ divided by $|x|$ for $x\ne 0$, where $|x|$ is the norm of $x$ computed on the source space, and $|Ax|$ is a norm of $Ax$, possibly an other one, computed on the target space. Since also in our case two norms are involved, the notation of the resulted norm on the space of linear maps has two indices, in our case this would be $\|A\|_{\infty,\infty}$...

Combining the two arguments from above, one can of course manufacture a direct one-usage proof for the needed inequality, but structurally it is better to see the general setting.