I am having trouble with the following problem:
Show that the vector norm $||x||_1$ gives the subordinate matrix norm: \begin{equation} ||A||_1 = \max_{1\leq j\leq n}\sum_{i=1}^n|a_{ij}| \end{equation}
I really do not have any starting point for this question. I though maybe we could use $||x||_1$ norm for the rows or columns of $A$ but I did not get anywhere with that.
Note: \begin{equation} ||A|| = \sup{||Au||: u\in \mathbb{R}^n, ||u||=1} \end{equation}
All help is greatly appreciated!
EDIT: This is what I have so far: \begin{align} ||A||_1 =& \sup_{||u||_1=1}||Au|| \\ =& \sup_{||u||_1=1}||\sum\limits_{i=1}^n|(Au)_i|\,|| \end{align}
Here is where I am having trouble. The maximum value depends on the entries in $A$. It just seems to make sense that we would pick the largest values in each row.
1.How do I finish the proof from here?
Let $A$ be a $m\times n$ matrix. Let us denote $$\gamma:=\max_{1\le j\le n}\sum_{i=1}^m |a_{ij}|$$ Then \begin{align} ||A||_1 =& \sup_{||u||_1=1}||Au||_{1} \\ =&\sup_{||u||_1=1}||v||_{1} \end{align} where $$v=\begin{bmatrix}A_{1*}u & A_{2*}u & \cdots & A_{m*}u \end{bmatrix}$$ where $A_{i*}$ is the $i$th row of $A$. Hence
\begin{align} \|v\|_{1}=&\sum_{k=1}^m |A_{k*}u|\\ \ =&\sum_{k=1}^m |\sum_{j=1}^n a_{kj}u_j|\\ \ \le& \sum_{k=1}^m \sum_{j=1}^n |a_{kj}||u_j|\ (\mbox{By triangle inequality})\\ \ \le& \left(\max_{1\le j\le n}\sum_{k=1}^m|a_{kj}|\right)\sum_{j=1}^{n}|u_j|=\gamma \|u\|_{1} \end{align}
So, $$\|A\|_{1}\le \gamma\tag{1}$$
Now, let $$k=\arg{\max_{1\le i\le m}}\sum_{j=1}^n |a_{ij}|$$ and let $e_k$ be the $n\times 1$ unit vector with $$(e_k)_{i}=\left\{\begin{array}{rl} 1 & \mbox{if}\ i=k\\ 0 & \mbox{else} \end{array} \right. $$ for $1\le i\le n$. Then $\|e_k\|_{1}=1$ and \begin{align} \|Ae_k\|_{1}=&\sum_{i=1}^m|a_{ik}|=\gamma\le \sup_{\|u\|_{1}=1}\|Au\|_{1}=\|A\|_{1}\tag{2}\\ \end{align} Hence, from $(1)$ and $(2)$, $$\|A\|_{1}=\gamma\hspace{0.6cm}\Box$$