Subordinate matrix norm of 1-norm 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.
 A: 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. 
A: Let us carry on $\sum_{i=1}^{n}\left|\sum_{j=1}^{n}a_{ij}u_j\right| \leq \sum_{i=1}^{n}\sum_{j=1}^{n}\left|a_{ij}u_j\right|$ 
Let us inverse the summation order:
$\sum_{i=1}^{n}\sum_{j=1}^{n}\left|a_{ij}u_j\right| =\sum_{j=1}^{n}\sum_{i=1}^{n}\left|a_{ij}u_j\right| = \sum_{j=1}^{n}\left|u_j\right|\sum_{i=1}^{n}\left|a_{ij}\right| \leq \sum_{j=1}^{n}\left|u_j\right|\bigg(\max_{j=1,...,n}\big(\sum_{i=1}^{n}\left|a_{ij}\right|\big)\bigg)$
Because $||u||_1 = 1$, we have that:
$ \sum_{j=1}^{n}\left|u_j\right|\bigg(\max_{j=1,...,n}\big(\sum_{i=1}^{n}\left|a_{ij}\right|\big)\bigg)=\max_{j=1,...,n}\big(\sum_{i=1}^{n}\left|a_{ij}\right|\big)$
Therefore, we have proved throughout these inequalities that $||A||_1 \leq \max_{j=1,...,n}\big(\sum_{i=1}^{n}\left|a_{ij}\right|\big)$. 
Let $j_\star$ the column index such that $\max_{j=1,...,n}\big(\sum_{i=1}^{n}\left|a_{ij}\right|\big) = \sum_i^n |a_{ij_\star}|$. Then define the vector $x_\star = (0,0,\dots,1,0,\dots 0) $ where $1$ is at the $j_\star$-th position.
Then $||Ax_\star||_1 = \sum_i^n |a_{ij_\star}| = \max_{j=1,...,n}\big(\sum_{i=1}^{n}\left|a_{ij}\right|\big)$.
Now remember we have the following lemma (left as an exercise):

Lemma: If $\sup_x A(x) \leq c$ and there exists $x_\star$ such that $A(x_\star) = c$, then $\sup_x A(x) = c$.

Hence $||A||_1 = \max_{j=1,...,n}\big(\sum_{i=1}^{n}\left|a_{ij}\right|\big)$
