Submatrix with small sum of elements

Question

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

Answer 1

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.