An m x n array of real numbers has the sum of each row and column integral. Show that each non-integral element x can be changed to [x] or [x] + 1, so that the row and column sums are unchanged.
Solution
Start by replacing every non-integral element x by [x] and marking it -. Then, taking each column in turn, take enough elements which have been rounded down and round them up instead so that the column total becomes correct. Mark + each element which is rounded up. Now let S be the sum over the rows of the non-negative difference between the row sum and the desired row sum. Then S must be zero or positive and even. If S is non-zero, we show how to make a series of changes each of which reduces S by 2.
If S is non-zero, then at least one row must have its sum too high. Take such a row R1. It must contain an element E1marked +. The column through this element has the correct total, so it must have an element E2 marked -. Let R2 be the row containing this element. If R2's total is too low, then increasing E2 by 1 and reducing E1 by 1 will reduce S by 2. If R2's total is not too low, then it must contain another element E'2 marked +. The column containing this element has the correct total, so it must have another element E3 marked -. Now continue this process. If we eventually reach a row Rn with sum too low, then we can change all the Ei and E'i and hence reduce S by 2. Note that the sequence Ri may include the same row more than once. Suppose Ri = Rj and j > i. Then since the row total is not too low, we must still be able to find an element E'j marked + which is distinct from E'i. The same is true if the sequence includes Ri a third or fourth time. However, there are only finitely many elements available, so the sequence must eventually terminate. So we must eventually reach a row Rn with sum too low. Thus if S is non-zero, then we can always reduce it. Repeating, we must eventually get S zero and hence both row and column sums correct.
© John Scholes
jscholes@kalva.demon.co.uk
30 Aug 2002