A GENERAL-APPROACH TO AVOIDING 2 BY 2 SUBMATRICES

A matrix C is said to avoid a set F of matrices, if no matrix of F can be obtained by deleting some rows and columns of C. In this paper we consider the decision problem whether the rows and columns of a given matrix C can be permuted in such a way that the permuted matrix avoids all matrices of a given class F. At first an algorithm is stated for deciding whether C can be permuted such that it avoids a set F of 2 x 2 matrices. This approach leads to a polynomial time recognition algor ithm for algebraic Monge matrices fulfilling special properties. As ma in result of the paper it is shown that permuted Supnick matrices can be recognized in polynomial time. Moreover, we prove that the decision problem can be solved in polynomial time, if the set F is sufficientl y dense, and a sparse set of 2 x 2 matrices is exhibited for which the decision problem is NP-complete.