# Finding a boolean submatrix isomorphic to a specific set of other boolean matrices

Given a matrix $$M$$ of certain size $$h\times w$$, where $$h\leq w$$, for example $$5\times 6$$, are also given the following set $$A$$ of (a)dditional matrices:

$$\begin{matrix} Matrices: & \begin{bmatrix} % 2 x 5 1 & 1 & 1 & 1 & 1\ 1 & 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 3 x 4 1 & 1 & 1 & 1\ 1 & 1 & 1 & 1\ 1 & 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 4 x 3 1 & 1 & 1\ 1 & 1 & 1\ 1 & 1 & 1\ 1 & 1 & 1 \end{bmatrix} & \begin{bmatrix} % 5 x 2 1 & 1\ 1 & 1\ 1 & 1\ 1 & 1\ 1 & 1 \end{bmatrix}\ Sizes: & 2 \times w – 1 & 3 \times w – 2 & 4\times w – 3 & 5\times w – 4 \end{matrix}$$

As you can see, this specific set of matrices follows the pattern of containing only $$1$$s, with sizes starting from $$2\times w – 1$$ up to $$h\times w – h + 1$$.

The problem is finding a submatrix of $$M$$ that is isomorphic with any of the matrices in the set $$A$$. In case there is more than one solution, the result is any submatrix of maximum height first, and in case there’s again multiple candidates, any submatrix with maximum width.

The problem have the following properties:

• $$2 \leq h \leq w$$.
• Each row of $$M$$ has at least one $$0$$.
• Deduced from the way $$A$$ is generated, for each $$a\in A$$ of size $$a_h\times a_w$$, it happens that $$a_h + a_w – 1 = w$$.
• The operations you can apply to $$M$$ to check for homomorphism are the usual ones, you can swap rows between them, or columns betweem them, but you cannot sum or substract rows or columns between them as in lineal algebra.

I have spend already a couple of days trying to construct a polynomial-time algorithm for this problem but I don’t see it clearly. Is this problem NP-hard, taking into account all of the restrictions it has?

I’m looking for any strategy that implies to "normalize" $$M$$ by applying a set of row or column swapping in a way that, in case there’s a solution, it’s in the "top left" corner of $$M$$. I have also explore the possibility of using the rank of $$M$$ to see if there’s some pattern regarding its potential solution, etc. I have also try to sort the columns and rows by number of $$1$$s and that kind of things, but my background on lineal algebra in very limited, and so it is my set of mathematical "tricks" to characterize $$M$$ regarding $$A$$.

NOTE: The maximum subarray problem is similar to this one, but take notice that my best solution is not neccesarily the maximum one. If, for example, the solution submatrices of size $$3\times 4$$ and $$5\times 2$$ exists, the "best solution" is $$5\times 2$$, because it has a bigger height, although it’s has less number of $$1$$s.

NOTE: The graph homomorphism problem is also similar, but take notice that $$M$$ is not equivalent to an adjacency matrix because it’s not square or symmetrical.

Posted on Categories proxies