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:  


*

*$AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies   
    C_{ij}=0$)

*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

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