6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you worked out the cases for one-dimensional and two-dimensional A? $\endgroup$ – mhum Dec 29 '15 at 23:38
  • $\begingroup$ @mhum, I have added some information on the one-dimensional case. I have not worked out the two-dimensional case. $\endgroup$ – Calle Dec 30 '15 at 23:08
  • $\begingroup$ Ok. Are you more interested in the case of general $A$ or particularly in the case where $A$ has entries in $\{+1,-1\}$? If the latter, then I believe there is a further simplification for the one-dimensional case: If $A$ has only $+1$, then the sum is $2^n - 1$; if $A$ has even one $-1$, then the sum is $-1$. $\endgroup$ – mhum Dec 30 '15 at 23:11
  • $\begingroup$ @mhum, I am mostly interested in the case with entries from $\{ \pm 1\}$, but I wouldn't mind a solution to a more general case. Yes, the one-dimensional case is special, and there doesn't seem to be such a rule for the two-dimensional case. $\endgroup$ – Calle Dec 31 '15 at 13:35
  • $\begingroup$ I have a trick for the two-dimensional case with $\pm 1$ entries. I'll write up a sketch. $\endgroup$ – mhum Dec 31 '15 at 23:28
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is a very interesting answer, thank you! $\endgroup$ – Calle Jan 2 '16 at 16:32
  • $\begingroup$ I've so far been unable to find an extension of this trick into three dimensions. But, if this is a practical question rather than a theoretical one, you might be able to get away with doing $2^{n_3}-1$ rank calculations of order $n_1 \times n_2$ if $n_3$ is sufficiently small. $\endgroup$ – mhum Jan 4 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.