# Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

Crossposted at MathOverflow

A problem I study reduces to a system of linear equations $$A\mathbf{x}=\mathbf{1}$$ where $$A$$ is an $$m\times n$$ matrix with each entry $$a_{ij}\in\{0,1\}$$. $$\mathbf{1}$$ is the $$m$$-dimensional vector with all its coordinates being 1. The nature of the problem I study guarantees that there exists at least a solution $$\mathbf{x}\in[0,1]^n$$ for this system, which means that the polyhedron $$P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$$ is nonempty. I want to know what condition guarantees the existence of a 0-1 solution $$\mathbf{x}\in\{0,1\}^n$$ to this system.

I know that the unimodularity of $$A$$ is a sufficient condition, which has been useful for me. I also know the TDI condition in integer programming is sufficient, whereas I do not know how to make use of this condition. Both unimodularity and TDI guarantee that all vertices of polyhedron $$P$$ to be integral, thus I know there is at least a 0-1 solution (vertex), since the polyhedron is nonempty. However, all vertices being integral is more than I want, because I only care about whether there exists an integral vertex. I wonder whether there are more specialized results for this problem.

As pointed out by a helpful comment in MathOverflow, this problem is essentially equivalent to the EXACT SET COVER problem. I would now ask whether there is any condition or structure that guarantees the existence of an exact cover.