# Can one find any solution to this matrix problem in polynomial time?

I am given an M * N (M > 1, N > 1) matrix with all the numbers blackened but their row and column sums are visible.

For example, I am given this 3 * 3 matrix. And one of the possible matrix values are My question is, can one solve one set of possible M * N matrix values, depending on just the row and column sums, in polynomial time? For example, can one use those 6 red values in the picture to solve those 9 black values as a possible solution, in polynomial time? For a matrix of M * N values, there will be M + N sum values. M and N can be very large.

Thanks!

• Use max flow... Aug 10 at 6:01
• Thank you. Could you give an example? Aug 10 at 7:17

It seems the following very simple algorithm works as long as $$\sum_x \text{row}[x]= \sum_y \text{col}[y]$$:

for x in 1..N:
for y in 1..M:
take = min(row[x],col[y])
row[x] -= take
col[y] -= take
m[x][y] = take


Indeed the invariant $$\sum_x \text{row}[x]= \sum_y \text{col}[y]$$ is preserved after each iteration of the loop and when the inner loop is finished for some $$x$$ we can see that row$$[x]=0$$ which means (by invariant) that when the outer loop is finished we have $$\sum_y \text{col}[y]=0$$.

In the case of negative numbers we can get back to non-negative numbers by virtually adding some constant $$c$$ to all matrix cells (i.e. adding $$cN$$ to all columns and $$cM$$ to all rows).

Note that if $$\sum_x \text{row}[x] \neq \sum_y \text{col}[y]$$ then the problem is unsolvable.

• Well if the numbers are not required to be nonnegative, the problem is much simpler: you can put e.g. $m[y]=col[y]$ for $y\ge2$, $m[x]=row[x]$ for $x\ge2$, assign whatever is left to $m$, and leave the remaining entries as $0$. Aug 10 at 9:45
• Yes, indeed, that works :) Aug 10 at 13:10
• Thank you Louis and Emil for your answer! Yes, negative answers are allowed and the condition ∑𝑥row[𝑥] = ∑𝑦col[𝑦] is not required. It seems then this is an NP problem. Aug 10 at 19:49
• It is not an NP problem because it is not a decision problem. If you were asking "is there a solution given row and col?" then it would be a decision problem and that decision problem would be in P because you just have to check that Σrow=Σcol (and since P is a subset of NP then it would be in NP but I suppose that was not what you meant). Aug 11 at 8:32
• Oh I see. Indeed, I revisited the definition of NP problems and they say "NP is the set of decision problems". And yes, my question is not a decision problem. Thank you again! Aug 11 at 18:46