# Sparsest matrix with specified row and column sums

Given a sequence of row sums $r_1, \ldots, r_m$ and column sums $c_1, \ldots, c_n$, all positive, I'd like to find a matrix $A_{m\times n}$ consistent with the given row and column sums that has the fewest nonzero entries. That is, we want to minimize $|\{a_{ij} \ne 0\}|$ under the constraint that $\sum_j a_{ij} = r_i$ and $\sum_i a_{ij} = c_j$.

One can also think of this as a network flow problem, with $m$ sources and $n$ sinks that must be connected with the minimum number of edges to achieve the specified flow out of each source ($r_i$) or into each sink ($c_j$).

Is this a known problem, or does it fit into a well-known class of problems? What is the computational complexity of finding the optimal solution? According to the comments on this Reddit discussion, it could be related to the cutting stock problem, but it's not exactly the same.

The motivation for this problem comes from settling debts. Suppose you have a set of people $P$ with debts between them. These debts can be settled by (1) finding the net debt $d(p)$ owed to each person $p \in P$, (2) dividing $P$ into two disjoint sets of people who are owed, $P_+ = \{p : d(p) > 0\}$, and people who owe, $P_- = \{p : d(p) < 0\}$, and (3) having the people in $P_-$ pay the ones in $P_+$. Then the problem of resolving debts with the fewest transactions is equivalent to the above optimization problem, with $a_{ij}$ being the amount that the $i$th person in $P_-$ must give the $j$th person in $P_+$.

-

This is linear optimization in the $L_0$ (Hamming) metric which in full generality is NP-hard, so either there is a solution adapted to the specific structure of the debt settlement equations, or it is intractable.

One structure the debt settlement system has is sparsity. It can be written as $m+n$ equations in $mn$ variables, with only $2mn$ (out of $(mn)^2$) nonzero coefficients. This is a very sparse system to which $L_0$-$L_1$ transference (so-called "compressed sensing") methods may apply, reducing the problem to linear programming.

-
Thanks, the connection to compressed sensing is surprising and very interesting. I'm trying to look up the precise conditions under which $L_0$-$L_1$ transference holds, but it occurs to me that if the $L_1$ metric is $\sum a_{ij}$, then it is constant (equal to $\sum r_i$ and $\sum c_j$) over the entire feasible space, so this may not help for this problem. –  Rahul Sep 9 '10 at 19:42
Rahul, that's a very interesting observation. Thanks. –  T.. Sep 9 '10 at 23:19

It turns out that, as T.. had guessed, the problem is indeed NP-hard. I realised this after participating in some discussions in the comments of this blog post where the same problem turned up again, and the corresponding Reddit discussion. The solution I am posting here is based on the above.

First, a lemma: The optimal solution for $m+n$ people cannot have more than $m+n-1$ nonzero entries.

The proof is by inductive construction of a solution with $m+n-1$ entries. For $m = n = 1$, the solution trivially has 1 entry. When $m+n > 2$, let $a_{11} = \min(r_1,c_1)$. This satisfies one row or column (or both, if $r_1 = c_1$), leaving a subproblem of size $m+n-1$ whose solution has at most $m+n-2$ entries. This completes the proof of the lemma.

Suppose a solution exists with fewer than $m+n-1$ entries. Consider the network flow view of the problem, with $m+n$ nodes connected by edges. If there are fewer than $m+n-1$ edges, the underlying undirected graph is disconnected. Then each connected component is "self-sufficient" in that it has no net in- or out-flow. That means that the sum of the corresponding subset of $\{r_i\} \cup \{-c_j\}$ is zero. So, this problem includes the subset sum problem, which is NP-complete.

More precisely, suppose an instance of the subset sum problem is given as a set of integers $X = \{x_1,\ldots,x_k\}$, and the problem is to determine whether there is a nonempty subset of $X$ whose sum is zero. Let these be the debts $d(p)$ among a set of people $P$ as in the question, introducing an additional person with $d(p) = -\sum X$ to balance the books. Then there is a solution with fewer than $|P|-1$ entries if and only if there is a subset of $X$ with sum zero. (The above lemma is useful for proving the "if" part.) Therefore the subset sum problem can be reduced to this problem.

-