# Submatrix with small sum of elements

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

• Do you want to assume the entries of A are positive? Commented Nov 11, 2016 at 4:02
• For the latin square you mention, any $m \times m$ submatrix will have sum at least $m \times (1 + 2 + \cdots + m) \sim m^3 /2$ and at most $m\times (n + (n-1) + \cdots + (n-m+1)) \sim m^2 (2n-m)/2$. So if $m \approx n$ then all $m \times m$ submatrices would have roughly the same sum. Commented Nov 11, 2016 at 4:09
• Yes, the entries of A are positive. Commented Nov 11, 2016 at 10:47
• @Pat Devlin: I think of m somewhat near n, but smaller by a factor exceeding any constant (as $n \to \infty$). Say $m = n/\log \log n$ or $m = n/\log n$. Then there clearly is a gap between the upper and lower bound in your calculation, and I would like to know what one can achieve. Commented Nov 11, 2016 at 10:50
• What about just taking a random submatrix? There you get sum $m^2 n/2$, which is within a factor of 2 of the maximum possible. No good? Commented Nov 11, 2016 at 18:46

Given

• a positive $$n \times n$$ real matrix $$\mathrm A$$
• a positive integer $$m < n$$

we would like to select $$m$$ rows and $$m$$ columns of $$\mathrm A$$ such that the sum of the (positive) entries of the selected submatrix is minimal.

Let $$\mathrm x, \mathrm y \in \{0,1\}^n$$ be the decision vectors. If $$x_i = 1$$, then the $$i$$-th row of $$\mathrm A$$ is selected. If $$y_j = 1$$, then the $$j$$-th column of $$\mathrm A$$ is selected. Thus, the selected entries of $$\mathrm A$$ are indicated by matrix $$\mathrm x \mathrm y^{\top}$$.

The sum of these $$m^2$$ selected entries is

$$\langle \mathrm A, \mathrm x \mathrm y^{\top} \rangle = \mbox{tr} \left( \mathrm A^{\top} \mathrm x \mathrm y^{\top} \right) = \mbox{tr} \left( \mathrm y^{\top} \mathrm A^{\top} \mathrm x \right) = \mbox{tr} \left( \mathrm x^{\top} \mathrm A \,\mathrm y \right) = \mathrm x^{\top} \mathrm A \,\mathrm y$$

Since we want to select $$m$$ rows and $$m$$ columns, we have two equality constraints

$$1_n^{\top} \mathrm x = m \qquad \qquad \qquad 1_n^{\top} \mathrm y = m$$

Thus, we have the following equality-constrained binary bilinear program

$$\begin{array}{ll} \text{minimize} & \mathrm x^{\top} \mathrm A \,\mathrm y\\ \text{subject to} & 1_n^{\top} \mathrm x = m\\ & 1_n^{\top} \mathrm y = m\\ & \mathrm x, \mathrm y \in \{0,1\}^n\end{array}$$

which can be rewritten as the following equality-constrained binary quadratic program (BQP)

$$\begin{array}{ll} \text{minimize} & \frac 12 \begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix}^{\top} \begin{bmatrix} \mathrm O_n & \mathrm A\\ \mathrm A ^{\top} & \mathrm O_n\end{bmatrix} \begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix}\\ \text{subject to} & 1_n^{\top} \mathrm x = m\\ & 1_n^{\top} \mathrm y = m\\ & \mathrm x, \mathrm y \in \{0,1\}^n\end{array}$$

Bicliques

From a graph-theoretic viewpoint, the following $$2n \times 2n$$ matrix

$$\begin{bmatrix} \mathrm O_n & \mathrm A\\ \mathrm A ^{\top} & \mathrm O_n\end{bmatrix}$$

is the adjacency matrix of a balanced, weighted bipartite graph (bigraph) with $$2n$$ vertices. Since matrix $$\mathrm A$$ is positive, we have a complete bipartite graph, i.e., a biclique. Hence, the original problem of finding an $$m \times m$$ submatrix of $$\mathrm A$$ whose sum is minimal can be reduced to the following combinatorial optimization problem:

Given

• a balanced, weighted biclique with $$2n$$ vertices
• a positive integer $$m < n$$

find a balanced sub-biclique with $$2m$$ vertices and whose weight is minimal.

Perhaps this problem has been studied already. I found a number of papers on biclique covers, which is a different problem.