A Clarification on the Summation symbol

  • #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:

Answers and Replies

  • #2
695
0
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.
 
  • #3
shmoe
Science Advisor
Homework Helper
1,992
1
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.
 
  • #4
shmoe said:
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.
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 [Broken]

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 [Broken]

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 by a moderator:
  • #5
shmoe
Science Advisor
Homework Helper
1,992
1
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?
 
  • #6
shmoe said:
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?
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:
  • #7
shmoe
Science Advisor
Homework Helper
1,992
1
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:
  • #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~
 

Related Threads on A Clarification on the Summation symbol

  • Last Post
Replies
15
Views
10K
Replies
9
Views
4K
Replies
5
Views
737
  • Last Post
Replies
3
Views
23K
  • Last Post
Replies
4
Views
305
  • Last Post
Replies
1
Views
771
  • Last Post
Replies
10
Views
20K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
4
Views
534
  • Last Post
Replies
1
Views
1K
Top