We need an algorithm so that all rows and columns have non-negative sums

Question

I am trying to figure out this problem. I have a matrix with integer values. The goal is to get it so that each row sum and each column sum are non-negative. The only thing I can do is change the characters of the whole row or the whole column.

Here is what I have tried. I am looking for a row or column with a negative sum, and I flip it. This works on all the examples I tried, but now I have to explain why, and I'm not sure. Sometimes, when I do this, the number of negative sums increases, for example, when I turn the line, sometimes worse columns appear after that. But I can not find an example where this does not work, and I do not know how to do it.

Answer 1

Turning over a row or column with a negative sum is correct and will always lead to a situation where all rows and columns have non-negative (not necessarily positive - take into account all 0 matrices) sums.

The problem is that you should not keep track of how many rows or columns you need to flip, but what is the sum of all the records. Let A be the matrix, a be the sum of all records. When you flip a row or column with the sum of -s (s is positive), then this adds 2s to a. Since a is bounded above, this process should ultimately end.

Answer 2

Suppose you have a string of integers, a, b, c ... etc.

If a + b + c + ... = n, then, turning all the signs over, you get

(- a) + (-b) + (-c) + (-)... = - (a + b + c +...) = -n

n , -n , , . , .

, ?