Summation Over Matrices

Start with computationally tractable:

Suppose we have M dimensions with N values for each dimesion. Assume all values used.

So full entries are: $$M^N$$

Suppose we aggregate over 1 dimension we get $$M^{N-1}$$ values and we can do this for N different dimensions yielding:

$$N M^{N-1}$$

Next one we will N choose 2 (columns to aggregate over) times $$M^{N-2}$$

Repeating we see that total number of aggregates is:

$$ Total = \sum_{i=1}^{N} C_{i}^{N} M^{N-i}$$

Now let us assume that N = M, then:

$$ Total = \sum_{i=1...N} C_{i}^{N} N^{N-i} = \sum_{i=1...N} \frac{N!}{i!(N-i)!} N^{N-i} $$

$$ Total \leq \sum_{i=1...N} \frac{N^{i}}{i!} N^{N-i} = \sum_{i=1...N} \frac{N^{N}}{i!} = N^{N} \sum_{i=1...N} \frac{1}{i!} $$

And finally:

$$ Total \leq N^{N} \sum_{i=0…N-1} \frac{1}{2^{i}} \leq 2 N^{N} = 2 \textrm{x Number of original entries} $$

Seems likely that we can do worse than this in real world cases. Would be nice to get an upper bound ….