[Math] Subordinate matrix norm of 1-norm

Question

Show that for the vector norm $$\|x\|_1=\sum_{i=1}^n |x_i|$$ the subordinate matrix norm is
$$
\|A\|_1=\max_{1\leq j\leq n} \sum_{i=1}^n |a_{ij}|
$$
I've managed to narrow it down doing the following:
$$
\|A\|_1=\sup_{\|u\|_1=1} \left\{\sum_{i=1}^n |(Au)_i|\right\} = \sup_{\|u\|_1=1} \left\{\sum_{i=1}^n \left|\sum_{j=1}^n a_{ij}u_j\right|\right\}
$$
Now intuitively I can see why the subordinate norm is what it is. I just can't come up with a mathematical way of proving it from here. I know $u_j=1$ when the sum in the sub. matrix norm is largest, however how do I prove that doing this makes the maximum equal to the supremum?
Thank you in advance.

Answer 1

You have $$ \sum_{i=1}^n|(Au)_i|=\sum_{i=1}^n\left|\sum_{j=1}^nA_{ij}u_j\right| \leq\sum_{i=1}^n\sum_{j=1}^n|A_{ij}|\,|u_j| =\sum_{j=1}^n|u_j|\sum_{i=1}^n|A_{ij}|\leq\|A\|_1\sum_{j=1}^n|u_j|=\|A\|_1. $$ So $$\tag{1} \sup_{\|u\|_1=1} \left\{\sum_{i=1}^n |(Au)_i|\right\}\leq\|A\|_1. $$ Now, if $\|A\|_1=\sum_{i=1}^n|A_{ik}|$, we can take $u$ the vector with all entries equal to zero with the exception of a $1$ in the $k^{\rm th}$ position to get $$ \sum_{i=1}^n|(Au)_i|=\sum_{i=1}^n\left|\sum_{j=1}^nA_{ij}u_j\right| =\sum_{i=1}^n\left|A_{ik}\right|=\|A\|_1, $$ So $$\tag{2} \sup_{\|u\|_1=1} \left\{\sum_{i=1}^n |(Au)_i|\right\}\geq\|A\|_1. $$ Combining $(1)$ and $(2)$, the equality is proven.