5

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.

2
  • I think you mean "non-negative" here. Otherwise the zero matrix would fail to have a solution.
    – tskuzzy
    Jun 30, 2011 at 19:14
  • Ok, yes, that's what I meant. Jun 30, 2011 at 19:15

2 Answers 2

9

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.

3
  • Ok. I can write out a proof from this. Is there a way to pick the row or col to flip to make it go faster? Jun 30, 2011 at 19:57
  • Interesting question. I'm not sure. You may want to ask that as a separate question.
    – PengOne
    Jun 30, 2011 at 20:02
  • Actually, it's not too hard to show that you want to change the row/column with the most negative sum. This will result in the fewest moves.
    – PengOne
    Jun 30, 2011 at 20:10
0

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

If a + b + c + ... = n, then by flipping all the signs you get

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

If n is negative, then -n is positive, so you just made the row positive by flipping all signs. That's the math behind your method, at least.

Is this what you're looking for?

2
  • This is how I change one row, but I need all rows and columns fixed in the end. Jun 30, 2011 at 19:15
  • 1
    I think he already figured that out. What he wanted to know is how to prove that repeatedly flipping signs will eventually result in a matrix which has no rows or columns with negative sums. Jun 30, 2011 at 19:16

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.