-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?

Improve this question
$\endgroup$
2
  • $\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
    Commented Apr 29, 2015 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
    Commented Apr 30, 2015 at 6:30

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Apr 29, 2015 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.