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

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

• Is the multiplication over $\mathbb F_2$ (the field with two elements) or over $\mathbb R$? And are you interested only in the global optimum or also in a heuristic for a near-optimal solution? – joriki Jun 29 '16 at 22:54
• I have clarified the question: multiplication is over $\mathbb{R}$ and near optimal solution is good enough for me. Thanks – user1188374 Jun 29 '16 at 23:13
• To address your question whether there exists a corresponding $x$: Given $A$ and $B$ with $AB$ strictly lower-triangular, you can turn all zeros below a one in $A$ and all zeros to the left of a one in $B$ into ones without violating the condition and without decreasing the objective function. Then each column in $A$ and each row in $B$ is divided into an interval of zeros and an interval of ones. Then you can simultaneously reorder the columns of $A$ and the rows of $B$ such that the columns of $A$ are in order of decreasing number of $1$s... – joriki Jun 29 '16 at 23:38
• ... Now the rows of $A$ are also divided into an interval of zeros and an interval of ones, so you can turn all zeros below a one in $B$ into ones. Now both matrices have a staircase structure, and you can fill them up with ones until they "meet" at some vector $x$ as you described. That leaves only the choice of $x$ to worry about. – joriki Jun 29 '16 at 23:38
• Thanks for taking the time to think about this! You had it but Robert posted the full proof first so I accepted his answer. – user1188374 Jun 30 '16 at 1:00

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