  The authors and Fischer recently proved that any hereditary property of
two-dimensional matrices (where the row and column order is not ignored) over a
finite alphabet is testable with a constant number of queries, by establishing
the following (ordered) matrix removal lemma: For any finite alphabet $\Sigma$,
any hereditary property $\mathcal{P}$ of matrices over $\Sigma$, and any
$\epsilon > 0$, there exists $f_{\mathcal{P}}(\epsilon)$ such that for any
matrix $M$ over $\Sigma$ that is $\epsilon$-far from satisfying $\mathcal{P}$,
most of the $f_{\mathcal{P}}(\epsilon) \times f_{\mathcal{P}}(\epsilon)$
submatrices of $M$ do not satisfy $\mathcal{P}$. Here being $\epsilon$-far from
$\mathcal{P}$ means that one needs to modify at least an $\epsilon$-fraction of
the entries of $M$ to make it satisfy $\mathcal{P}$.
  However, in the above general removal lemma, $f_{\mathcal{P}}(\epsilon)$
grows very fast as a function of $\epsilon^{-1}$, even when $\mathcal{P}$ is
characterized by a single forbidden submatrix. In this work we establish much
more efficient removal lemmas for several special cases of the above problem.
In particular, we show the following: For any fixed $s \times t$ binary matrix
$A$ and any $\epsilon > 0$ there exists $\delta > 0$ polynomial in $\epsilon$,
such that for any binary matrix $M$ in which less than a $\delta$-fraction of
the $s \times t$ submatrices are equal to $A$, there exists a set of less than
an $\epsilon$-fraction of the entries of $M$ that intersects every $A$-copy in
$M$.
  We generalize the work of Alon, Fischer and Newman [SICOMP'07] and make
progress towards proving one of their conjectures. The proofs combine their
efficient conditional regularity lemma for matrices with additional
combinatorial and probabilistic ideas.
