6

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

dxdydz
  • 1,371

1 Answers1

8

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

PrincessEev
  • 43,815
Mark
  • 39,605
  • 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}|$? – dxdydz Feb 15 '19 at 20:23
  • 1
    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. – Mark Feb 15 '19 at 20:27
  • Excellent explanation! – user10101 Oct 27 '21 at 04:09