# Optimize summing over 4d matrix

Say I have an $$N \times N$$ matrix defined by $$A_{ij} = f(i,j)$$ with $$i=1, 2, ..., N$$ and similar for $$j$$ and the symmetric function $$f(i,j)=f(j,i)$$. If I want to sum over all elements, $$\sum_{ij}^N A_{ij}$$, I can simplify it (in terms of reducing iterations) as

$$\sum_{ij} A_{ij} = 2 \sum_{j=1} \sum_{i=j+1} A_{ij} + \sum_{j=1} A_{jj}$$

where the first term is twice the off-diagonal part and the second term is the diagonal.

Now: I have a tensor $$A_{ijkl} = g(i,j,k,l)$$ with the function that obeys the eightfold symmetry $$g(i,j,k,l) = g(j,i,k,l) = g(i,j,l,k) = g(j,i,l,k)$$ and $$g(k,l,i,j) = g(k,l,j,i) = g(l,k,i,j) = g(l,k,j,i)$$ (symmetrical upon permuting $$i$$ and $$j$$ as well as $$k$$ and $$l$$ as well as the products $$ij$$ and $$lk$$, similarly to something like $$ij+kl$$, if I see that correctly). I'm sure there must be a 'trick' like before but something like

$$\sum_{ijkl} A_{ijkl} \neq 4 \sum_{j=1} \sum_{i=j+1} \sum_{l=1} \sum_{k=l+1} A_{ijkl} + 2\sum_{jl} A_{jjll}$$

is not the answer. How do I think about these 'higher' dimensional problems to simplify them?

• What does $\sum_{i+i}$ mean? Also, do you really mean $A_{ij}=ij$ or some arbitrary symmetric function of $i$ and $j$? Commented May 10, 2022 at 1:31
• The $i+i$ was a typo, sorry. I corrected it to $i+1$. The notion $ij$ was to denote an arbitrary symmetric function, which I wrote out explicitly now. Thanks for the clarifying questions.
– ste
Commented May 10, 2022 at 12:48
• There are still some issues. It should be $f(i,j)$, and you didn't mention symmetry. Similarly, $g(i,j,k,l)$. And what does $\sum_{i+1}$ mean? Commented May 10, 2022 at 12:59
• I corrected the sum again. It's essentially the notion of summing over the upper triangle part, doubling it and adding the left out diagonal. As for the function, I put the correct notation and explicitly stated the symmetry relations. I originally put $ij+kl$ because as far as I see it, $ij+kl$ obeys the symmetry relations that I added now. Thanks again for the help in stating the question!
– ste
Commented May 10, 2022 at 13:42

I'm assuming the symmetry $$g(i,j,k,l) = g(j,i,k,l) = g(j,i,l,k)$$, thus symmetry in the first two an second two arguments, this is what I think you mean with your assumptions. Then, you can use the 'trick' from the 2-D case to obtain:

$$\sum_{ijkl} g(i,j,k,l) = \sum_{ij}\left(\sum_k g(i,j,k,k) + \sum_k\sum_{l > k}g(i,j,k,l)\right).$$

Rearranging and using the trick again (this time for i and j) yields:

$$... = \sum_k\left(\sum_i g(i,i,k,k) + 2 \sum_i \sum_{j > i}g(i,j,k,k)\right) + 2\sum_k \sum_{l > k}\left(\sum_i g(i,i,k,k) + 2 \sum_i \sum_{j > i}g(i,j,k,l)\right).$$

Simplifying this gives:

$$\sum_{ik} g(i,i,k,k) + 2\sum_k\sum_{i}\sum_{j>i}g(i,j,k,k) + 2 \sum_i \sum_k \sum_{l > k} g(i,i,k,l) + 4 \sum_i\sum_k\sum_{j > i}\sum_{l > k}g(i,j,k,l)$$

(I have not checked this, if you find any errors, please tell me)

• I have specified the symmetry more clearly, I'm terribly sorry I wasn't clear the first time. With $ij+kl$ I meant symmetry upon permuting the $i$ and $j$ as well as $k$ and $l$ as well as each pair, so permuting $ij$ and $kl$. In your assumptions $g(i,j,l,k)$ is missing (I think even for your stated symmetry), to obtain 4-fold, furthermore the symmetries where $i,j$ and $k,l$ are flipped to obtain 8-fold.
– ste
Commented May 10, 2022 at 13:54