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

  • 1
    $\begingroup$ Do you want to assume the entries of A are positive? $\endgroup$
    – Pat Devlin
    Commented Nov 11, 2016 at 4:02
  • $\begingroup$ 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. $\endgroup$
    – Pat Devlin
    Commented Nov 11, 2016 at 4:09
  • 1
    $\begingroup$ Yes, the entries of A are positive. $\endgroup$ Commented Nov 11, 2016 at 10:47
  • $\begingroup$ @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. $\endgroup$ Commented Nov 11, 2016 at 10:50
  • $\begingroup$ 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? $\endgroup$
    – Pat Devlin
    Commented Nov 11, 2016 at 18:46

1 Answer 1



  • 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}$$


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:


  • 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.