Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is this proof of an ##\infty## norm valid?

  1. Jan 26, 2016 #1
    I am trying to prove
    ##||A||_{\infty} = max_i \sum_{j} |a_{ij}|##
    which reads as the ##\infty## norm is the max row sum of matrix A.
    ##i## is the row index and ##j## is the column index.

    Here is what I thought of:

    ##||A||_{\infty} = sup_{x\neq 0} \frac{||Ax||_{\infty}}{||x||_{\infty}}##
    The numerator can be written as:
    ##||Ax||_{\infty} = max_i \sum_{j} |a_{ij} x_j| \leq max_i \sum_{j} |a_{ij}|\ |x_j| \leq max_j |x_j| * max_i \sum_{j} |a_{ij}| = ||x||_{\infty} * max_i \sum_{j} |a_{ij}|##
    Therefore,
    ##||Ax||_{\infty} \leq ||x||_{\infty} * max_i \sum_{j} |a_{ij}|##
    Next,
    ##\frac{||Ax||_{\infty}}{||x||_{\infty}} \leq max_i \sum_{j} |a_{ij}|##
    Next,
    the supremum is defined as the "least upper bound." Thus, the supremum of the above expression is simply the equal sign. Thus,
    ##||A||_{\infty} = max_i \sum_{j} |a_{ij}|##


    Do you guys see any flaws in this proof? I saw various other proofs that went on to prove that the "<" condition cannot exist, which is still correct, but I don't understand what the point is when you know that the supremum is the "LEAST" upper bound.
     
  2. jcsd
  3. Jan 26, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The first equality is incorrect. However, it's fixable. Replace
    $$||Ax||_{\infty} = max_i \sum_{j} |a_{ij} x_j|$$
    by
    $$||Ax||_{\infty} = max_i \left\vert \sum_{j} a_{ij} x_j\right\vert\leq max_i \sum_{j} |a_{ij} x_j|$$
    I haven't looked through the rest yet. Will do that a bit later, but have to run off now.
     
  4. Jan 26, 2016 #3
    Ah yes! Thanks. that is a typo, but the rest of the proof did not carry over that typo.
     
  5. Jan 26, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That is correct.
    I'm afraid that doesn't make sense. A supremum is a number. An equals sign is not. Nor can I see any way of interpreting this statement to make it both meaningful and correct.

    What you have proven (it needs a couple more steps added in, but you're close enough) is that
    $$||A||_{\infty} \leq max_i \sum_{j} |a_{ij}|$$
    Now you need to prove that
    $$ ||A||_{\infty} \geq max_i \sum_{j} |a_{ij}|$$

    Hint, use the definition of the infinity norm, and consider only vectors ##x## of norm 1. What's the biggest value of ##\|Ax\|_\infty## you can get given that ##x## has norm 1?
     
  6. Jan 26, 2016 #5
    This is the part where I got stuck on.

    I am not sure if it was the way I worded it, but I mean to say the supremum is the condition given by the equal sign, since it would be the "lowest" "upper" bound. Does that still not make sense?

    I was influenced by an answer to another thread I made where I made a hypothetical example:
    ##x\leq y##
    sup(x) = y

    so carried over to the current problem, wouldn't that make it the condition given by the equal sign?
     
  7. Jan 26, 2016 #6
    i.e., ##sup_{x\neq 0} \frac{||Ax||_{\infty}}{||x||_{\infty}} = max_i \sum_{j} |a_{ij}|##

    since we know the least upper bound of ##\frac{||Ax||_{\infty}}{||x||_{\infty}}## is ##max_i \sum_{j} |a_{ij}|##
     
  8. Jan 27, 2016 #7

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Since we know ##||A||_{\infty}## is an upper bound for ##\frac{||Ax||_{\infty}}{||x||_{\infty}}##, to prove it's a least upper bound, all that's needed is to find a vector ##x## for which ##||A||_{\infty}=\frac{||Ax||_{\infty}}{||x||_{\infty}}##.

    This is equivalent to finding a vector ##x## with unit infinity-norm, such that ##||A||_{\infty}=||Ax||_{\infty}##.
    Can you think of such a unit vector? Since you want to make the vector as 'big' as possible, what's the 'biggest' vector you can think of that has unit infinity-norm (start by thinking of 'big' as meaning the size of the usual norm on ##\mathbb{R}^n##).
     
  9. Jan 27, 2016 #8
    Thank you. I think I know what I was missing. I basically used the end result to arrive st the end result which doesn't make much sense, since I am to prove the end result.

    Are you saying x has to be a unit vector with an infinity norm equal to 1?
    If so wouldn't that just be a vector with all zero elements except for one element which is 1?
     
  10. Jan 27, 2016 #9

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    'UNit vector' just means a vector with norm equal to 1. Since all the norms being used here are infinity norms, that means a vector ##x## such that ##\|x\|_\infty=1##, which in turn means a vector for which the largest absolute value of any of its components is 1. For example, if ##n=3##, then (1 0 0), (1 1 0), (0 1 0), (0 -1 1), (1 1 1), (1 -1 1), (0.5 0 1), (0.5 -0.5 -1) are all unit vectors.

    What I'm suggesting in my post is that you consider which of the vectors like this have the largest 2-norm, where the 2-norm of vector ##x## is the 'usual' (not infinity) norm calculation ##\|x\|_2\equiv\left(\sum_{k=1}^n x_k{}^2\right)^\tfrac{1}{2}##.
     
  11. Jan 27, 2016 #10
    Oh I see.
    Largest 2-norm would be (1,1,1), (-1, -1, -1), and so on.

    So ##||x||_{\infty} = 1##
    and
    ##||Ax||_{\infty} = max_i |\sum_{j} a_{ij}|##

    is this the idea?
     
  12. Jan 27, 2016 #11

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, that's it! :smile:
     
  13. Jan 27, 2016 #12
    Thanks. Dumb question, but I am not seeing how this proves the infinite norm of a matrix.
    I just showed ##||Ax||_{\infty} = max_i |\sum_j a_{ij}|##
    but I am unsure how this relates to
    ##||A_{\infty}||##

    I think I'm missing a simple connection here.
     
  14. Jan 27, 2016 #13
    In particular, I am not understanding why we looked for a vector with a unit infinity norm that maximizes the 2-norm.
     
  15. Jan 27, 2016 #14
    I am not understanding why we looked for a vector with a unit infinity norm that maximizes the 2-norm.
     
  16. Jan 27, 2016 #15

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Above it was shown that, for all vectors ##x##, we have
    $$\frac{||Ax||_{\infty}}{||x||_{\infty}} \leq \max_i \sum_{j} |a_{ij}| $$
    So ##\max_i \sum_{j} |a_{ij}|## is an upper bound for ##\frac{||Ax||_{\infty}}{||x||_{\infty}}## over ##x##.
    You have just identified a value of ##x##, namely ##x'\equiv (1 1 1)##, for which ##\frac{||Ax'||_{\infty}}{||x'||_{\infty}} = \max_i \sum_{j} |a_{ij}|##.

    What does that tell you about whether there can be an upper bound ##u## for ##\frac{||Ax||_{\infty}}{||x||_{\infty}}## that is less than ##\max_i \sum_{j} |a_{ij}|##?

    And what does that then tell you about what sort of an upper bound ##\max_i \sum_{j} |a_{ij}|## is?
     
  17. Jan 27, 2016 #16
    So I'm thinking, what if we have:
    ##
    A = \begin{bmatrix}
    1 & 1\\
    1 & 1
    \end{bmatrix}##

    and ##
    x =
    \begin{bmatrix}
    1\\
    0
    \end{bmatrix}##

    We can see that ##||Ax||_{\infty} = 1## and ##||x||_{\infty} = 1##
    thus ##\frac{||Ax||_{\infty}}{||x||_{\infty}}= 1##
    but
    ##\max_i \sum_{j} |a_{ij}| = 2##
    so the equality doesn't hold?

    ##\max_i \sum_{j} |a_{ij}| ## would always be greater or equal to ##\frac{||Ax||_{\infty}}{||x||_{\infty}}## for all ##x##
     
  18. Jan 27, 2016 #17

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, but that doesn't advance the proof at all, as you already proved that in the OP. The missing piece is to show that it's a least upper bound, not just any old upper bound. Focus on the two questions at the end of my post #15.
     
  19. Jan 27, 2016 #18
    For the first question:
    There can't be an upper bound ##u## less than ##\max_i \sum_j |a_{ij}|## Anything lower wouldn't be considered an "upper" bound.
    For the second question:
    Since anything lower is a no longer an "upper" bound, ##\max_i \sum_j |a_{ij}|## is simply the "least" upper bound.

    I think these are the missing piece?


    I still don't understand why we picked a unit vector with an infinity norm = 1 and a maximum 2-norm.
    Also, for this post, how does the past previous posts prove that $$ ||A||_{\infty} \geq max_i \sum_{j} |a_{ij}|$$?
     
  20. Jan 27, 2016 #19

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    They don't. That's (equivalent to) the extra bit that you have to prove. See post 15 for hints on how to prove that.
     
  21. Jan 27, 2016 #20
    So carrying on we have shown that for
    ##x'\equiv (1 1 1)##, ##\frac{||Ax'||_{\infty}}{||x'||_{\infty}} = \max_i \sum_{j} |a_{ij}|##.
    The next statement can be
    $$ ||A||_{\infty} \geq max_i \sum_{j} |a_{ij}|$$

    So in one line:
    ##||Ax||_{\infty} = sup_{x\neq 0}\frac{||Ax||_{\infty}}{||x||_{\infty}} \leq max_i \sum_{j} |a_{ij}| = \frac{||Ax'||_{\infty}}{||x'||_{\infty}} \leq ||Ax||_{\infty}##
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Is this proof of an ##\infty## norm valid?
  1. Validity of a proof (Replies: 5)

  2. Valid argument ? (Replies: 2)

  3. What's this norm? (Replies: 2)

  4. Confusing 2-norm proof (Replies: 6)

Loading...