2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Do you want to assume the entries of A are positive? $\endgroup$ – Pat Devlin Nov 11 '16 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 Nov 11 '16 at 4:09
  • 1
    $\begingroup$ Yes, the entries of A are positive. $\endgroup$ – Kurisuto Asutora Nov 11 '16 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$ – Kurisuto Asutora Nov 11 '16 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 Nov 11 '16 at 18:46
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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