-1
$\begingroup$

I have a rectangular boolean matrix and I'd like to have an efficient algorithm to find non-intersecting submatrices. I'll to demonstrate that in the example below.

The ideal case is when all elements are non-zero and rows and columns are happen to be in such an order that the submatrices all lie on the diagonal.

\begin{array}{ccccc} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ \end{array}

\begin{array}{ccccc} a & a & . & . & . \\ a & a & . & . & . \\ . & . & b & b & b \\ . & . & b & b & b \\ \end{array}

Where a and b are the sought-for submatrices.

The general case is when the rows and columns and not so fortunately arranged and not all elements in the submatrices are non-zero.

\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ \end{array}

\begin{array}{ccccc} a & . & . & 0 & . \\ . & b & b & . & b \\ a & . & . & a & . \\ . & b & 0 & . & b \\ \end{array}

There's probably a name for that decomposition/transformation but I couldn't find it by googling. Is there a name for that? And an efficient algorithm?

$\endgroup$
  • $\begingroup$ In the second example you have at least two measures of quality of solution: number of submatrices and number of mistakes. What kind of tradeoff between them do you expect? $\endgroup$ – Vsevolod Oparin Apr 29 '15 at 18:34
  • 1
    $\begingroup$ This is not a well-defined question. Do you want to find monochromatic submatrices? Do you want to partition the original matrix into the minimum number of monochromatic submatrices? $\endgroup$ – Sasho Nikolov Apr 30 '15 at 6:30
0
$\begingroup$

In the first case, if matrices can not have common rows and columns, you can just hash each row and try to select blocks of the same rows. If my assumption works for a beaten matrix you can use something like locality sensitive hashing.

In general case I suppose you need low-rank approximation: http://en.wikipedia.org/wiki/Low-rank_approximation

$\endgroup$
  • $\begingroup$ In the second example above, the matrix has the maximum possible rank of 4. Instances of this problem which are full rank are easy to create... $\endgroup$ – Niel de Beaudrap Apr 29 '15 at 16: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.