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

A Clarification on the Summation symbol

  1. Aug 21, 2006 #1
    Hi guys,

    I know this may sound so "newbieish", but I really need some clarification. While resaerching over the net I came across a proof on a derivation of the Matrix p-norms. While reading, I stumbled upon this part of the proof:

    [tex]

    \| Ax \|_1 \leq \sum^n_{i=1} \left| \sum^n_{k=1} a_{ik}x_k \right| = \left( \sum^n_{k=1} |x_k| \right) \left( \sum^n_{i=1} |a_{ik}| \right)
    \quad (1)
    [/tex]

    I am confused when I came upon this. I know that


    [tex]
    \left( \sum_j a_j \right) \left(\sum_k b_k\right) = \sum_j \sum_k a_j b_k \quad (2)
    [/tex]

    But in (1), the [tex]b_k[/tex] term is given by [tex]a_{ik}[/tex]. Is it possible to "split" the two summation symbols into a product of two sums even though it's clear that [tex]a_{ik}[/tex] is dependent on both i and k?

    All help is appreciated

    Thanks,

    Reli~
     
    Last edited: Aug 21, 2006
  2. jcsd
  3. Aug 21, 2006 #2
    Seems wrong to me. [itex]\sum_{i = 1}^n |a_{ik}|[/itex] doesn't make any sense, because k is an index variable for a different sum.
     
  4. Aug 21, 2006 #3

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Was this found on a webpage? Do you have the link? It's probably just some typsetting problems, parenthesis where they don't belong (also an equality which should be an inequality), but it would be good to see the next few lines to make sure.
     
  5. Aug 21, 2006 #4
    Yes, this was found on a webpage. I was reading the part for the Derivation of the Matrix 1-norm (column sum norm) on this page.

    http://www.maths.lancs.ac.uk/~gilbert/m306a/node6.html

    Here, they state that

    [tex]

    \| A \|_1 \leq \max \limits_{\| x\|_1 = 1} \sum^n_{i=1} \left| \sum^n_{k=1} a_{ik}x_k \right| = \max \limits_{\| x\|_1 = 1} \left( \sum^n_{k=1} |x_k| \right) \left( \sum^n_{i=1} |a_{ik}| \right)\quad

    [/tex]

    Here, they equated after applying the triangle equality, which implied that

    [tex]
    \max \limits_{\| x\|_1 = 1} \sum^n_{i=1} \left| \sum^n_{k=1} a_{ik}x_k \right| = \max \limits_{\| x\|_1 = 1} \left( \sum^n_{k=1} |x_k| \right) \left( \sum^n_{i=1} |a_{ik}| \right)\quad
    [/tex]

    I also thought this was a misprint, or maybe it had something to do with the maximum function. But then I visited another webpage just to make sure.

    http://web.umr.edu/~hilgers/classes/CS328/notes/norm/node7.html

    Again, in their derivation of the matrix 1-norm, it states that

    [tex]
    \|Ax\|_1 \leq \sum^n_{i=1}\sum^n_{j=1} |a_{ij}||x_j| = \leq \sum^n_{j=1} |x_j| \sum^n_{i=1} |a_{ij}| \leq C \sum^n_{j=1} |x_j|
    [/tex]

    They did the exact same thing - "split" the summation so that the [tex]\sum^n_{k=1} |x_k| [/tex] could be "factored".

    I'm really confused. All help is appreciated.

    Reli~
     
    Last edited: Aug 21, 2006
  6. Aug 21, 2006 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    It's fine, and different from what you've written. Let me add some parenthesis:

    [tex]\sum^n_{i=1} \left| \sum^n_{k=1} a_{ik}x_k \right| \leq \sum^n_{i=1} \sum^n_{k=1} |a_{ik}||x_k|
    =\sum^n_{k=1}\left( |x_k| \sum^n_{i=1} |a_{ik}| \right)[/tex]

    The second sum is "inside" the first, it still depends on k. Does this clarify?
     
  7. Aug 21, 2006 #6
    Well, it is right, however, what I'm really troubled about is how they treated [tex] \sum^n_{k=1} |x_k| [/tex] in the first website (OR [tex] \sum^n_{j=1} |x_j| [/tex] in the second website)

    This is what they did after they "split" the summation"

    Website 1

    [tex]

    \| A \|_1 \leq \max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k| \sum^n_{i=1} |a_{ij}| \\
    \leq \max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k| \max \limits_{j} \sum^n_{i=1} |a_{ij}| = \max \limits_{j} \sum^n_{i=1} |a_{ij}|

    [/tex]

    Again, for Website #2,

    EDIT: Changed subscripts from k to j

    [tex]

    \| Ax \|_1 \leq \sum^n_{j=1} |x_j| \sum^n_{i=1} |a_{ij}|
    [/tex]

    Define [tex]C = \max \limits_{1\leq j\leq n} \sum^n_{i=1} |a_{ij}| [/tex]. Then

    [tex]
    \| Ax \|_1 \leq C \sum^n_{j=1} |x_j| = C \|x\|_1
    [/tex]

    Hence,

    [tex]
    \frac{\| Ax \|_1}{\|x\|_1} \leq C
    [/tex]

    In both cases, it seems like they treat [tex]\sum^n_{k=1} |x_k|[/tex] like a factor. Or maybe... is it [tex]\sum^n_{i=1} |a_{ij}|[/tex] that they're treating like a factor? God... I'm confused >.<

    Thanks for all the help,

    Reli~
     
    Last edited: Aug 21, 2006
  8. Aug 21, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    On website #1 they get to:

    [tex]\| A \|_1 \leq \max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k| \sum^n_{i=1} |a_{ik}|[/tex]

    Which you can think of as:

    [tex]\| A \|_1 \leq \max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k| c_k [/tex]

    where

    [tex]c_k=\sum^n_{i=1} |a_{ik}|[/tex]

    Replacing [tex]c_k[/tex] in the sum with the max (as k ranges from 1 to n) gives:

    [tex]\| A \|_1 \leq \max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k| \left(\max\limits_{1\leq j\leq n} c_j\right)[/tex]

    This inner max is not dependant on k or your choice of the vector x, so it can be pulled out of the summation sign and the max over the vectors x to give:

    [tex]\| A \|_1 \leq \left(\max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k|\right)\left( \max\limits_{1\leq j\leq n} c_j\right)[/tex]

    and [tex]\max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k|=1[/tex], so that's it.
     
    Last edited: Aug 21, 2006
  9. Aug 21, 2006 #8
    Thanks alot shmoe. From you explanation of #1, I can see why they did the same for #2. Thanks alot! I appreciate the help!

    Reli~
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A Clarification on the Summation symbol
  1. Summation question (Replies: 3)

  2. Summation Verification (Replies: 6)

Loading...