Sufficient conditions for a system of linear inequalities to admit a solution

Question

I am looking for sufficient conditions such that a system of linear inequalities of the type $A x >0$ admits a non-negative solution $x \in \mathbb{R}^n_+$. I know a few properties of the $m \times n$ matrix $A$

1. All entries are either $0,1$ or $-1$.
2. For each row $i$ there exists at least one column $j$ such that $A_{ij}=1$.
3. There exists at least one column $j$ such that $\sum_{i} A_{ij}=1$.

Do you know of any literature that studies sufficient conditions of this type?

Answer 1

Here are some unsatisfying sufficient conditions followed by an interesting one.

• $A$ is the identity matrix $I_n.$
• $A$ has no negative entries.
• Each row has a positive sum.
• There is a list of non-negative weights $x_1,\cdots ,x_n$ such that the weighted sum of each row is positive $\sum_1^nx_i a_{ij} \gt 0.$

Each condition is more general than the previous ones. The last condition is both sufficient and necessary. This because it simply restates the desired property.

So what kind of condition do you seek?

Let me remove the non-negativity condition and instead place the $n$ rows of $I_n$ at the top to get an $(n+m) \times n$ matrix $A^*$ with the condition $A^*x\geq 0$ with any $0$ entries among the top $n.$

Each inequality determines a half space in $\mathbb{R}^n$ closed for the first $n$ and open for the rest. The question is if their intersection is non-empty.

Helly’s Theorem states that given $t \gt n$ convex sets in $\mathbb{R}^n$ , if every $n+1$ of them have non-empty intersection then all $t$ do. So this is also a necessary and sufficient condition.

In this case we can reduce to requiring that any $n$ of them can be simultaneously satisfied: Scaling by a positive factor does not change anything so we can restrict to vectors $x$ which have $\sum x_i=1$. These belong to a set which is essentially $R^{n-1}$

If I have it right, the condition is thus that of the original $m$ inequalities,

• any one can be satisfied with at most one negative entry
• any pair can be satisfied with at most two negative entries
• etc.
• any $n$ can be satisfied by some vector ( no restrictions on signs)