How does this step occur in the proof?

Question

I was looking at the proof for the 1-Norm of a matrix.

$A$ is any $m x n$ matrix and $||A||_1$ is the maximum column sum of $A$.

The proof goes like this:

Write $A$ in terms of its columns.

$A=[ a_1 | ... | a_n ]$, where each $a_j$ is an $m-$ vector. Consider the $1-$norm unit ball in $\mathbb{C}^n$ i.e. the set $\{ x \in \mathbb{C}^n : \sum_{j=1}^{n}|x_j| \leq 1 \}$.

Any vector $Ax$ in the image of this set satisfies

$||Ax||_1 = ||\sum_{j=1}^{n} x_j a_j ||_1 \leq \sum_{j=1}^{n} |x_j| ||a_j||_1 \leq \max_{1 \leq j \leq n} ||a_j||_1$.

I don’t understand how we achieved the last term, from the second last term.

Because we have $\sum_{j=1}^{n}|x_j| \leq 1$ I feel we should have, $\sum_{j=1}^{n} |x_j|.||a_j||_1 \leq \sum_{j=1}^{n} ||a_j||_1 \leq n.max_{1 \leq j \leq n} ||a_j||_1$. Where am I thinking wrong? If you could simplify the steps somehow, it’d be easier for me to see.

Answer 1

In fact, the inequality you doubt is correct.

For, $$ \sum_{j=1}^n |x_j| \|a_j\| \le \sum_{j=1}^n |x_j| \max_l \|a_l\| $$ (since each $\|a_j\| \le \max_l \|a_l\|$), and hence $$ \sum_{j=1}^n |x_j| \|a_j\| \le \max_l \|a_l\| \overbrace{\sum_{j=1}^n |x_j|}^{\le1}. $$