Sum of all products of subarrays

Question

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} a_{i_1,i_2,i_3}.$$

A subarray (cf. submatrix) of $A$ is given deleting rows in any of the tree dimensions. For e.g. the $3 \times 3 \times 3$ array $B$ with elements $b_{ijk}$: $$B = \left( \begin{array}{ccc} \left( \begin{array}{c} b_{1,1,1} \\ b_{1,1,2} \\ b_{1,1,3} \end{array} \right) & \left( \begin{array}{c} b_{1,2,1} \\ b_{1,2,2} \\ b_{1,2,3} \end{array} \right) & \left( \begin{array}{c} b_{1,3,1} \\ b_{1,3,2} \\ b_{1,3,3} \end{array} \right) \\ \left( \begin{array}{c} b_{2,1,1} \\ b_{2,1,2} \\ b_{2,1,3} \end{array} \right) & \left( \begin{array}{c} b_{2,2,1} \\ b_{2,2,2} \\ b_{2,2,3} \end{array} \right) & \left( \begin{array}{c} b_{2,3,1} \\ b_{2,3,2} \\ b_{2,3,3} \end{array} \right) \\ \left( \begin{array}{c} b_{3,1,1} \\ b_{3,1,2} \\ b_{3,1,3} \end{array} \right) & \left( \begin{array}{c} b_{3,2,1} \\ b_{3,2,2} \\ b_{3,2,3} \end{array} \right) & \left( \begin{array}{c} b_{3,3,1} \\ b_{3,3,2} \\ b_{3,3,3} \end{array} \right) \end{array} \right)$$ one can form a subarray $B'$ of $B$ by deleting the first row in the first dimension, the second row in the second dimension, and keeping all of the third dimension: $$B' = \left( \begin{array}{cc} \left( \begin{array}{c} b_{2,1,1} \\ b_{2,1,2} \\ b_{2,1,3} \end{array} \right) & \left( \begin{array}{c} b_{2,3,1} \\ b_{2,3,2} \\ b_{2,3,3} \end{array} \right) \\ \left( \begin{array}{c} b_{3,1,1} \\ b_{3,1,2} \\ b_{3,1,3} \end{array} \right) & \left( \begin{array}{c} b_{3,3,1} \\ b_{3,3,2} \\ b_{3,3,3} \end{array} \right) \end{array} \right).$$

For a given three-dimensional array $A$ with elements only being $1$ or $-1$, I want to compute the sum of $P(A')$ for all subarrays $A'$ of $A$: $$\sum_{A' \text{ subarray of } A} P(A').$$

Is there a clever way to do this? Can it be done in polynomial time?

In other words, I want to compute

$$\sum_{S_1,S_2,S_3} \prod_{i_1 \in S_1} \prod_{i_2 \in S_2} \prod_{i_3 \in S_3} a_{i_1,i_2,i_3},$$

where $S_i$ ranges over all non-empty subsets of $[n_i] = \{1,\dots,n_i\}$

Some observations I have made: A subarray is uniquely determined by which rows are kept from the original array. For example, in the case above $B'$ is determined by saying that we keep rows $2,3$ in the first dimension, rows $1,3$ in the second dimension and rows $1,2,3$ in the third dimension. So, for a $n_1 \times n_2 \times n_3$ array $A$, we get one subarray for each triple of subsets $(l_1,l_2,l_3)$, where $l_1 \subset \{1, \dots, n_1\}$ and so on. This gives a total of $(2^{n_1} - 1)(2^{n_2} -1)(2^{n_3} -1)$ subarrays, so a naive approach is out of the question if we want to compute the sum in polynomial time.

If a subarray is given by $(l_1,l_2,l_3)$ then another subarray is given by $(l_1 \setminus [n_1], l_2 \setminus [n_2], l_3 \setminus [n_3])$, so if you compute $P$ for one subarray, you get the other one "for free", if you know what $P$ for the whole array is. Maybe this can be used to do some clever thing, but I can't see it.

Here is a table of the products for the $2 \times 2 \times 2$ case, each row are the elements we want to multiply together in one product, and the result will be the sum of the products: $$\begin{array}{llllllll} b_{1,1,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,1,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,1} & b_{1,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,1} & b_{1,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,1} & b_{2,1,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,2} & b_{1,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,2} & b_{2,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,2,1} & b_{1,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,2,1} & b_{2,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,2,2} & b_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,1,1} & b_{2,1,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,1,1} & b_{2,2,1} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,1,2} & b_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{2,2,1} & b_{2,2,2} & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,1} & b_{1,1,2} & b_{1,2,1} & b_{1,2,2} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,1} & b_{1,1,2} & b_{2,1,1} & b_{2,1,2} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,1} & b_{1,2,1} & b_{2,1,1} & b_{2,2,1} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,2} & b_{1,2,2} & b_{2,1,2} & b_{2,2,2} & \text{} & \text{} & \text{} & \text{} \\ b_{1,2,1} & b_{1,2,2} & b_{2,2,1} & b_{2,2,2} & \text{} & \text{} & \text{} & \text{} \\ b_{2,1,1} & b_{2,1,2} & b_{2,2,1} & b_{2,2,2} & \text{} & \text{} & \text{} & \text{} \\ b_{1,1,1} & b_{1,1,2} & b_{1,2,1} & b_{1,2,2} & b_{2,1,1} & b_{2,1,2} & b_{2,2,1} & b_{2,2,2} \end{array}$$

The one-dimensional case

If we have a one-dimensional array $A$, we can just as well consider $A$ to be a set and compute: $$\sum_{A' \subseteq A} \prod_{x \in A'} x$$ which can be computed by considering the polynomial $$p(x) = \prod_{a \in A} (x-a)$$ and if we expand this polynomial to $$p(x) = \sum_{j=0}^n \alpha_j x^j$$ the coefficient $\alpha_j$ is the sum of all products of $n - j$ elements in $A$, so to get total sum we just need to sum the $\alpha$. Computing the coefficients $\alpha_j$ can be done in polynomial time.

Answer 1

This is a partial solution for the case of a two-dimensional $A$ with entries in $\{+1, -1\}$.

First, some notation.

As above, for a given array $A$, let $P(A)$ denote the product of all the entries in $A$. Further, we'll define $S(A)$ to be the sum of all $P(B)$ where $B$ is a subarray of $A$.

For a given array $A$ with index sets $I_1 \times I_2 \times \ldots$, we identify a subarray $B$ of $A$ by a tuple of subsets $S_1 \times S_2 \times \dots$ where $\emptyset \neq S_j \subseteq I_j$. We will denote $B = A[S_1, S_2, \ldots]$.

Lemma 1: Let $A$ be a one-dimensional array (i.e.: vector) of length $n$ with entries in $\{+1, -1\}$. If $A$ consists solely of $+1$ entries, then $S(A) = 2^n-1$; otherwise if $A$ contains any $-1$ entries, then $S(A) = -1$.

Proof: Left as an exercise to the reader

Let $A$ be a $n_1 \times n_2$ two-dimensional array (i.e.: matrix) with entries in $\{+1, -1\}$. For a fixed $T \subseteq [n_2]$, we can easily compute the sum

$$S_T := \Sigma_{S \subseteq [n_1]} P(A[S, T])$$

by reducing the two-dimensional problem to the one-dimensional one. Note that $$S(A) = \Sigma_{\emptyset \neq T \subseteq n_2} S_T$$ Let us treat $A$ as a set of $n_2$ vectors, each of length $n_1$. In this way, the subarray $A[[n_1], T]$ (with $T \subseteq [n_2]$) can be considered a set of vectors $\{v_i | i \in T\}$. Consider the vector $u$ where $u[j] = \Pi v_i[j]$, i.e.: the $j^{th}$ entry of $u$ is the product of the $j^{th}$ entries of all the $v_i$. From Lemma 1, we know that if all the elements of $u$ are $+1$, then the required sum is $2^{n_1}-1$; otherwise, it is $-1$. We'll call $T$ degenerate in the former case and non-degenerate in the latter.

Of course, this alone doesn't quite help us enough because there are still exponentially many subsets $T \subseteq [n_2]$. So, lets try to understand exactly which subsets $T$ are degenerate. Evidently , $T$ is degenerate iff for all $1\leq j\leq n_1$ there are an even number of $-1$s in $\{v_i[j] | i \in T\}$. Now, when we see situations involving the parity of entries over an array, the first thing we should think about is translating things over to $\mathbb{Z}_2$, the field over 2 elements.

Define: For an array $A$ with entries in $\{+1,-1\}$, we define the array $A'$ by mapping each entry in $A$ according to $+1\mapsto 0$ and $-1 \mapsto 1$. We will typically understand the entries of $A'$ to be elements of $\mathbb{Z}_2$.

Lemma 2: A subset $T \subseteq [n_2]$ is degenerate iff the vector sum $\Sigma_{i\in T} v'_i$ equals the zero vector (over $\mathbb{Z}_2$).

Proof: This follows directly from the fact that an even number of $1$s in $\mathbb{Z}_2$ sums to $0$.

Corrollary 2: If $T$ is such that the set of vectors $\{v'_i|i\in T\}$ has full rank over $\mathbb{Z}_2$ then $ \forall \emptyset \neq U \subseteq T$, $U$ is non-degenerate.

We see now that the degeneracy of a subset $T$ is intimately tied up with the rank of the associated matrix $A'[[n_1], T]$. So, let us take $r$ to be the rank of $A'$ over $\mathbb{Z}_2$. Let us re-order the vectors $\{v_1, v_2,\ldots, v_{n_2}\}$ so that $\{v'_1, v'_2, \ldots, v'_r\}$ forms a maximal, linearly independent subset of $\{v'_1,v'_2,\ldots,v'_{n_2}\}$. By Corollary 2, we know that if $T \subseteq [r]$, then $T$ is non-degenerate.

Now, consider some non-empty subset $U$ of $\{r+1, r+2, \ldots, n_2\}$. By some basic properties of linear algebra, we know that there is a unique (possibly empty) subset $V \subseteq [r]$ such that $\Sigma_{j\in V} v'_j = \Sigma_{j \in U} v'_j$. And, since we're operating in $\mathbb{Z}_2$, we can re-arrange this equality into $\Sigma_{j\in U \cup V} v'_j = 0$. So, we conclude that for every non-empty subset $U$ of $\{r+1, r+2, \ldots, n_2\}$ we can construct a unique degenerate subset $T \subseteq [n_2]$. Conversely, we claim that every degenerate subset $T$ is accounted for in this manner (proof left to the reader).

Theorem: Let $A$ be a $n_1 \times n_2$ two-dimensional array with entries in $\{+1, -1\}$. Let $r$ be the rank of $A'$ over $\mathbb{Z}_2$. Then,

$$ S(A) = (2^{n_2-r}-1) * (2^{n_1}-1) - (2^{n_2} - 2^{n_2-r})*(-1) $$

Proof: The first summand corresponds to the $2^{n_2-r}-1$ degenerate subsets formed by extended the non-empty subsets of $\{r+1, r+2, \ldots, n_2\}$. The second summand corresponds to all the other (non-degenerate) subsets.