Maximize the number of non zero elements of a product of binary matrices.

Question

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that:

1. $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$)
2. The number of non-zero elements of $C$ is maximal.

where $N, M$ are given (around 1000) with $N>M$. By binary matrices I mean $a_{ij}, b_{ij} \in \{0,1\}$, but the multiplication is the usual matrix multiplication over $\mathbb{R}$, ie $0\leq c_{ij}\leq M$. This is a real life problem, not an exercise, so I'm not sure there is a simple solution.

Any idea how to solve this? Any pointers? I'm not necessarily looking for the global optimum, a simple heuristic would be enough.

Some ideas I have:

• I have a way to find matrices $A$ and $B$ that satisfy 1. Let $x$ be a vector with $M$ elements and let $A_{ij} = \delta(x_j < i)$ and $B_{ij} = \delta(x_i \geq j)$. Then $AB=C$ is strictly lower triangular because $c_{ij}=\sum_k \delta(x_k< i)\delta(x_k \geq j)$. But I'm not sure that for any $C$ satisfying 1) there exists a corresponding $x$, and I'm not sure how to choose $x$ to satisfy 2).
• I think there might be a graph theoretic interpretation of this problem, viewing $A$ and $B$ as adjacency matrices.

Thanks

Answer 1

For each $m = 1 \ldots M$, let $g(m) = \min\{i:a_{im} = 1\}$ and $h(m) = \max \{j: b_{mj} = 1\}$. In order for $C$ to be strictly lower triangular, what we need is $g(m) > h(m)$. We may as well take $h(m) = g(m) - 1$, and assume $a_{im} = 1$ for all $i \ge g(m)$ and $b_{mj} = 1$ for all $j\le h(m)$. Then $c_{ij} > 0$ iff there is $m$ such that $i \ge g(m) > j$. We may assume the $g(m)$ are all distinct, and partition $\{1, \ldots, N\}$ into $M+1$ intervals. We want to maximize the number of pairs $(i,j)$ for which $i$ and $j$ are in different classes, which is equivalent to minimizing the sum of the squares of the cardinalities of the classes (i.e. the number of pairs for which $i$ and $j$ are in the same class). Thus the problem is equivalent to: $$ \eqalign {\text{Minimize} & \sum_{i=0}^{M} x_i^2\cr \text{subject to} & \sum_{i=0}^{M} x_i = N\cr & x_i \ge 0 \ \text{integers}\cr}$$

If $N = a(M+1) + b$, $a$ and $b$ integers with $0 \le b \le M$, the solution to this is to have $M-b+1$ values $x_i = a$, and $b$ values $x_i=a+1$.