Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

\begin{equation} Y=\lbrace 1 \ldots m \rbrace ^N \end{equation}

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

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

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:

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

with base cases

\begin{equation} S(1,j;A) = A_{1,j} \end{equation}

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

share|improve this question
1  
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
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks John, this is very helpful. –  Alex Flint Feb 16 '12 at 8:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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