Matrix approximation and Tusnády’s problem

We consider the problem of approximating a given matrix by an integer one such that in all geometric submatrices the sum of the entries does not change by much. We show that for all integers m,n≥2 and real matrices there is an integer matrix such that holds for all intervals I[m], J[n]. Such a matrix can be computed in time O(mnlog(min{m,n})). The result remains true if we add the requirement |aij−bij| <2 for all i[m],j[n]. This is surprising