Let $A$ be an $m \times n$ matrix with real-valued entries such that the rows and columns sum up to integers. I wish to show that there exists a matrix $B$, with integer entries, such that $A$ and $B$ share the same row and column sums, and $|A_{i,j} – B_{i,j}| < 1$ for all $i,j$.
I tried various methods but none came to fruition. For instance, I tried to induct on $m + n$. The case where $m = 1$ or $n = 1$ is clearly trivial. The $2 \times 2$ case is also simple: We must have $A = \begin{pmatrix} a & r_1 – a \\ c_1 – a & r_2 – c_1 + a \end{pmatrix}$, where $r_1,c_1,r_2 \in \mathbb{Z}$ are integers. Then $B = \begin{pmatrix} \lfloor{a}\rfloor & r_1 – \lfloor{a}\rfloor \\ c_1 – \lfloor{a}\rfloor & r_2 – c_1 + \lfloor{a}\rfloor \end{pmatrix}$ does the trick.
Given an $(m + 1) \times n$ matrix $A$, I considered:
$$
A_{i,j}' :=
\begin{cases}
A_{i,j}, &\text{if $i < m$} \\
A_{m,j} + A_{m+1,j}, &\text{if $i = m$}
\end{cases}
$$
Then $A'$ is an $m \times n$ matrix, so by induction hypothesis, we may approximate it with some integer-valued $m \times n$ matrix $B$. However, I'm not sure how to proceed from there onwards.
Best Answer
(1) The result:
For any matrix $C=(c_{ij})\in \mathbb R^{m\times n}$, we denote $$C_i=\sum_k c_{ik},\quad C^j=\sum_k c_{kj}.$$
Let $A=(a_{ij})\in \mathbb R^{m\times n}$, with $A_i,A^j\in \mathbb Z$. Then there exists $B=(b_{ij})\in \mathbb Z^{m\times n}$, satisfying $B_i=A_i, B^j=A^j$ and $$|a_{ij}-b_{ij}|< 1.$$
(2) First, by deleting those rows and columns all of whose entries are integers, we may assume each row and column contains at least two non-integer entries.
(3) Consider the bipartite graph $\Gamma$ with $r_1,\ldots, r_m,c_1,\ldots, c_n$, with $r_i\sim c_j$ i.f.f $a_{ij}\notin \mathbb Z$. We see that $\Gamma$ is a bipartite graph with minimun degree $\geq 2$ by (2). Hence $\Gamma$ contains an even cycle $$r_{i_1}c_{j_1}r_{i_2}c_{j_2}\ldots r_{i_s}c_{j_s},$$ which corresponds to a sequence of even number of non-integer entries $$a_{i_1 j_1} a_{i_2 j_1}a_{i_2j_2}\ldots a_{i_1j_s}.$$
(4) Denote the index of entries in the cycle by $\Lambda$ and $d(x,\mathbb Z)=\min\{x-\lfloor x\rfloor,\lfloor x\rfloor+1-x\}$. We may assume $d(a_{i_1,j_1})=\min_{(i,j)\in \Lambda} d(a_{ij},\mathbb Z)=\epsilon$. Then by changing the entries in the cycle consecutively with $\pm \varepsilon$, we obtain a matrix with one more integer entry than $A$. The result follows by induction on the number of non-integer entries of $A$.