Why is the matrix norm $||A||_1$ maximum absolute column sum of the matrix?

Solution 1:

Let's denote the columns of $A$ by $A_1,\, \dotsc,\, A_n$. Then for every $x \in \mathbb{R}^n$, we have

$$\begin{align} \lVert Ax \rVert_1 &= \left\lVert\sum_{\nu=1}^n x_\nu\cdot A_\nu \right\rVert_1\\ &\leqslant \sum_{\nu=1}^n \lVert x_\nu\cdot A_\nu\rVert_1\\ &= \sum_{\nu=1}^n \lvert x_\nu\rvert\cdot\lVert A_\nu\rVert_1\\ &\leqslant \max \left\{\lVert A_\nu\rVert_1 : 1 \leqslant \nu \leqslant n\right\} \left(\sum_{\nu=1}^n \lvert x_\nu\rvert\right)\\ &= \max \left\{\lVert A_\nu\rVert_1 : 1 \leqslant \nu \leqslant n\right\}\cdot \lVert x\rVert_1. \end{align}$$

That shows that

$$\lVert A\rVert_1 \leqslant \max \left\{\lVert A_\nu\rVert_1 : 1 \leqslant \nu \leqslant n\right\},$$

and choosing $x = e_m$, where $m$ is the index where the absolute column sum has its maximum shows the converse inequality, hence equality.