Sum of all products of subarrays

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 don

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.

StackExchange Computer Science Q#51007, answer score: 4