This question is question 63 from Putnam and Beyond by Razvan Gelca and Titu Andreescu.
The entries of a matrix are real numbers of absolute value less than or equal to $1$, and the sum of the elements in each column is $0$. Prove that we can permute the elements of each column in such a way that the sum of the elements in each row will have absolute value less than or equal to $2$.
Suppose we have an $n \times m$ matrix. What I tried to do is to use the following method to arrange each columns. For the first column, arrange the entries in ascending order from top to bottom. For the next column, arrange the entries in descending order, so that you have maximal amount of 'cancelling out'.
Now, inductively arrange the rest of the columns. Suppose we have arranged the first $k$ columns. Compute the row sums of the first $k$ columns, call it $(r_1, \dots, r_n)$. Let the $(k+1)$-th column be $c_1, \dots, c_n$. Then we want to pair up the biggest $r_i$ with the smallest $c_j$, the second biggest $r_i$ with the second smallest $c_j$, and so on.
I tried this with a few small examples and it seems to work. But I am stuck trying to show that the absolute values of each row sum will not exceed $2$. Could anyone help me make some progress?
Thank you.