Product of sums as sum of products

Question

Let $\mathbf{X} \in \mathbb{R}^{m \times n}$, and $x_{m,n}$ be the element in the $m$-th row and $n$-th column of the matrix. Is it possible to rewrite the product of sums $\prod_{m=1}^{M} \sum_{n = 1}^{N} x_{m, n}$ as a sum of products?

Answer 1

Yes, it's possible. I suspect the tough part is how to write such a summation.

In the $3 \times 2$ case, the sum is \begin{align*} (x_{11} + x_{21})(x_{21} + x_{22})(x_{31} + x_{32}) &= x_{11}x_{21}x_{31} + x_{12}x_{21}x_{31} + x_{11}x_{22}x_{31} + x_{12}x_{22}x_{31} \\ &+ x_{11}x_{21}x_{32} + x_{12}x_{21}x_{32} + x_{11}x_{22}x_{32} + x_{12}x_{22}x_{32}, \end{align*} certainly a sum of products, when expanded.

In general, a product like $(a_1 + a_2 + \cdots + a_{n})(b_1 + b_2 + \ldots + b_{n})\ldots (z_1 + z_2 + \ldots + z_n)$ of $m$ factors expands into a sum of products: one term for each selection $(a_{i_1}, b_{i_2}, \ldots, z_{i_m})$. In short, you just make $m$ selection of indices, each being selected from $n$ possible indices. Thus, each function $f: \{1, 2, \ldots, m\} \to \{1, 2, \ldots, n\}$ uniquely identifies a term in the product.

If we use the notation $[M] = \{1, 2, \ldots, M\}$ and $[N] = \{1, 2, \ldots, N\}$, the set of all functions $f: [M] \to [N]$ is usually denoted $[N]^{[M]}$ (in part because there are $N^M$ such functions).

We may then write $\prod_{m=1}^{M} \sum_{n = 1}^{N} x_{m, n}$ as a sum indexed by these functions, namely, $$\sum_{f \in [n]^{[m]}} \prod_{m = 1}^M x_{m,f(m)}$$

In the intro example, we can see all $8$ functions $f \in [2]^{[3]}$ showing up: The $x_{11}x_{21}x_{31}$ coming from the function that sends all of $1, 2$, and $3$ to $1$, then the $x_{12}x_{21}x_{31}$ corresponding to the function $f: 1 \mapsto 2,\, 2 \mapsto 1,\, 3 \mapsto 1$, and so on.

Answer 2

Looks like$$\sum_{n_{1},\ldots,n_{M}=1}^{N}\prod_{m=1}^{M}x_{m,n_{m}}$$ should do the trick.