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: MNM^N

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

NMN−1N M^{N-1}

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

Repeating we see that total number of aggregates is:

Total=∑i=1NCiNMN−i Total = \sum_{i=1}^{N} C_{i}^{N} M^{N-i}

Now let us assume that N = M, then:

Total=∑i=1...NCiNNN−i=∑i=1...NN!i!(N−i)!NN−iTotal = \sum_{i=1...N} C_{i}^{N} N^{N-i} = \sum_{i=1...N} \frac{N!}{i!(N-i)!} N^{N-i}
Total≤∑i=1...NNii!NN−i=∑i=1...NNNi!=NN∑i=1...N1i! 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≤NN∑i=0...N−112i≤2NN=2x Number of original entriesTotal \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 …