<p>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.</p>

<p>In general case I suppose you need low-rank approximation: <a href="http://en.wikipedia.org/wiki/Low-rank_approximation" rel="nofollow">http://en.wikipedia.org/wiki/Low-rank_approximation</a></p>

CC BY-SA 3.0
2015-04-29T16:59:50.427Z
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...
Niel de Beaudrap
CC BY-SA 3.0
2015-04-29T15:52:01.323Z
2015-04-29T15:52:01.323Z
Vsevolod Oparin
<p>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.</p>

<p>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.</p>

<p>\begin{array}{ccccc}
 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\
 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 \\
 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 \\
\end{array}</p>

<p>\begin{array}{ccccc}
 a &amp; a &amp; . &amp; . &amp; . \\
 a &amp; a &amp; . &amp; . &amp; . \\
 . &amp; . &amp; b &amp; b &amp; b \\
 . &amp; . &amp; b &amp; b &amp; b \\
\end{array}</p>

<p>Where <code>a</code> and <code>b</code> are the sought-for submatrices.</p>

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

<p>\begin{array}{ccccc}
 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
 0 &amp; 1 &amp; 1 &amp; 0 &amp; 1 \\
 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 \\
\end{array}</p>

<p>\begin{array}{ccccc}
 a &amp; . &amp; . &amp; 0 &amp; . \\
 . &amp; b &amp; b &amp; . &amp; b \\
 a &amp; . &amp; . &amp; a &amp; . \\
 . &amp; b &amp; 0 &amp; . &amp; b \\
\end{array}</p>

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

CC BY-SA 3.0
2015-04-29T18:34:11.320Z
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
CC BY-SA 3.0
2015-04-30T06:30:44.140Z
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
<matrices>
Find non-intersecting submatrices
Max
# Find non-intersecting submatrices

(Asked by: username_0 on 2015-04-29)

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?

**Tags:** matrices

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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?  

---

## 1 answers

### Answer by username_1 on 2015-04-29. Score: 0

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>

> **Comments:**
> **username_3**: 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...  

---

