Need an algorithm to make all rows and columns have non-negative sums

Question

I'm trying to figure out this problem. I have a matrix with integer values. The goal is to get it so that every row sum and every column sum is non-negative. The only things I can do are change the signs of an entire row or an entire column.

Here's what I've tried. I look for a row or column with negative sum, and I flip it. This works on all the examples that I tried, but now I have to explain why, and I'm not sure. Sometimes when I do this the number of negative sums goes up, like when I flip a row, sometimes there are more bad columns afterwards. But I can't find an example where this doesn't work, and I don't know how else to do the problem.

Answer 1

Flipping a row or column with negative sum is correct and will always lead to a situation where all rows and columns have nonnegative (not necessarily positive -- consider the all 0's matrix) sums.

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