I am studying matrix norms. I have read that $\|A\|_{\infty}$ is the largest row sum of absolute value and $\|A\|_{1}$ is the highest column sum of absolute values of the matrix $A$. However, I am not able to prove this. Are there any proof of these statements? Please help and thanks for your time.

Edit: Where $\|A\|_{\infty}$ is the matrix norm induced by the vector norm $\|x\|_{\infty}$.

  • $\begingroup$ You are talking about definition, why you want to prove it? $\endgroup$
    – CosimoDS
    Jul 12 '13 at 9:37
  • $\begingroup$ This sounds like a good exercise. You might want to first establish that the suspected value is an upper bound, then show that the value can be achieved. $\endgroup$
    – Tunococ
    Jul 12 '13 at 9:37
  • $\begingroup$ @Tunococ I have studied operator norm. I want to apply same definition to evaluate matrix norms but I am not able to do so properly. Thanks for your reply. $\endgroup$
    – mathscrazy
    Jul 12 '13 at 9:40
  • $\begingroup$ This doesn't answer my question. $\endgroup$
    – mathscrazy
    Jul 12 '13 at 9:40
  • $\begingroup$ @mathscrazy CosimoDS does answer your question, as $\|A\|_\infty=\max_i\sum_j|a_{ij}|$ is indeed the definition of the maximum row sum norm in some books. If you define $\|A\|_\infty$ as the matrix norm induced by the vector norm $\|x\|_\infty$, it is your responsibility to make it clear in your question. $\endgroup$
    – user1551
    Jul 12 '13 at 9:49

I assume that the author tries to derive the matrix norms $\|A\|_1$ and $\|A\|_\infty$ induced by vector norms $\|x\|_1$ and $\|x\|_\infty$.

Let's take, for example, $\|\cdot\|_\infty$. We write

$$\|Ax\|_\infty=\sup_i \left|\sum_j A_{ij}x_j\right|\le \sup_i \sum_j |A_{ij}||x_j|\le \sup_j |x_j| \sup_i \sum_j |A_{ij}|.$$ Hence, a good candidate for $\|A\|_\infty$ is $\sup_i \sum_j |A_{ij}|$. We need to prove that this boundary is indeed achieved; it is true, since we can take $i$ where that supremum is achieved and impose $x_j=\mathrm{sign}(A_{ij})$. With such $x$ all our inequalities degenerate to equalities and we conclude that $\|A\|_\infty = \sup_i \sum_j |A_{ij}|$ is a matrix norm induced by $\|x\|_\infty = \sup_j |x_j|$.

The case $\|\cdot\|_1$ is done likewise.

  • $\begingroup$ By showing there exists such an x, how do we know that it is the tightest possible upper bound? – $\endgroup$ Aug 24 '18 at 19:10
  • 1
    $\begingroup$ @SridharThiagarajan because for one of such $x$ the chain of inequalities will become a chain of equalities. $\endgroup$ Aug 24 '18 at 19:13

I will give you some guidelines then. Suppose an $m$-by-$n$ matrix $A = (a_{ij})$ is given. For any $n$-dimensional vector $x$,

\begin{align*} \|Ax\|_1 & = \sum_{i=1}^m \left|\sum_{j=1}^n a_{ij}x_j\right| \\ & \le \sum_{i=1}^m \sum_{j=1}^n \left|a_{ij}x_j\right| \\ & = \sum_{j=1}^n \left|x_j\right| \sum_{i=1}^m \left|a_{ij}\right| \\ & = \sum_{j=1}^n \left|x_j\right| A_j \end{align*} where I define $A_j = \sum_{i=1}^m \left|a_{ij}\right|$. If $J = \operatorname{argmax}_j A_j$, i.e., $A_J$ is a maximum among all $A_j$'s, then $$ \|Ax\|_1 \le A_J \sum_{j=1}^n |x_j| = A_J \|x\|_1. $$ This shows that $\|A\|_1 \le A_J$. Next, you show that there exists $x$ such that $\|Ax\|_1 = A_J\|x\|_1$. This is quite simple as you can choose $x_i = 0$ for all $i \ne J$, and $x_J = 1$ or $-1$.

For the case of $\|\cdot\|_\infty$, the situation is quite similar. (Choosing $x$ in the last step might be a bit tricky as you need to pick the right signs.) I will leave that to you.

  • 3
    $\begingroup$ Funny enough, you decided to take $\|\cdot\|_1$ and I took $\|\cdot\|_\infty$. Combined together these two posts give a complete answer) $\endgroup$ Jul 12 '13 at 10:08

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.