Let $\|\cdot \|:\mathbb{R}^n\rightarrow \mathbb{R}$ be the norm defined by $$\|x\|=\max_{1\leq i\leq n}|ix_i|, \ x\in \mathbb{R}^n$$ Show that the corresponding matrix norm to vector norm $\|\cdot \|$ can be computed by $$\|A\|=\max_{1\leq i\leq n}\sum_{j=1}^n\frac{i}{j}|a_{i,j}|, \ A\in \mathbb{R}^{n\times n}$$
We have that $$\|A\|=\sup_{x\neq 0}\frac{\|Ax\|}{\|x\|}$$ So we have to write the numerator and the denominator using the given formula, right?
It is :\begin{align*}\frac{\|Ax\|}{\|x\|}&=\frac{\displaystyle{\max_{1\leq i\leq n}\left |i\sum_{i,j}a_{i,j}x_i\right |}}{\|x\|}\leq \frac{\displaystyle{\max_{1\leq i\leq n}i\sum_{i,j}|a_{i,j}|\cdot |x_i|}}{\|x\|} \leq \frac{\displaystyle{\left (\max_{1\leq i\leq n}\sum_{i,j}|a_{i,j}|\right )\cdot \left (\max_{1\leq i\leq n}i |x_i|\right )}}{\|x\|}\\ & =\frac{\displaystyle{\left (\max_{1\leq i\leq n}\sum_{i,j}|a_{i,j}|\right )\cdot \|x\|}}{\|x\|}=\max_{1\leq i\leq n}\sum_{i,j}|a_{i,j}|\end{align*} How do weget the missing term $\frac{i}{j}$ ?
Best Answer
On one hand, we have \begin{aligned} \frac{\|Ax\|}{\|x\|} &=\frac{\max_i\left|i(Ax)_i\right|}{\|x\|}\\ &=\frac{\max_i\left|i\sum_j a_{ij}x_j\right|}{\|x\|}\\ &=\frac{\max_i\left|\frac{i}{j}\sum_j a_{ij}jx_j\right|}{\|x\|}\\ &\le\frac{\max_i\frac{i}{j}\sum_j |a_{ij}|\|x\|}{\|x\|}\\ &=\max_i\frac{i}{j}\sum_j |a_{ij}|. \end{aligned} On the other hand, tie occurs in the inequality above when $|x_1|=|2x_2|=\cdots=|nx_n|$ and the sign of each $x_j$ is chosen such that $a_{i_0j}x_j\ge0$ for every $j$ on row $i_0$, where $i_0=\arg\max_i\frac{i}{j}\sum_j |a_{ij}|$. Therefore $\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}=\max_i\frac{i}{j}\sum_j|a_{ij}|$.
If you are familiar with the induced maximum norm $\|B\|_\infty=\sup_{x\ne0}\frac{\|Bx\|_\infty}{\|x\|_\infty}$ and know that it is identical to $\max_i\sum_j|b_{ij}|$, here is a cleaner solution. Let $D=\operatorname{diag}(1,2,\ldots,n)$. Then $\|x\|=\|Dx\|_\infty$ and hence $$ \|A\| =\sup_{\|x\|=1}\|Ax\| =\sup_{\|Dx\|_\infty=1}\|DAx\|_\infty =\sup_{\|y\|_\infty=1}\|DAD^{-1}y\|_\infty =\|DAD^{-1}\|_\infty. $$ It is now evident that the $\frac{i}{j}$ factor comes from $DAD^{-1}$ because $(DAD^{-1})_{ij}=\frac{i}{j}a_{ij}$.