On the hardness of efficiently approximating maximal non-L submatrices

AbstractThe sign pattern of a real matrix A is the matrix obtained by replacing each entry of A by its sign. A real matrix A is an L-matrix if every real matrix with the same sign pattern as A has linearly independent columns. L-matrices arise naturally in and are essential to the study of sign-solvability and related notions. In special cases, the L-matrix property has connections to the even dicycle problem, Pfaffian orientations, and Pólya’s permanent problem. Unfortunately, the problem of recognizing L-matrices is known to be co-NP-complete in general. We elaborate in this vein by showing a polynomial-time inapproximability result for Max-not-L-rows, a particular optimization version of L-matrix recognition, by means of an approximation-preserving reduction from the previously studied problem Max-not-equal-2-Sat