# A Clarification on the Summation symbol

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:

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

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

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

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 by a moderator:
shmoe
Homework Helper
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?

shmoe said:
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~

Last edited:
shmoe
Homework Helper
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:
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~