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.

1more comment