Nonnegative Sums of Rows and Columns

For any $ n\times n$ matrix $ A$ with real entries, is it possible to make the sum of each row and each column nonnegative just by multiplying rows and columns by $ -1$? In other words, you are allowed to multiply any row or column by $ -1$ and repeat a finite number of times.

My fellow office mate Kirill, who also has a math blog, gave me this problem a few weeks ago and I thought about it for a few minutes here and there. The solution is in the fourth paragraph, so if you’d like to think about it yourself stop here before you get close.

Today solved this problem, but I find it interesting that before finding the solution I tried all sorts of bizarre things: looking at the quotient of all $ n\times n$ matrix under the group action corresponding to multiplying rows and columns by $ -1$, reducing the problem to integer matrices and thus to an action on $ \mathbb{Z}^{n^2}$, and other attempts that were equally futile. Perhaps this just goes to show that even with the increasing amount of advanced knowledge saturating my brain, elementary attempts are no less worthwhile.

The Solution

The solution is actually quite simple: if there is some row or column that has a negative sum, multiply it by $ -1$, and continue. This process eventually terminates with the sum of rows and columns all nonnegative because each time a sum is changed from negative to positive, it strictly increases the sum of all the entries, and this sum is bounded above.

Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.