# 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? – Pat Devlin Nov 11 '16 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. – Pat Devlin Nov 11 '16 at 4:09
• Yes, the entries of A are positive. – Kurisuto Asutora Nov 11 '16 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. – Kurisuto Asutora Nov 11 '16 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? – Pat Devlin Nov 11 '16 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.