Let $A,B$ be two matrices with positive integer entries such that sum of entries of a row in $A$ is equal to sum of entries of the same row in $B$ and sum of entries of a column in $A$ is equal to sum of entries of the same column in $B$. Show that there exists a sequence of matrices $A_1,A_2,A_3,\cdots , A_n$ such that all entries of the matrix $A_i$ are positive integers and in the sequence \[A=A_0,A_1,A_2,A_3,\cdots , A_n=B,\] for each index $i$, there exist indexes $k,j,m,n$ such that \[\begin{array}{*{20}{c}} \\ {{A_{i + 1}} - {A_{i}} = } \end{array}\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} \quad \quad \ \ j& \ \ \ {k} \end{array}} \\ {\begin{array}{*{20}{c}} m \\ n \end{array}\left( {\begin{array}{*{20}{c}} { + 1}&{ - 1} \\ { - 1}&{ + 1} \end{array}} \right)} \end{array} \ \text{or} \ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} \quad \quad \ \ j& \ \ \ {k} \end{array}} \\ {\begin{array}{*{20}{c}} m \\ n \end{array}\left( {\begin{array}{*{20}{c}} { - 1}&{ + 1} \\ { + 1}&{ - 1} \end{array}} \right)} \end{array}.\] That is, all indices of ${A_{i + 1}} - {A_{i}}$ are zero, except the indices $(m,j), (m,k), (n,j)$, and $(n,k)$.
Problem
Source: Iran Third Round MO 1998, Exam 1, P3
Tags: linear algebra, matrix, linear algebra unsolved
16.07.2012 21:39
Nice problem, but this is not really matrix algebra. Matrices are just being used as tables of numbers here. For any $i$ and $j$, let $a_{i,j}$ denote the $\left(i,j\right)$-th entry of the matrix $A$, and let $\left(b_{i,j}\right)$ denote the $\left(i,j\right)$-th entry of the matrix $B$. We induce over $\sum\limits_{i,j}\left|a_{i,j}-b_{i,j}\right|$. As long as $\sum\limits_{i,j}\left|a_{i,j}-b_{i,j}\right|\neq 0$, we can find some $\left(u,v\right)$ such that $a_{u,v}>b_{u,v}$. Pick such $\left(u,v\right)$, and find some $w$ such that $a_{u,w}<b_{u,w}$ (such a $w$ exists since the sum of the $u$-th row of $A$ equals the sum of the $u$-th row of $B$, and thus the imbalance caused by $a_{u,v}>b_{u,v}$ has to be counteracted). Pick such $w$, and find some $t$ such that $a_{t,w}>b_{t,w}$ (such a $t$ exists since the sum of the $w$-th column of $A$ equals the sum of the $w$-th column of $B$, and thus the imbalance caused by $a_{u,w}<b_{u,w}$ has to be counteracted). Pick such $t$. Now, add $1$ to $a_{u,w}$ and $a_{t,v}$, and subtract $1$ from $a_{u,v}$ and $a_{t,w}$. This clearly can be obtained by addition of a matrix of the form \[\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} \quad \quad \ \ j& \ \ \ {k} \end{array}} \\ {\begin{array}{*{20}{c}} m \\ n \end{array}\left( {\begin{array}{*{20}{c}} { + 1}&{ - 1} \\ { - 1}&{ + 1} \end{array}} \right)} \end{array} \ \text{or} \ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} \quad \quad \ \ j& \ \ \ {k} \end{array}} \\ {\begin{array}{*{20}{c}} m \\ n \end{array}\left( {\begin{array}{*{20}{c}} { - 1}&{ + 1} \\ { + 1}&{ - 1} \end{array}} \right)} \end{array},\] and clearly lowers the sum $\sum\limits_{i,j}\left|a_{i,j}-b_{i,j}\right|$ by at least $2$. That's it, or where is the catch?