Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always make all row sums and column sums non-negative.
I am supposed to find an algorithm to prove this statement. Nevertheless, I tried induction on $m$ and $n$, but that did not work out well.
My first instinct was to make all the row sums non-negative. Now, we start to make the column sums non-negative. Take the first column. Call it $C_1$. If it is already non-negative, then move on. If not, then switch the sign of every number in this column. Note that this might make some row sums negative. Let these rows be called $R_1,\cdots R_k$. Note that after the switch, $C_1\cap R_i$ must be a negative number. To see why this is so, simply assume to the contrary and note that if it were positive, the row sum of $R_i$ has increased from its previous value, and hence can't be negative. So switch all the $R_i$. Clearly, this makes all the rows non-negative again. $C_1$ also remains non-negative, because switching all the rows turn the $C_1\cap R_i$ into positive numbers, and hence the column sum of $C_1$ increases, and hence remains non-negative.
I have also figured out an algorithm to turn the second row non-negative without altering any of the rows or the first column, but I am stuck here.
I also thought about using the extremal principle. Simply consider the configuration of the board which maximizes the number of positive rows and columns, but I haven't been able to proceed.
Any help will be appreciated.
Best Answer
Say you have a column $C_i$ with negative sum, and you change the sign of all elements in that column. This must increase the total sum of all the elements in the grid (hereby just called the "total sum"), since all the other columns are unaffected, and the sum of all the column sums is the same as the total sum. The same thing goes for rows, of course.
There are only finitely many different total sums that can be made with the numbers on the board by changing the signs, even if you could freely change the signs of single elements. As long as there is a row or column with negative sum, you can increase the total sum, and increasing the total sum can be done only finitely many times. That means that the algorithm "Find a row or column with negative sum and flip the signs in it, then repeat" must end after a finite number of repeats.