3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Do you know what you're supposed to do? $\endgroup$
    – Git Gud
    Jul 26 '13 at 13:18
  • 4
    $\begingroup$ Looks like a typical numerical analysis homework problem to me. $\endgroup$ Jul 26 '13 at 13:22
  • 2
    $\begingroup$ 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. $\endgroup$
    – Julien
    Jul 26 '13 at 14:23
  • $\begingroup$ This certainly must have been asked before. Here's one instance: math.stackexchange.com/questions/441912/… $\endgroup$
    – Tunococ
    Jul 29 '13 at 7:37
5
+100
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.