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?


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).

  • $\begingroup$ 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 $\endgroup$ Jan 22 '14 at 8:22
  • $\begingroup$ nevermind i got it at long least what i was getting wrong $\endgroup$ Jan 22 '14 at 8:28
  • $\begingroup$ 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}$. $\endgroup$
    – horqat
    Jan 22 '14 at 8:49

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.