0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice,+1. I should have thought about the fact that the sum is a monovariant quantity if at each stage we make the row sums and column sums non-negative. Btw, is the algorithm then "make all row sums positive. Now start making the column sums positive and at each stage, if the row sums become negative, then just apply the operation to make it positive. The process must terminate after finitely many steps." ? Thanks again for the answer. $\endgroup$ – rah4927 Aug 21 '15 at 10:24
  • $\begingroup$ @rah4927 That algorithm works too, but it takes more room to write down. $\endgroup$ – Arthur Aug 21 '15 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.