# max induced norm of matrix

I have to prove that matrix norm $||A||_\infty$ induced by vector norm $||x||_\infty = \smash{\displaystyle\max_{1 \leq k \leq n}} |x_k|$ where $x_k$ is k-th element of vector can be disribed by equation $||A||_\infty = \smash{\displaystyle\max_{1 \leq i \leq n}} \sum\limits_{j=1}^{n}|a_{i,j}|$.

I can use fact that induced norm $||A||_\alpha = \sup \limits_{x\neq 0} \frac{||Ax||_\alpha}{||x||_\alpha}$.

Oblvius conclusion is that $||A||_\infty = \smash{\displaystyle\max_{1 \leq i \leq n}} |\sum\limits_{j=1}^{n}a_{i,j}x_j| : \smash{\displaystyle\max_{1 \leq i \leq n}}|x_i|$ and i cannot move past that point. I think i am missing some knowledge about x. Can anyone give me a hint how to move past that point?

## 1 Answer

Notice that since $\|x\|_\infty>0$ you can push the denominator into the max, then into the absolute value, and then apply the distributive property to the sum, i.e. $$\frac{\max_{i}\left|\sum_j a_{ij} x_j\right|}{\|x\|_\infty}=\max_{i}\left|\sum_j a_{ij}\frac{x_j}{\|x\|_\infty}\right|$$

You can then upper bound this value due to the fact that $x_j \le \|x\|_\infty \Rightarrow\frac{x_j}{\|x\|_\infty}\le1$, hence: $$\max_{i}\left|\sum_j a_{ij}\frac{x_j}{\|x\|_\infty}\right|\le \max_{i}\left|\sum_j a_{ij}\right|$$

Now, you only need to to find an $x$ such that this upper bound is achieved. I leave that to you (it's quite straightforward, really).

• Well it looks that x be vector like [a,a,a,a,a,a,..a] a>0. $x_j \le \|x\|_\infty \Rightarrow\frac{x_j}{\|x\|_\infty}\le1$- this is of course true but its not can be less then zero: $$\max_{i}\left|\sum_j a_{ij}\frac{x_j}{\|x\|_\infty}\right|\le \max_{i}\left|\sum_j a_{ij}\right|$$ - and i dont think its true: well imagine such a matrix [1 ,2 ,3 , 4, 5, 6] [2 ,-3 ,4 ,-5 ,6 ,-7] sum of first row is of course greater then sum of the row below now lets assume that $x = [1,-1,1,-1,1,-1]^T$ then ||x||= 1 and sum of second row * x is greater then sum of 1 row * x Jan 22 '14 at 8:22
• nevermind i got it at long least what i was getting wrong Jan 22 '14 at 8:28
• You're right, sorry about that, the absolute value should have been inside the sum otherwise you can't deal with negative $a_{ij}$ values. In which case you would need to flip the sign of the entries in the vector $x$ associated to negative $a_{ij}$. Jan 22 '14 at 8:49