# A Clarification on the Summation symbol

1. Aug 21, 2006

### 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~

Last edited: Aug 21, 2006
2. Aug 21, 2006

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

3. Aug 21, 2006

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

4. Aug 21, 2006

### relinquished™

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~

Last edited: Aug 21, 2006
5. Aug 21, 2006

### 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?

6. Aug 21, 2006

### relinquished™

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~

Last edited: Aug 21, 2006
7. Aug 21, 2006

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

Last edited: Aug 21, 2006
8. Aug 21, 2006

### relinquished™

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~