# Infinity matrix norm is maximum row sum norm

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

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}|$$.
• 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}|$? Feb 15, 2019 at 20:23
• 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.