A Clarification on the Summation symbol

[relinquished™]

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:

$$\| 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)$$

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


$$\left( \sum_j a_j \right) \left(\sum_k b_k\right) = \sum_j \sum_k a_j b_k \quad (2)$$

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

All help is appreciated

Thanks,

Reli~

 

[Muzza]

Seems wrong to me. $\sum_{i = 1}^n |a_{ik}|$ doesn't make any sense, because k is an index variable for a different sum.

 

[shmoe]

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.

 

[relinquished™]

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

Here, they state that

$$\| 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$$

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

$$\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$$

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

$$\|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|$$

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

I'm really confused. All help is appreciated.

Reli~

 

[shmoe]

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

$$\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)$$

The second sum is "inside" the first, it still depends on k. Does this clarify?

 

[relinquished™]

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

$$\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)$$

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 $$\sum^n_{k=1} |x_k|$$ in the first website (OR $$\sum^n_{j=1} |x_j|$$ in the second website)

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

Website 1

$$\| 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}|$$

Again, for Website #2,

EDIT: Changed subscripts from k to j

$$\| Ax \|_1 \leq \sum^n_{j=1} |x_j| \sum^n_{i=1} |a_{ij}|$$

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

$$\| Ax \|_1 \leq C \sum^n_{j=1} |x_j| = C \|x\|_1$$

Hence,

$$\frac{\| Ax \|_1}{\|x\|_1} \leq C$$

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

Thanks for all the help,

Reli~

 

[shmoe]

On website #1 they get to:

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

Which you can think of as:

$$\| A \|_1 \leq \max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k| c_k$$

where

$$c_k=\sum^n_{i=1} |a_{ik}|$$

Replacing $$c_k$$ in the sum with the max (as k ranges from 1 to n) gives:

$$\| 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)$$

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:

$$\| 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)$$

and $$\max \limits_{\| x\|_1 = 1} \sum^n_{k=1} |x_k|=1$$, so that's it.

 

[relinquished™]

Thanks a lot shmoe. From you explanation of #1, I can see why they did the same for #2. Thanks alot! I appreciate the help!

Reli~