Signs in a Matrix

Given a rectangular array of real numbers, prove that by changing signs in a row or a column at a time it is possible to make sums of all elements in individual columns and rows all non-negative.

(In the applet, to reverse the signs in a column click on the sum of its elements just beneath it. The sums of elements in rows serve the same purpose - they are also clickable - and are located to the right of the matrix.)

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

What if applet does not run?

You may not need the applet to realize that the problem may not be very challenging, but applet suggests a solution. A click on a negative sum of row elements will make it positive by reversing the signs of elements in this row. However, this operation may cause new negative sums in some columns. Clicking on negative column sums may create new negative row sums. And so on... It is not obvious that the process will ay all end. Playing with the applet, one is bound to discover that it always does. The question is why?

References

P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, pp.77-79

Whenever the signs of elements in a row (or in a column) are reversed, the sum of all elements of the matrix change by twice the sum of the elements in that row (column). Thus, clicking on negative sums, will cause the sum of all elements to grow. If the matrix has dimensions n×m, all in all its elements taken with different signs may form at most 2^{m + n} sums. The number may be big, but is finite. Thus the operation (of clicking on negative sums) that causes the total sum of all elements to grow is bound to terminate. At which time, all the individual sums will have to be non-negative.

71544411