# Property for Norms of Matrices

I am having trouble with the following problem:

Show that the vector norm $||x||_1$ gives the subordinate matrix norm: $$||A||_1 = \max_{1\leq j\leq n}\sum_{i=1}^n|a_{ij}|$$

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: $$||A|| = \sup{||Au||: u\in \mathbb{R}^n, ||u||=1}$$

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?

• Do you know what you're supposed to do? Jul 26 '13 at 13:18
• Looks like a typical numerical analysis homework problem to me. Jul 26 '13 at 13:22
• There are two inequalities to prove. For $\leq$, use the triangular inequality on $\sum_{i} |(Ax)_i|=\sum_i |\sum_j a_{ij}x_j|$. For $\geq$, pick the good vector $x$ with only one nonzero coordinate. Jul 26 '13 at 14:23
• This certainly must have been asked before. Here's one instance: math.stackexchange.com/questions/441912/… Jul 29 '13 at 7:37

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
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$$