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.