Consider the operation of multiplying any row or column of a real matrix by -1. Show that a finite number of such operations can transform any real matrix into a matrix with all row and column sums nonnegative.

Consider a m x n matrix A. Call the sum of the i-th row r_i(A), the sum of the j-th column c_j(A) and the sum of all matrix elements t(A).

Apparently we have

t(A) = r_1(A)+...+r_m(A) = c_1(A)+...+c_n(A)

This provides an easy algorithm for the transformation:

1. If we see a negative row sum r_i(A), we negate all entries in row i. This increases r_i(A), but keeps all other row sums at their current value. Therefore t(A) increases.

2. If we see a negative column sum c_j(A), we negate all entries in column j. Again, t(A) increases.

Because t(A) cannot increase forever, the algorithm must end eventually, at which point row and column sums are non-negative.

Posted by JLo on 2020-01-21 01:40:11