We study a binary matrix transformation problem. One can see such a matrix as agrid where every cell contains a dot (the ones) or nothing (the zeros). It is possible to contract two neighbour lines or two neighbour columns by merging every couple of adjacent cells if and only if two dots are not merged in the same cell. In other words, two neighbour lines containing a 1 on the same column cannot be contracted, similarly two neighbour columns containing a 1 on the same line cannot be contracted.For instance, on the figure on the right, it is not possible to merge the first line with the second one of the matrix M1. On the other hand, as it is done on the Figure, we can contract columns 1 and 2, then lines 2 and 3 in order to obtain the matrix M3.
The objective is to contract the matrix as much as possible. We measure the contraction of the matrix with its density: the number of pairs of neighbour ones, including the diagonal pairs. For example, the density of the matrix M3 is 6. We search for a sequence of contractions of lines and columns that maximize the density of the resulting matrix.