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.
Best Answer
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.