Expansion of $\prod_{j=1}^{n} \left( \sum_{i = 1}^{m} x_{i, j} \right)$

Question

I would like to know if there is a sum-of-products expansion for the following product-of-sums. A special case is given here for the difference of two entries.

$$\prod_{j=1}^{n} \left( \sum_{i= 1}^{m} x_{i, j} \right)$$

I suspect the result will be a sum-of-product-of-products because of having to distribute each term of each factor out to each term of each other factor.

Answer 1

Indeed, you can expand this out to get a sum of products $$\sum_{f\in S}\prod_{j=1}^n x_{f(j),j}$$ where $S$ is the set of all functions $\{1,\dots,n\}\to\{1,\dots,m\}$. Intuitively, this is the sum of all products you can form by picking one term from each of the sums in the original expression and multiplying them together. Hopefully it should make some intuitive sense why this is what the distributive law ends up giving you. More formally, you can prove this by induction on $n$: in the induction step, you just have to know how to expand out a product of two big sums (the one you get from the induction hypothesis and the final factor of the product), and you can prove how that works by induction on the number of terms in the sums.

Answer 2

You can write it as $$\sum_{(i_1,\dots,i_n)\in\{1,\dots,m\}^n} \prod_{j=1}^n x_{i_j,j}$$

Answer 3

$$ \large{ \sum_{1\leq\ k_1,\ k_2,\ \ldots,\ k_n\ \leq m} \left(\prod_{i=1}^{n} x_{k_i,i} \right)} $$