Problem

Source: Iran Third Round MO 1998, Exam 1, P3

Tags: linear algebra, matrix, linear algebra unsolved



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)$.