First, we should show that for $A\in \mathbb{R}^{m\times n}$: $\|Av\|_1 \le \|A\|_1 \|v\|_1$.

$$(1)\quad\|Av||_1=\sum_{i=1}^m|(Av)_i| \le \sum_{i=1}^m \sum_{j=1}^n|A_{i j}||v_j|=\sum_{j=1}^n (\sum_{i=1}^m |A_{ij}|)|v_j|\le \|A\|_1 \|v\|_1$$

Is that even correct? Because next, we are supposed to construct a vector such that $\|Av\|_1 = \|A\|_1 \|v\|_1$ for some fixed $A$.

Constructing a vector such that the first inequality in (1) becomes equal is simple (equal triangle inequality).

But the second inequality in (1) has me stumped. We can't possibly guarantee that all column sums of $A$ are equal, so how can I find that vector?

  • 1
    $\begingroup$ Your question is not clear... For what I understand, $A$ is given. But then, such a vector may not exist (if restricted to be nonzero), take for instance $A=2I$ where $I$ is the identity. $\endgroup$ – Surb Nov 17 at 13:20
  • $\begingroup$ @Surb I don't understand your example. When $A=2I$ then every vector is just scaled up by two, and the 1-norm of $A$ is also two, meaning that for every vector we have equality. $\endgroup$ – Ruben Kruepper Nov 17 at 14:47
  • $\begingroup$ my bad, I misread the question. Which definition of $\|A\|_1$ do you use? $\endgroup$ – Surb Nov 17 at 17:34
  • $\begingroup$ @Surb Take all column sums, then take the largest one. That's the norm. :) $\endgroup$ – Ruben Kruepper Nov 17 at 20:33
  • $\begingroup$ I see. it is late for me now, so I will answer tomorrow if nobody does before. But essentially, by homoegeneity you have $\|A\|_1 = \sup\{\|Av\|_1 \mid \|v\|=1\}$. As the unit ball induced by $\|\cdot \|_1$ is compact, the maximizer always exists and this is the vector you are looking for. $\endgroup$ – Surb Nov 17 at 20:56

From the discussion in comments, you define $$\| A \|_1 = \max\{\|c(A,j)\|_1 \mid j=1,\ldots,n\},$$ where $c(A,1),\ldots,c(A,n)$ are the columns of $A$. Now, let $k$ be such that $\|c(A,k)\|_1=\|A\|_1$ and let $e_k$ be the $k$-th vector of the canonical basis of $\Bbb R^n$, i.e. $(e_k)_i=0$ if $i\neq k$ and $(e_k)_k = 1$. Then, we have $\|e_k\|_1=1$ and $$\|Ae_k\|_1 = \|c(A,k)\|_1=\|A\|_1=\|A\|_1\|e_k\|_1.$$

Side note: In conclusion you have then shown that $$\|A\|_1=\max_{x\neq 0}\frac{\|Ax\|_1}{\|x\|_1}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.