0
$\begingroup$

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.

enter image description here

And one of the possible matrix values are

enter image description here

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ Use max flow... $\endgroup$
    – Laakeri
    Commented Aug 10, 2022 at 6:01
  • $\begingroup$ Thank you. Could you give an example? $\endgroup$
    – Hang Chen
    Commented Aug 10, 2022 at 7:17

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Well if the numbers are not required to be nonnegative, the problem is much simpler: you can put e.g. $m[1][y]=col[y]$ for $y\ge2$, $m[x][1]=row[x]$ for $x\ge2$, assign whatever is left to $m[1][1]$, and leave the remaining entries as $0$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 10, 2022 at 9:45
  • $\begingroup$ Yes, indeed, that works :) $\endgroup$
    – Louis
    Commented Aug 10, 2022 at 13:10
  • $\begingroup$ 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. $\endgroup$
    – Hang Chen
    Commented Aug 10, 2022 at 19:49
  • 1
    $\begingroup$ 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). $\endgroup$
    – Louis
    Commented Aug 11, 2022 at 8:32
  • $\begingroup$ 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! $\endgroup$
    – Hang Chen
    Commented Aug 11, 2022 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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