Htydjtk

I have a sparse non-symmetric binary matrix with a block structure. The dimensions of the matrix are thousands rows and less than one hundred columns.

How do I identify the largest non-contiguous rectangular sub-matrix consisting only of 1-entries?

Edit

The pattern is either very sparse, or there are very few large submatrices. However, the blocks are likely to overlap.

In the simplified example below, it would be elements {2, 4} towards {6, 6}.

$qquad mat=left( begin{array}{ccc}
1&1&1&1&0&0\
1&1&1&1&1&1\
0&0&0&1&1&1\
1&1&0&1&1&1\
1&1&1&1&1&1\
1&1&1&1&1&1\
end{array} right)$

A brute force approach:

mat = {{1, 1, 1, 1, 0, 0}, {1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 1, 1}, {1, 1, 0, 1, 1, 1}, 

   {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}};

pairs = Transpose /@ MaximalBy[DeleteDuplicates[CoordinateBounds /@ 

   Subsets[SparseArray[mat]["NonzeroPositions"], {2}]], 

     Min[#] Total[#, 2] &@mat[[## & @@ Span @@@ #]] &]

{{{2, 4}, {6, 6}}}

Update: This answer is not correct but for referencing, because the Subsets does not give all the possible slices of the matrix.

mat = {{1, 1, 1, 1, 0, 0}, {1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 1, 1}, {1,

    1, 0, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}};



mat//MatrixForm//TeXForm

$left(
begin{array}{cccccc}
1 & 1 & 1 & 1 & 0 & 0 \
1 & 1 & 1 & 1 & 1 & 1 \
0 & 0 & 0 & 1 & 1 & 1 \
1 & 1 & 0 & 1 & 1 & 1 \
1 & 1 & 1 & 1 & 1 & 1 \
1 & 1 & 1 & 1 & 1 & 1 \
end{array}
right)$

lst = Subsets@mat;



result = DeleteDuplicates@(MatrixForm /@ Select[lst, DeleteDuplicates@Flatten@# == {1} &]) // Sort;

result // TeXForm

$
left{left(
begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 & 1 \
end{array}
right),left(
begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 & 1 \
1 & 1 & 1 & 1 & 1 & 1 \
end{array}
right),left(
begin{array}{cccccc}
1 & 1 & 1 & 1 & 1 & 1 \
1 & 1 & 1 & 1 & 1 & 1 \
1 & 1 & 1 & 1 & 1 & 1 \
end{array}
right)right}
$

Is this ok? I'm not sure to apply Transpose to the last one of the result.

This can be solved by dynamic programing. is called monochromatic square.
Let you Matrix be T of size n*m.
you have to make build a second matrix L that has the same size as the first one fill with 0.
i, j the row and column coordinate respectively.

Then you start by the lower right triangle (i=n, j=m).
and you iterate from there :

if T[i,j] == 0 

   then L[i,j] = 0



else: 

    if T[i,j] == T[i+1,j] == T[i, j+1] == T[i+1, j+1] 

        then L[i,j] = 1 + min(L[i+1, j], L[i, j+1], L[i+1, j+1])

    else: L[i,j] = 1

at the end the maximal value of L will be the upper coordinate of the largest rectangle with only '1'

I am not a mathematician and it is my first answer so if I have forgot anything, feel free to ask for clarification or EDIT, also I can provides python code that does this.