# Intuition for Multiple Summation becoming One Summation - Nothing too formal/rigorous please

Source. I grok addition is associative and commutative, and a term can be moved into other summations iff these other summations aren't summing this term. Hence I grok

$$\sum_{i,j} g_{ij} \sum_r a_{ir} x_r \sum_s a_{js} x_s = \sum_{i,j} \sum_{r} \sum_s g_{ij} a_{ir}x_r a_{js}x_s = \color{blue}{ \sum_{i} \sum_{j} \sum_{r} \sum_s g_{ij} a_{ir}x_r a_{js}x_s}.$$

$$\text{But } \color{blue}{ \sum_{i} \sum_{j} \sum_{r} \sum_s g_{ij} a_{ir}x_r a_{js}x_s} = \sum_{i, j, r, s} g_{ij} a_{ir}x_r a_{js}x_s \,???$$

(Follow-up 1) The R.S. of $\color{green}{\sum_{i_k} A_{i_1,i_2,\dots , i_k} = A^1_{i_1,i_2,\dots , i_{k-1}}}$ eliminates $i_k$ and introduces superscript $1$.
Similarly, R.S. of $\sum_{i_{k - 1}} \color{green}{A^1_{i_1,i_2,\dots , i_{k-1}}}= \color{#7A7676}{A^2_{i_1,i_2,\dots ,i_{k - 3}, i_{k-2}}}$ eliminates $i_{k - 1}$ and introduces superscript $2$.
Similarly, R.S. of $\sum_{i_{k - 1}}\color{#7A7676}{A^2_{i_1,\dots ,i_{k - 3}, i_{k-2}}}= A^3_{i_1,\dots ,i_{k - 4}, i_{k-3}}$ eliminates $i_{k - 2}$ and introduces superscript $3$ and so forth...

But what do the $A^{\text{# of index removed}}_{\text{one less index than before}}$ and this whole process mean, other than writing out the $k - 1$ summation symbols?

(II) More generally, if $i_k$ satisfies some property $P(i_k)$, then how to rewrite with only 1 summation $$\sum\limits_{i_1 \; : \; P(i_1)} \cdots \sum\limits_{i_{k - 1} \; : \; P(i_{k - 1})} \; \sum\limits_{i_k \; : \; P(i_k)} A(i_1, ..., i_k) \; ?$$

(III) You wrote $\sum_{i_1,i_2,\dots , i_k} A_{i_1,i_2,\dots , i_k}= \sum_{i_1}\bigl(\sum_{i_2} \dots \color{green}{\left[\sum_{i_k} A_{i_1,i_2,\dots , i_k}\right]} \cdots \bigr)$.
Why are there dots after the green sum? It is the last sum, so nothing comes after?

(Follow-up 2) (II) Sadly I do not understand the first three sentences in your answer. Can you please elaborate? Is $\sum_{j=1}^{r} B_j$ one sum or a multiple sum already rewritten as one sum?

Also, thank you for recommending writing multiple sums. Actually, I like them better too! But I am addled by $S=\sum_{i,j} \epsilon_{ij} = -\sum_{i,j} \epsilon_{ji} =-\sum_{j,i} \epsilon_{ji} =-S$. You summed over $i, j$ but there is only one sum here. Why not two sums? Which is better?

-
Isn't it only one notation? – eccstartup Jul 20 '13 at 12:01
That's also just rebracketing such as in $(a_{1,1}+a_{1,2})+(a_{2,1}+a_{2,2})+(a_{3,1}+a_{3,2}) = a_{1,1}+a_{1,2}+a_{2,1}+a_{2,2}+a_{3,1}+a_{3,2}$. – Hagen von Eitzen Jul 20 '13 at 12:25
Just added a follow-up to your follow-up. Hope it helps. – James S. Cook Nov 16 '13 at 15:45
Writing $\sum_{i,j,k}$ instead of $\sum_i\sum_j\sum_k$ is tantamount to writing $\int_{R}$ for $R=[a,b]\times [c,d]\times [e,f]$ a cube instead of an iterated integral $\int_a^b\int_c^d\int_e^f$ (of course, we're not always promised this is possible with integrals, but neither we're promised it is possible with infinite sums) – Pedro Tamaroff Nov 16 '13 at 15:46
@PedroTamaroff thanks! I think that helps my edit further. – James S. Cook Nov 16 '13 at 17:30

The notation $\sum_{i_1,i_2,\dots , i_k}$ is just short-hand for the iterated sums $\sum_{i_1}$, $\sum_{i_2}, \dots , \sum_{i_k}$. I would say (my convention) starting with $i_k$ and proceeding outward to $i_1$:

$$\sum_{i_1,i_2,\dots , i_k} A_{i_1,i_2,\dots , i_k}= \sum_{i_1}\bigl(\sum_{i_2} \dots \color{green}{\left[\sum_{i_k} A_{i_1,i_2,\dots , i_k}\right]} \cdots \bigr)$$

In particular, if we denote $\color{green}{\sum_{i_k} A_{i_1,i_2,\dots , i_k} = A^1_{i_1,i_2,\dots , i_{k-1}}}$ then $$\sum_{i_1,i_2,\dots , i_k} A_{i_1,i_2,\dots , i_k}= \sum_{i_1}\bigl(\sum_{i_2} \dots \sum_{i_{k - 2}} \underbrace{\sum_{i_{k-1}} \color{green}{\left[A^1_{i_1,i_2,\dots , i_{k-1}}\right]}}_{\Large{A^2_{i_1,\dots ,i_{k - 3}, i_{k-2}}}} \cdots \bigr)$$

and so forth until we're down to $\sum_{i_1,i_2,\dots , i_k} A_{i_1,i_2,\dots , i_k} =\sum_{i_1} A^{k-1}_{i_1}$.
This would be my default interpretation of such an expression. Some obvious questions to ask:

1. how am I sure it wasn't done in a different order, say starting with $i_1$ and proceeding outward until finally we finish with the sum over $i_k$?

2. wait, does it even matter which order the summations are taken? The simplest version of this is does $\sum_i (\sum_j A_{ij}) = \sum_j(\sum_i A_{ij})$ ?

If the answer to (2.) is no, then the answer to (1.) is that the order of summation does not matter. Here, we're assuming that (2.) extends to $k$-sums. But that's clear since we can always break
a $k$-sum into iterated $2$-sums, in other words $\sum\limits_{i_1}\left(\sum\limits_{i_2,...,i_k}\right) = \sum\limits_{i_k}\left(\sum\limits_{i_1,...,i_{k - 1}}\right)$

So, let us address (2.). To keep it easy to understand let's look at $n=2$: $$\sum_{i=1}^2\sum_{j=1}^2 A_{ij} = \sum_{i=1}^2 (A_{i1}+A_{i2}) = (A_{11}+A_{12})+(A_{21}+A_{22}).$$ Compare against: $$\sum_{i=j}^2\sum_{i=1}^2 A_{ij} = \sum_{j=1}^2 (A_{1j}+A_{2j}) = (A_{11}+A_{21})+(A_{12}+A_{22}).$$ So as Hagen von Eitzen has commented, it's just rearranging parenthesis. Now, if these summations pass to infinite upper bounds (series) then we cannot rearrange these so easily. Some analytical conditions concerning uniformity of the convergence must be met. But, so long as the sums are finite, we can reorder them.

Incidentally, if you did want to prove these things carefully, you'll need a definition for the finite sum. May I recommend that $\sum_{i=1}^{1} A_i = A_1$ and $\sum_{i=1}^{n+1}A_i = A_{n+1}+\sum_{i=1}^{n}A_i$. Most authors think these things are too trivial to put in books.

Following the follow-up:

I.) the superscript notation in my example is merely to emphasize the idea that the summations can be thought of as happening one at a time. It's much the same idea as the iterated integral $\int_0^1 \int_{0}^{x}\int_0^{1-x-y} xydz \, dy \, dx$

1. we integrate over $z$ leaving $\int_0^1 \int_{0}^{x} \underbrace{[xy(1-x)-xy^2)]}_{\text{like} \ A_1} \, dy \, dx$

2. next, integrate over $y$ leaving $\int_0^1 \underbrace{[x\frac{x^2}{2}(1-x)-x\frac{x^3}{3})]}_{\text{like} \ A_2} \, dx$

3. finally we're left with an integral in just one variable $\int_0^1 \underbrace{[x\frac{x^2}{2}(1-x)-x\frac{x^3}{3})]}_{\text{like} \ A_2} \, dx = \frac{-1}{24}$

My idea was to suppress the indices of summation to emphasize that after the sum is complete that index is gone for the summations that follow. Just like $z$ or $y$ is gone as we iterate the integral inside out.

II.) writing multiple sums as one sum? Well, I suppose the sum is just an addition of finitely many terms thus we can place the possible indices in an ordered set and label those indices from say $1$ to $r$ where $r$ is the total number of summands then the iterated sum becomes $\sum_{j=1}^{r} B_j$. However, I don't recommend this. The point of writing multiple sums is found both from their natural origin from compound summative processes (for example, the finite sum which sets-up the double integral) as well as the nice property that repeated sums allow us to exploit symmetries between certain subsets of the summands $B_1, \dots B_r$. For example, $\sum_{i,j} \epsilon_{ij} = 0$ since, by definition, $\epsilon_{ij}=-\epsilon_{ji}$ and so: $$S=\sum_{i,j} \epsilon_{ij} = -\sum_{i,j} \epsilon_{ji} =-\sum_{j,i} \epsilon_{ji} =-S$$ which shows $S=0$.

III.) this one is easier, those dots indicate the many parentheses I did not write.

In response to Following the follow-up (2): I meant to indicate that a multiple finite sum is still just the sum of finitely many things. For example, $$\sum_{i=1}^3 \sum_{j=1}^3 A_{ij} = \sum_{r=1}^9 B_r$$ provided I define $B_1 = A_{11}, B_2 = A_{12}, \dots , B_9 = A_{33}$. This would not usually be a wise step since it hides any nice symmetries of the summands $A_{ij}$. Getting back to my other comment, to be more pedantic, \begin{align} S &= \sum_i \sum_j \epsilon_{ij} \\ &= -\sum_i \sum_j \epsilon_{ji} \qquad \text{since $\epsilon_{ij} = -\epsilon_{ji}$} \\ &= -\sum_j \sum_i \epsilon_{ji} \qquad \text{property of finite sums, can swap order}\\ &=-S \end{align} and thus $S=0$.

-
Sorry for the late reply. +1. Thanks a lot. I made some minor edits and hope they're OK with you. I have some follow-ups that I put in my question. Can you please get back to me in your answer, and not in comments? Sub- and superscripts are too hard to read down here. – Pauline Ercute Nov 16 '13 at 9:12
Sorry for my late reply. Thanks so much! It's too bad I can't upvote more than once. I'll do it for your other first-rate posts. I have another follow-up to II. Can you please get back to me in your answer and not in comments? Merry Christmas! – Pauline Ercute Dec 22 '13 at 14:47
@P.Ercute Merry Christmas to you as well, sorry for the delay, I'm a bit wrapped up in preparing for next semester. It happens that I was writing a proof that the sums can swap. I'd add it here but it's already a bit slow to add more. If you want to ask a question about that alone, I'll cut and paste my proof in there for you. It might have to wait until next year though. – James S. Cook Dec 30 '13 at 6:21
Thanks so much! No problem. I can wait until next year. Can you please post your proof or link to it here as a second answer? I want to keep everything together. Happy new year! – Pauline Ercute Dec 30 '13 at 11:59
Can you please give an example of "nice symmetries of the summands $A_{ij}$ in your answer that you talked about in your last follow-up (your follow-up to my follow-up 2)? I'm stuck on seeing why it's bad to write out multiple sums as one single sum. – Pauline Ercute Dec 30 '13 at 12:03

This answer adds detail to the comments. In particular, it is primarily intended to provide proof of the following basic claim about finite sums: Let us call this $P_n$:

$$\sum_{i=1}^{n} \biggl( \sum_{j=1}^{n} B_{ij} \biggr) = \sum_{j=1}^{n}\biggl( \sum_{i=1}^{n} B_{ij} \biggr)$$

Here it is assumed that $B_{ij}$ are given scalars (could be real, complex, even functions)

Proof: we use induction on $n$. Observe for $n=1$ it is trivially true as $B_{11}=B_{11}$ so no sum is even possible. While I don't think it's logically necessary, it might be helpful to see the proof for $n=2$ as well: $$\sum_{i=1}^{2}\sum_{j=1}^{2} B_{ij} = \sum_{i=1}^{2} [B_{i1}+B_{i2}] = [B_{11}+B_{12}] + [B_{21}+B_{22}]$$ On the other hand, $$\sum_{j=1}^{2}\sum_{i=1}^{2} B_{ij} = \sum_{j=1}^{2} [B_{1j}+B_{2j}] = [B_{11}+B_{21}] + [B_{11}+B_{21}].$$ The sums in opposite order produce the same terms overall, just rearranged.

Next, assume inductively that $P_n$ is true for some $n > 1$. Using the definition of sum throughout and the induction hypothesis in transitioning from the 3-rd to the 4-th line: \begin{align} \notag \sum_{i=1}^{n+1}\sum_{j=1}^{n+1} B_{ij} &=\sum_{i=1}^{n+1}\biggl[ B_{i,n+1}+\sum_{j=1}^{n} B_{ij} \biggr] \\ \notag &=\sum_{i=1}^{n+1} B_{i,n+1}+\sum_{i=1}^{n+1}\sum_{j=1}^{n} B_{ij} \\ \notag &=\sum_{i=1}^{n+1} B_{i,n+1}+\sum_{j=1}^{n} B_{n+1,j}+\sum_{i=1}^{n}\sum_{j=1}^{n} B_{ij} \\ \notag &=\sum_{i=1}^{n+1} B_{i,n+1}+\sum_{j=1}^{n} B_{n+1,j}+\sum_{j=1}^{n}\sum_{i=1}^{n} B_{ij} \\ \notag &=\sum_{i=1}^{n+1} B_{i,n+1}+\sum_{j=1}^{n} \left[ B_{n+1,j}+\sum_{i=1}^{n} B_{ij} \right] \\ \notag &=\sum_{i=1}^{n+1} B_{i,n+1}+\sum_{j=1}^{n}\sum_{i=1}^{n+1} B_{ij} \\ \notag &=\sum_{j=1}^{n+1}\sum_{i=1}^{n+1} B_{ij} \notag \end{align} Thus $n$ implies $n+1$ for $P_n$ therefore by proof by mathematical induction we find $P_n$ is true for all $n \in \mathbb{N}$. In short, we can swap the order of finite sums.

Now, as to why it's bad to just lump all the indices into one longer ranging index, the example where I showed $S=-S$ hence $S=0$ is such an example. If I just wrote out all the terms it would take me longer to see the cancellation which is essentially manifest in the double-index notation. An important lemma of tensor calculus, is that whenever we see a symmetric pair of indices contracted (summed over all the values) multiplied with an object with antisymmetric indices then the result is zero. This happens in many calculations I've seen. Here's one from calculus III, $$(\nabla \times \nabla f)_k = \sum_{i,j=1}^{3} \epsilon_{ijk} \partial_i \partial_j f$$ Clairaut's theorem says for continuously twice differentiable functions $\partial_i \partial_j f=\partial_j \partial_i f$ hence the expression above is symmetric in $i,j$ whereas $\epsilon_{ijk}$ is antisymmetric hence $(\nabla \times \nabla f)_k=0$ for $k=1,2,3$ hence $\nabla \times \nabla f =0$.

Note, the symbol $\epsilon_{ijk}$ is the completely antisymmetric symbol. It is defined by $\epsilon_{123}=1$ and the assumed antisymmetry. For example, $\epsilon_{112}=0$ whereas $\epsilon_{213}=-1$ and $\epsilon_{231}=1$ etc... there are six nonzero values and 21 triples where $\epsilon_{ijk}=0$.

-