1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – joriki Jun 29 '16 at 22:54
  • $\begingroup$ I have clarified the question: multiplication is over $\mathbb{R}$ and near optimal solution is good enough for me. Thanks $\endgroup$ – user1188374 Jun 29 '16 at 23:13
  • $\begingroup$ 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... $\endgroup$ – joriki Jun 29 '16 at 23:38
  • $\begingroup$ ... 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. $\endgroup$ – joriki Jun 29 '16 at 23:38
  • 1
    $\begingroup$ Thanks for taking the time to think about this! You had it but Robert posted the full proof first so I accepted his answer. $\endgroup$ – user1188374 Jun 30 '16 at 1:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great -- this is a more rigorous version of what I was saying in the comments. $\endgroup$ – joriki Jun 30 '16 at 0:25
  • $\begingroup$ Thank you very much for the detailed demo! That works! $\endgroup$ – user1188374 Jun 30 '16 at 0:59

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.