<p>It seems the following very simple algorithm works as long as <span class="math-container">$\sum_x \text{row}[x]= \sum_y \text{col}[y]$</span>:</p>
<pre><code>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
</code></pre>
<p>Indeed the invariant <span class="math-container">$\sum_x \text{row}[x]= \sum_y \text{col}[y]$</span> is preserved after each iteration of the loop and when the inner loop is finished for some <span class="math-container">$x$</span> we can see that row<span class="math-container">$[x]=0$</span> which means (by invariant) that when the outer loop is finished we have <span class="math-container">$\sum_y \text{col}[y]=0$</span>.</p>
<p>In the case of negative numbers we can get back to non-negative numbers by virtually adding some constant <span class="math-container">$c$</span> to all matrix cells (i.e. adding <span class="math-container">$cN$</span> to all columns and <span class="math-container">$cM$</span> to all rows).</p>
<p>Note that if <span class="math-container">$\sum_x \text{row}[x] \neq \sum_y \text{col}[y]$</span> then the problem is unsolvable.</p>

CC BY-SA 4.0
2022-08-10T09:45:01.323Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2022-08-10T13:10:13.277Z
Yes, indeed, that works :)
Louis
CC BY-SA 4.0
2022-08-10T19:49:31.317Z
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.
Hang Chen
CC BY-SA 4.0
2022-08-11T08:32:42.850Z
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).
Louis
CC BY-SA 4.0
2022-08-11T18:46:45.660Z
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!
Hang Chen
CC BY-SA 4.0
2022-08-10T08:27:20.063Z
2022-08-10T08:27:20.063Z
Louis
<p>I am given an M * N (M &gt; 1, N &gt; 1) matrix with all the numbers blackened but their row and column sums are visible.</p>
<p>For example, I am given this 3 * 3 matrix.</p>
<p><a href="https://i.sstatic.net/hdEvW.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/hdEvW.png" alt="enter image description here" /></a></p>
<p>And one of the possible matrix values are</p>
<p><a href="https://i.sstatic.net/0zJ3B.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0zJ3B.png" alt="enter image description here" /></a></p>
<p>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.</p>
<p>Thanks!</p>

CC BY-SA 4.0
2022-08-10T06:01:58.243Z
Use max flow...
Laakeri
CC BY-SA 4.0
2022-08-10T07:17:48.123Z
Thank you. Could you give an example?
Hang Chen
<matrices><np><polynomial-time>
Can one find any solution to this matrix problem in polynomial time?
Hang Chen
# Can one find any solution to this matrix problem in polynomial time?

(Asked by: username_0 on 2022-08-10)

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](https://i.sstatic.net/hdEvW.png)](https://i.sstatic.net/hdEvW.png)

And one of the possible matrix values are

[![enter image description here](https://i.sstatic.net/0zJ3B.png)](https://i.sstatic.net/0zJ3B.png)

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!

**Tags:** matrices, np, polynomial-time
> **Comments:**
> **username_1**: Use max flow...  
> **username_0**: Thank you. Could you give an example?  

---

## 1 answers

### Answer by username_2 on 2022-08-10. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_3**: 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$.  
> **username_2**: Yes, indeed, that works :)  
> **username_0**: 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.  
> **username_2**: 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).  
> **username_0**: 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!  

---

