1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I'm studying this kind of problem. Did you find some literatures or something new about it? Thanks. $\endgroup$
    – Quy Nguyen
    Sep 22, 2020 at 7:48
  • $\begingroup$ Unfortunately, I did not find much on the topic apart from en.wikipedia.org/wiki/Alternating_sign_matrix $\endgroup$
    – Peter
    Sep 26, 2020 at 19:25

1 Answer 1

2
$\begingroup$

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)
$\endgroup$
3
  • $\begingroup$ Thanks a lot for pointing out helly's theorem and please excuse the vague question. My hope was that there is a literature studying matrices with entries only +1,-1,0 and additional properties. I came across alternating sign matrices which turned out to be useful for me: en.wikipedia.org/wiki/Alternating_sign_matrix $\endgroup$
    – Peter
    Jul 5, 2019 at 11:38
  • $\begingroup$ For $n>1$ the condition "$A$ has no negative entries" is not more general than the previous one ("$A$ is the identity matrix"). $\endgroup$ Mar 18, 2020 at 17:41
  • $\begingroup$ It could be some other permutation matrix $\endgroup$ Mar 18, 2020 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.