6
$\begingroup$

I want to prove that the infinity matrix norm is maximum row sum norm. I've shown that for $\|x\|_{\infty}=1$ $$||Ax||_{\infty} = \max_{i}\left|\sum^n_{j=1}a_{ij}x_j \right| \leq \max_{i}\sum^{n}_{j=1} |a_{ij}|\|x\|_{\infty}= \max_{i}\sum^{n}_{j=1} |a_{ij}|.$$ Now I need to show that there exists vector $x$ with $\|x\|_{\infty}=1$ for which this inequality becomes equality. And I'm stuck here. How do I proceed? What is the correct $x$?

$\endgroup$

1 Answer 1

8
$\begingroup$

Suppose the maximum sum $\sum_{j=1}^n |a_{ij}|$ is gained in row number $i$. Then for each $j$ let $x_j=1$ if $a_{ij}\geq 0$ and $x_j=-1$ if $a_{ij}<0$. Then take $x=(x_1,...,x_n)$. That way for each $j$ we have $a_{ij}x_j=|a_{ij}|$ and hence for each row $k$ we get:

\begin{align*} \left|\sum_{j=1}^n a_{kj}x_j\right| &\leq \sum_{j=1}^n \left|a_{kj}x_j\right|\\ &=\sum_{j=1}^n \left|a_{kj}\right|\\ &\leq \sum_{j=1}^n \left|a_{ij}\right|\\ &=\left|\sum_{j=1}^n a_{ij}x_j \right| \end{align*}

Hence $\|Ax\|_\infty=\sum_{j=1}^n |a_{ij}|$.

$\endgroup$
3
  • $\begingroup$ Can you explain the last equality: $\sum_{j=1}^n |a_{ij}|=|\sum_{j=1}^n a_{ij}x_j|$ Shouldn't this be triangle inequality? And how does this imply that $||Ax||_\infty=\sum_{j=1}^n |a_{ij}|$? $\endgroup$
    – dxdydz
    Feb 15, 2019 at 20:23
  • 1
    $\begingroup$ Yes, in general there is an inequality. But in our case $a_{ij}x_j=|a_{ij}|$. So this means $|\sum_{j=1}^n a_{ij}x_j|=|\sum_{j=1}^n |a_{ij}||$ and because all the terms in the sum are non negative then it just equals to $\sum_{j=1}^n |a_{ij}|$. So we showed that for each $1\leq k\leq n$ we have $|\sum_{j=1}^n a_{kj}x_j|\leq |\sum_{j=1}^n a_{ij}x_j|$, hence $||Ax||_\infty=|\sum_{j=1}^n a_{ij}x_j|$ by definition. But the last expression equals to $\sum_{j=1}^n |a_{ij}|$ as we already know. So that's it. $\endgroup$
    – Mark
    Feb 15, 2019 at 20:27
  • $\begingroup$ Excellent explanation! $\endgroup$
    – user10101
    Oct 27, 2021 at 4:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .