How can I prove maximum norm?

Question

Prove that for a matrix $A \in R^{n \times n}$, we have

$$\|A\|_{\infty}=\max_{i=1,...,n}\sum_{j=1}^{n}|a_{ij}|.$$

I know that

$$\|A\|_{\infty}=\max\frac{\|Ax\|_{\infty}}{\|x\|_{\infty}}$$

such that $x \in R^n$.

Answer 1

You are on the right track. For the induced norm $\|A\|_\infty=\text{max}\frac{\|Ax\|_\infty}{\|x\|_\infty}$ we can also write the induced norm $\|A\|_\infty=\max\limits_{x \neq 0} (\|Ax\|_\infty)$ where $\|x\|_\infty = 1$. We know that the definition of the infinity norm on matrices is choosing the largest element. So follow these steps where $\|x\|_\infty=1$: $$\begin{aligned}\|A\|_\infty&= \max_{x\in\Bbb R^n,\|x\|_\infty=1} (\|Ax\|_\infty)\\&=\max_{x \in \Bbb R^n, \|x\|_\infty=1} (\max_{i \in [1,n]} |a_i x|)\\&\le\max_{x \in \Bbb R^n, \|x\|_\infty=1}\left(\max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}x_j|\right)\\&\le \max_{x \in \Bbb R^n, \|x\|_\infty=1}\left(\max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}||x_j|\right)\\&\le\max_{x \in \Bbb R^n, \|x\|_\infty=1}\left(\max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}|\max_{i \in [1,n]}(x_i)\right)\\&=\max_{x \in \Bbb R^n, \|x\|_\infty=1} \left(\max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}| \|x\|_\infty\right)\\&= \max_{x \in \Bbb R^n, \|x\|_\infty=1} \left(\max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}|\cdot 1\right)\\&= \max_{x \in \Bbb R^n, \|x\|_\infty=1}\left(\max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}|\right)\\&= \max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}|\end{aligned}$$

Now it just remains to show that we can always find an $v \in \mathbb{R}^n, \ \|v\|_\infty=1$ where this upper bound can be attained. If such an $v$ exists, then we know that $\|A\|_\infty = \max_{x \in \Bbb R^n, \|x\|_\infty=1} (\|Ax\|_\infty) \ge \|Av\|_\infty$.

Suppose that the maximal row sum occurs at row $k$. Then let $v$ be defined by:

$$ v^\top = \begin{pmatrix} \frac{|a_{k1}|}{a_{k1}} & \frac{|a_{k2}|}{a_{k2}} & \cdots & \frac{|a_{kn}|}{a_{kn}} \\ \end{pmatrix}$$

The $k^{th}$ entry of $Av$ is $a_i v = \sum_{j=1}^n |a_{kj}|$ which is the maximal row sum of $A$. Therefore $$\|Av\|_\infty \ge \max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}|$$ so we have defined a $v$ as we wished.

Given that $\|Av\|_\infty \ge \max\limits_{i \in [1,n]} \sum\limits_{j=1}^n |a_{ij}|$ and $\|Av\|_\infty \le \max\limits_{i \in [1,n]} \sum\limits_{j=1}^n |a_{ij}|,$ we have shown that $$\|Av\|_\infty = \max_{i \in [1,n]} \sum_{j=1}^n |a_{ij}|.$$