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 $B$ of additional all-ones matrices, that I like to call target (b)oxes.
$$ \begin{matrix} Boxes: & \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, these specific boxes have 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 boxes in $B$. In other words, swapping rows between them, and/or columns between them so that any of the boxes of $B$ can be placed, for example, in the top left corner of $M$.
If there is more than one solution, the box of maximal height must be choosen, and if there's more than one solution of maximal height, then the one with maximal height and width.
The problem has the following properties:
- $2 \leq h \leq w$.
- Each row of $M$ has at least one $0$.
- Deduced from the way $B$ is generated, for each $b\in B$ of size $b_h\times b_w$, it happens that $b_h + b_w - 1 = w$.
Is there a way of solving this problem in polynomial time? Can any technique from lineal algebra or numerical characterization of matrices help to the problem?
