3

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?

Rodrigo de Azevedo
  • 1
Amenhotep
  • 183
  • 2
    Sorry, but this is not a do my homework for me site. Please edit your post to show an attempt. – cpiegore Feb 18 '23 at 23:18
  • 3
    @cpiegore I don't understand why you think this is homework. It is not. I am not a student (do I look like one?). I am just trying to model something in economics and my calculations got me to this point. I don't know how to solve it. If you know, please tell me. – Amenhotep Feb 18 '23 at 23:42
  • 1
    If this is not the right site to ask, I would appreciate if you could direct me to such a site where people who know linear algebra could assist me. Thank you. – Amenhotep Feb 18 '23 at 23:52
  • 1
    Please add more details. – CroCo Feb 19 '23 at 00:25
  • 1
    To say this in another way: Given $M\in \mathbb{R}^{m\times n}$, find all vectors in $\mathbb{R}+^n$ such that $-Mx\in \mathbb{R}+^m$. With that in mind, you may be best off thinking about how to find the inverse image of $\mathbb{R}+^m$ under $M$. Once you have this, intersecting with $\mathbb{R}+^n$ will give the desired subset. – Semiclassical Feb 19 '23 at 00:27
  • 1
    Note that there are matrices $M$ for which there is no $x\ge0$ with $Mx\le0$, other than the zero vector, $x=0$. – Gerry Myerson Feb 19 '23 at 00:38
  • @GerryMyerson Yes, indeed. My problem is to first see if there are any nontrivial solutions (maybe they aren't), and then, if they exist, to find them. – Amenhotep Feb 19 '23 at 00:50
  • @Semiclassical Thank you, this is a very good reformulation. I will think about how to find the inverse image. Maybe using the pseudoinverse? But I don't think so... SVD decomposition? I will try that and see where it gets me. Or maybe rref?... – Amenhotep Feb 19 '23 at 00:54
  • 2
    The rules of this website require you to either show your own work/thoughts on a problem, or provide other context, such as where the problem is from. This rule is specifically meant to combat students asking others to do homework for them, but applies equally to everyone. If you encountered this problem while trying to model something in economics, I encourage you to edit that info into your question, and be specific about it. This might help get rid of some of the downvotes, and make others more inclined to answer. Good luck. : ) – Christian E. Ramirez Feb 19 '23 at 01:27
  • 1
    What form do you want the answer to be in? because the inequalities you give are already a pretty neat description of the set you're looking for. Would it be enough to find a neater description of the preimage of the negative vectors under $M$, and say the solution is the intersection of this with the set where $x\ge 0$? – Zoe Allen Feb 19 '23 at 08:43
  • @ZoeAllen A very good question... I find myself torn between two approaches: the numeric/algorithmic one (which I'm more familiar with) and the purely mathematical view (which may allow me to advance theoretically, to prove things about my model). Since you are right that the formulation is pretty compact, I guess what I want is a characterisation of matrices $M$ that do not lead to solutions (other than $x = 0$). Then, for the $M$'s that have solutions, a method (algorithm) to explore the solution space. I am mainly interested in maximal $x$'s in the unit cube ($0 \leq x \leq 1$). – Amenhotep Feb 19 '23 at 08:59
  • What kind of characterisation are you looking for? as your description is already a characterisation of such matrices, of a sort. And 'a method to explore the solution space' is very vague. Could you translate what you are looking for into something more precisely formulated? do you want to be able to compute easily if an arbitrary matrix leads to solutions? or do you want to be able to prove theorems about the set of matrices that leads to solutions? it might help if you say what you are trying to do with this model in the first place. – Zoe Allen Feb 19 '23 at 09:08
  • @ZoeAllen I was looking for both. :) But either one would help. At this stage I am just exploring ideas with this model, so I am myself uncertain what I want. I apologise for the vagueness of the question... I can approach the problem numerically, but I hoped there were some mathematical insights that could help me prove things (I don't know what, I'm just exploring). – Amenhotep Feb 19 '23 at 09:38

2 Answers2

2

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.

Rodrigo de Azevedo
  • 1
  • Thank you for the suggestion. I will read the chapter about linear arithmetic. Indeed, it is a linear programming problem. I just hoped there existed a purely mathematical approach giving a neat characterisation of the solution space, that's why I asked here. But it seems there is not. So I will approach it numerically, as you suggest. – Amenhotep Feb 19 '23 at 09:23
  • The characterization is the set of linear inequalities. – Rodrigo de Azevedo Feb 19 '23 at 09:30
  • I hoped there is a mathematical condition for the matrices $M$ that don't lead to any solutions (apart form the trivial one). That would have helped me to not even start looking for a solution, if the solution space were just {0}. – Amenhotep Feb 19 '23 at 09:47
  • 1
    There might be. Have you tried using quantifier elimination? Do you have access to Mathematica? I once tried something of the sort and Mathematica did output a formula that I stored in a 100-page-long PDF file. That is Big Math, and it's not for humans – Rodrigo de Azevedo Feb 19 '23 at 09:53
  • 1
    Wow, quantifier elimination sounds very cool! I didn't know about it. Indeed, it's exactly what I am looking for. Thank you for the suggestion. – Amenhotep Feb 19 '23 at 10:20
2

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.

Zoe Allen
  • 4,380
  • Thank you, it seems to be what I need. Re the onto condition: If I understood correctly, a matrix is onto iff it has full row rank; so if my matrix has (many) more columns than rows, and the values are somehow random, it is probably onto, right? – Amenhotep Feb 19 '23 at 13:35
  • To "quotient out the domain space by $ker M$" means to find a left inverse of $ker M$ and multiply $M$ on the left by that? I.e., find $X$ such that $X ker M = I$ and then put $M^\prime = XM$? – Amenhotep Feb 19 '23 at 13:40
  • @Amenhotep yes, onto just means full row rank, so 'almost all' matrices with columns $\ge$ rows will have be onto. – Zoe Allen Feb 19 '23 at 22:40
  • 1
    @Amenhotep Are you familiar with the construction of a quotient space? if $M$ is $U \to V$ then $M'$ is the linear map $U/kerM \to V$ such that $[x] \mapsto Mx$. This is just a ways of getting rid of the difference between points that $M$ maps to the same point, so to turn $M$ into a left invertible linear map, $M'$. – Zoe Allen Feb 19 '23 at 22:45
  • No, I wasn't familiar with this. But now that you explained it, it makes sense. Thanks. :) – Amenhotep Feb 20 '23 at 20:32