Let $A$ be an $n \times n$ matrix, for which I know the size of the sum of all its entries. Now I want to select an $m \times m$-submatrix, whose sum of entries is as small as possible. Is there any result on how well I can do? (In my case, $A$ is symmetric)

Clearly, it will depend on some kind of irregularity of $A$. For example, if all entries of $A$ are ones, then the sum of elements is $n^2$, and any $m \times m$-submatrix will trivially have sum of elements $m^2$.

But what if, for example, $A$ is such that each row and each column has all the numbers $1, \dots, n$ in it. Then I can calculate the sum of elements, and use an averaging argument to show that there is a submatrix whose sum of elements is at least as good as average. However, is there a better result?

(For example, in the case of the matrix above, I can find a $1 \times 1$-submatrix whose sum of elements is 1, which is much better than average. But what for larger submatrices? In my application, I will rather need $m \approx n$ or $m \approx n/\log n$ and not a small fixed value of $m$.)