7
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ please edit in your proof for the 2 by 2 case $\endgroup$
    – Will Jagy
    Feb 3 at 1:18
  • 1
    $\begingroup$ @WillJagy I've added the $2 \times 2$ case. $\endgroup$
    – ilovecats
    Feb 3 at 1:32
  • 1
    $\begingroup$ Some ideas here might help reader.elsevier.com/reader/sd/pii/… $\endgroup$ Feb 3 at 1:42
  • 1
    $\begingroup$ The problem with all flooring is that error in row and column sum accumulates. So if you keep track of errors in row and column sum and do ceil and floor ? This seems more natural to do. $\endgroup$
    – Balaji sb
    Feb 3 at 2:08
  • $\begingroup$ Appears not too bad for the case when all entries are rational, let $M$ denote the least common denominator, multiply through by $M$ and force the entries to become $0 \pmod M$ $\endgroup$
    – Will Jagy
    Feb 3 at 2:12

1 Answer 1

11
$\begingroup$

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

$\endgroup$
8
  • 2
    $\begingroup$ +1 beautiful answer. $\endgroup$
    – Balaji sb
    Feb 3 at 3:44
  • 1
    $\begingroup$ A slight tweak which I think makes the procedure a little clearer: you can drop step (2), and modify step (3) to say “$\Gamma$ is a bipartite graph with no elements of degree 1. Hence either it is discrete, meaning all entries are integers and we’re done, or else it contains an even cycle…” This way you’re just modifying entries at each step, never changing the shape of the matrix, so it’s easier to compare the matrices in successive steps, and see how the procedure converges directly to the desired integer replacement. $\endgroup$ Feb 3 at 13:03
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine In each step, we only change the (non-integer) entries in the cycle, and we choose the minimial error to change, so we do not jump any integer. In the next step, we choose a new cycle with new error. We do not jump any integer in each step. $\endgroup$
    – stlinex
    Feb 3 at 13:06
  • 2
    $\begingroup$ @stlinex: Yes, I agree your procedure works! But that property “we do not jump any integer” is crucial, and needs to be included to make the proof work — I’d suggest by putting it into the claim at the start. This seems like a classic “strengthening the induction hypothesis” example. $\endgroup$ Feb 3 at 13:14
  • 1
    $\begingroup$ Since shifting the value of an entry by an integer doesn't change anything, we could start by adding an integer to each entry so that they are all in $[0,1]$. Then the notion of "not jumping any integers" is just "keeping all entries in the range $[0,1]$" which is a bit easier to intuit. $\endgroup$
    – Carmeister
    Feb 3 at 15:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .