# Find non-intersecting submatrices

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?

• 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? – Vsevolod Oparin Apr 29 '15 at 18:34
• 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? – Sasho Nikolov Apr 30 '15 at 6:30