My problem is in understanding the last part, when $(x_i -y_j)(a_{ij}-b_{ij})=0$. It is suppose to imply $(a_{ij}-b_{ij})=0$ but I don't know why it can't be $(x_i -y_j)=0$. Please help.
Lemma Let $x_1, x_2, \dots x_n$ and $y_1, y_2, \dots y_n$ be real numbers. Let $A = (a_{ij})$ be an $n \times n$ matrix with entries $$a_{ij} = \left\{ \begin{array}{l l} 1, & \textrm{if $x_i + y_j \ge 0$}\\ 0, & \textrm{else.} \end{array} \right.$$ Let $B = (b_{ij})$ be an $n \times n$ matrix with entries $0$ or $1$ such that the sum of elements of each row and each column of $B$ equals to the corresponding sum for the matrix $A$. Show that $A = B$.
Proof Let \begin{align} S &= \sum_{i=1}^n\sum_{j=1}^n(x_i+y_j)(a_{ij} - b_{ij})\\ &= \sum_{i=1}^n\sum_{j=1}^nx_i(a_{ij} - b_{ij}) + \sum_{i=1}^n\sum_{j=1}^n y_j(a_{ij} - b_{ij})\\ &= \sum_{i=1}^n x_i \sum_{j=1}^n(a_{ij} - b_{ij}) + \sum_{j=1}^n y_j\sum_{i=1}^n (a_{ij} - b_{ij}) = 0\\ \end{align}
because the row and column sums of $A$ and $B$ are the same.
On the other hand, using the definition of $a_{ij}$, we have
- When $x_i + y_j \ge 0$ the $a_{ij} - b_{ij} = 1 - b_{ij} \ge 0$
- When $x_i + y_j < 0$ the $a_{ij} - b_{ij} = - b_{ij} \le 0$
So, $(x_i + y_j)(a_{ij} - b_{ij}) \ge 0$ for all $i, j$. Since $S = 0$, then $(x_i + y_j)(a_{ij} - b_{ij}) = 0$ for all $i, j$, and $a_{ij} = b_{ij}$ for all $i, j$, and we are done.
$\square$
You are right. The proof is too short. Let $i$ be fixed and let $J = \{j : x_i+y_j= 0\}$. Then $a_{ij} = b_{ij}$ for all $j\notin J$. Therefore, $$ |J| = \sum_{j\in J}a_{ij} = \sum_ja_{ij} - \sum_{j\notin J}a_{ij} = \sum_jb_{ij} - \sum_{j\notin J}b_{ij} = \sum_{j\in J}b_{ij}. $$ Hence, $b_{ij} = a_{ij} = 1$ also for all $j\in J$. Listo! ;o)