# Computing the sum over paths through a matrix satisfying constraints

Let $A$ be a $m \times n$ matrix and let Y be the set of paths "from left to right through the matrix"

$$Y=\lbrace 1 \ldots m \rbrace ^N$$

Let $f(y;A)$ be the "sum along the path $y$"

$$f(y;A) = \sum_{i=1}^n A_{y_i,i}$$

Let $Z_k = \lbrace y \in Y : f(y,A) < k \rbrace$. I wish to calculate $\sum_{y\in Z_k} f(y;A)$

There is a simple dynamic programming solution to the sum over all paths:

$$S(i,j;A) = \sum_{k=1}^m S(k,j-1;A) + A_{i,j} m^{i-1}$$

with base cases

$$S(1,j;A) = A_{1,j}$$

Is there a way to generalize this to compute the sum over paths satisfying $f(y;A) < k$ ?

-
If k is small, then you just need to keep track of the multiset of path-lengths so far, discarding those which exceed k. If k is large, then there's a generating function argument against an efficient solution. – John Wiltshire-Gordon Feb 12 '12 at 20:44
Thanks John, can you expand on the generating function argument, or give me a pointer? By the way, the elements of A can be negative. – Alex Flint Feb 15 '12 at 10:31
@Alex Flint If the entries of A are negative, we may add some constant to each entry so they all become positive. Unfortunately, this means that k will be large and your problem is hopeless in general. – John Wiltshire-Gordon Feb 15 '12 at 18:10

Here is an example calculation using generating functions. We begin with a matrix

$$A = \left( \begin{array}{cccc} 1 & -1 & 0 & 2\\ 2 & 2 & -3 & 0\\ 0 & 2 & 1 & 2 \end{array} \right).$$

Each column contributes a factor of $\sum x^e$ where $e$ ranges over the column:

$$f(x)=(x+x^2+x^0)(x^{-1}+2x^2)(x^0 + x^{-3}+x^1)(2x^2+x^0)$$

Expanding, we see that

$$f(x)=x^{-4} + x^{-3} + 3 x^{-2} + 5 x^{-1} + 6 x^{0} + 10 x^1 + 11 x^2 + 12 x^3 + 10 x^4 + 10 x^5 + 8 x^6 + 4 x^7.$$

These coefficients have a combinatorial interpretation: they count the number of paths of a given sum! For instance, the term $4x^7$ signals that four paths sum to 7.

Unfortunately, we are now in the position of asking for the sum of the coefficients of $f(x)$ in a certain range of degrees. This problem is NP-complete because an efficient algorithm would solve the subset sum problem.

For example: we wish to determine if the set $\{-7, -3, -2, 5, 8 \}$ has a subset which sums to zero (borrowing the example from http://en.wikipedia.org/wiki/Subset_sum_problem). Consider the matrices

$$B = \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 0\\ -7 & -3 & -2 & 5 & 8\end{array} \right)$$

and

$$B' = \left( \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 0\\ 1 & -7 & -3 & -2 & 5 & 8\end{array} \right).$$

Taking $k=0$, $B$ is asking about subsets with negative sum, while $B'$ is asking about subsets with nonpositive sum (each of which will appear twice). Subtracting half the answer for $B'$ from the answer for $B$, we obtain the number of ways to produce $0$ as a subset sum:

$$14-26/2 = 1.$$

This number is not zero, so there exists a subset with sum 0. Worse, this tells us how many such subsets there are, answering a question in #P.

-
Thanks John, this is very helpful. – Alex Flint Feb 16 '12 at 8:27