How to solve matrix inequation $Mx \leq 0$? While trying to model the relation between offers and exchanges in economics, I reached the point where I need to solve the following:
Given a fat real matrix $M$ (more columns than rows), find all vectors $x \geq 0$ such that $Mx \leq 0$. The inequalities apply to all elements.

Since the scale of the solution doesn't matter, I guess I could study just the positive region of the unit sphere (i.e., $x^\top x = 1, x \geq 0$).
My first thought was to separate $M$ into two parts: $M^+$ containing the positive elements and $M^-$ containing the negative elements: $M = M^+ - M^-$. So now the inequation is $M^+x \leq M^-x$. But it doesn't look like progress...
Any idea how to solve the inequation?
 A: Pick a solver and solve the following linear program
$$ \begin{array}{ll} \underset {{\bf x}} {\text{minimize}} & 0 \\ \text{subject to} & {\bf M} {\bf x} \leq {\bf 0} \\ & {\bf x} \geq {\bf 0} \end{array} $$
You may want to take a look at chapter 5 of Kroening & Strichman.
A: Edit: this only works if $M$ is onto, which I guess it isn't. So this might not be helpful.
If you quotient out the domain space by $kerM$ you get a (left) invertible linear map. Let's call this new map $M'$. Let the standard basis for the range be $e_i$ for $i \in \{1,...,m\}$. Then
$$-M'y\ge 0 \iff -M'y=\sum_{i=1}^{n}\lambda_ie_i : \lambda_i \ge 0$$
$$\iff y=\sum_{i=1}^{n}\lambda_iNe_i : \lambda_i \ge 0$$
where $N$ is the left inverse of $-M'$. So the set of $y$ such that $-M'y\ge 0$ is just the span of $Ne_i: i \in \{1,...,m\}$ over $\mathbb{R}_{\ge0}$. Thus the set of $x: -Mx \ge 0$ is just the preimage of this under the quotient map. Requiring $M$ to be onto: if you take  a preimage $v_i: i \in \{1,...,m\}$ such that the quotient of $v_i$ is $Ne_i$, then the set of $x$ such that $-Mx \ge 0$ can be described as $$kerM +span_{\mathbb{R}_{\ge 0}}\{v_1,...,v_m\}$$
The intersection of this with $\mathbb{R}_{\ge0}^n$ is then an alternative characterisation of the set you're interested in.
