Proving that the norm $n \|A\|_{l_\infty}$ is a matrix norm.

Question

I'm trying to prove that the norm $\| \circ \| = n \|A\|_{l_\infty}$ is a matrix norm. Reminder that the $l_\infty$-norm of a matrix $A \in \mathbb{R}^{n \times n }$ is defined as: \begin{equation} \|A\|_{l_\infty} = \max \left\{\left|a_{i j}\right|: i, j=1,2, \ldots, n\right\} \end{equation}

What I need to prove is that the sub-multiplicative property holds (the other four conditions can be proven fairly simply), that is, for every $A,B \in \mathbb{R}^{n \times n}$ the following is true: \begin{align} \|A B\| &\leq \|A\| \|B\| \Longleftrightarrow \\ n \|A B\|_{l_\infty} &\leq \left(n\|A\|_{l_\infty} \right) \left(n|B\|_{l_\infty}\right) \end{align}

My effort so far: Knowing that $(AB)_{i j} = \sum_k^n a_{i k} b_{k j}$, \begin{align*} \|AB\| &= n \|AB\|_{l_\infty} = n \max \left\{ \left| \sum_k^n a_{i k} b_{k j} \right|: i,j = 1, \ldots, n \right\} \leq n \max \left\{ \sum_k^n \left| a_{i k} b_{k j} \right|: i,j = 1, \ldots, n \right\} \\ &= n \max \left\{ \sum_k^n \left| a_{i k} | |b_{k j} \right|: i,j = 1, \ldots, n \right\} \leq n \max \left\{ \sum_k^n \left| a_{i k} \right|: i = 1, \ldots, n \right\} \max \left\{ \sum_k^n \left| b_{k j} \right|: j = 1, \ldots, n \right\} \end{align*}

Don't know if the last inequality holds, I do not know how to proceed.

Answer 1

Your last inequality is slightly wrong, but you were on the right path. For what follows, I'd suggest to first drop the $\max$s and then put them back on later. Not necessary but should make things clearer for you.

Hint: use Cauchy-Schwarz in $\mathbb{R}^n$ on the vectors $a := (n a_{i,1}, \dots, n a_{i,n})$ and $b := (b_{1,j}, \dots, b_{n,j})$, then try to make the connection between $\|a\|_2$ and $\|b\|_2$ and what you actually want.

Let me know if you need more hints or if you want me to write the full answer by the way.

Full answer:

By Cauchy-Schwarz, we have: $$\sum_{k=1}^n \left|na_{i k} \right| \left|b_{k j} \right| \leq \left(\sum_{k=1}^n \left|na_{i k}\right|^2\right)^\frac{1}{2} \left(\sum_{l=1}^n \left|b_{l j} \right|^2\right)^\frac{1}{2} = n \left(\sum_{k=1}^n \left|a_{i k}\right|^2\right)^\frac{1}{2} \left(\sum_{l=1}^n \left|b_{l j} \right|^2\right)^\frac{1}{2}$$

But, for a vector $x =: (x_1, \dots, x_n) \in \mathbb{R}^n$: $$\left(\sum_{k=1}^n \left|x_k \right|^2\right)^\frac{1}{2} \leq \left(\sum_{k=1}^n \|x \|_\infty^2\right)^\frac{1}{2} = \left(n\|x\|_\infty^2\right)^\frac{1}{2} = \sqrt{n}\|x\|_\infty$$

Therefore: $$\sum_{k=1}^n \left|na_{i k} \right| \left|b_{k j} \right| \leq n \cdot \sqrt{n} \max_k(|a_{ik}|) \cdot \sqrt{n} \max_k(|b_{lj}|) = n^2 \max_k(|a_{ik}|)\max_l(|b_{lj}|)$$

By taking the $\max$ over all $(i,j)$s on each side, we can conclude: $$\begin{split} \max_{i,j} \left(\sum_{k=1}^n \left|na_{i k} \right| \left|b_{k j} \right|\right) &\leq n^2 \max_{i,j}\left(\max_k(|a_{ik}|)\max_l(|b_{lj}|)\right)\\ &\leq n^2 \max_{i}\left(\max_k(|a_{ik}|)\right) \max_{j}\left(\max_l(|b_{lj}|)\right)\\ &\leq \left(n\|A\|_{l_\infty}\right)\left(n\|B\|_{l_\infty}\right)\end{split}$$ This provides the desired result with what you've already done.

Answer 2

The key thing is that the leading $n$ coefficient is needed to make $|| \cdot ||_\infty$ into a matrix norm. You don't need the coefficient to show any of the normed vector space axioms—$\mathbb{R}^n$ is a [erfectly fine normed vector space with the standard $\infty$-norm.

An illustrative example: Let $A = B = \begin{pmatrix} 1 & 1 \\ 1 & 1 \\ \end{pmatrix}$. Then $AB = \begin{pmatrix} 2 & 2 \\ 2 & 2 \\ \end{pmatrix}$. So $||A||_\infty = ||B||_\infty = 1$ and $||AB||_\infty = 2$, but $2 \not \leq 1 \cdot 1$.

The bound you need to prove sub-multiplicativity is actually pretty crude. After you use the triangle inequality to obtain $$ n ||AB||_\infty \leq n \max_{i,j \in 1 \ldots n} \left\{ \sum_k^n |a_{ik}| |b_{kj}| \right\} $$ you can conclude almost immediately with one more key step. This is the part where you can see how the factor of $n$ is needed.