I have some existence results using one modified version of the Farkas Lemma for which I need to solve the following problem. This problem has its application on economics but I will refer here merely to its mathematical part to avoid confusions (and no, this is not homework).
I have a matrix $A \in \{-1,0,1 \}^{n\times m}$ (is this notation right? I mean it takes values from $\{-1,0,1\}$ and which is of size $n\times m$) with $m \ggg n$ (lots of columns, for example think of it as $50\times1000$) such that for each row only one of the following conditions hold:
- all the numbers of the row are zeros and ones exclusively
- all the numbers of the row are zeros and minus ones exclusively
So that a possible example for $A$ is:
$$ A = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 \\ -1 & -1 & 0 & 0 & -1 \\ 1 & 0 & 0 & 1 & 0 \\ -1 & 0 & 0 &0 & 0 \end{pmatrix} $$
What I need to show is if there exists one $x\in\mathbb{R}^n$ such that $x$ has only non-negative coordinates (ie. $x\geq 0$) such that $x\cdot A = 0$ with the standard dot product. In particular, I want to distinguish two cases. If the only solution possible is $x=0$, or if there exists one solution for which at least one of the coordinates is different from zero. I am very, very interested in finding out if the second case is true. My aim is to explicitly show such $x$ if it exists.
I was using MATLAB via its quadprog function by stating a maximization problem that allows me to look $x$, and this method works if $n$, the number of rows in my matrix is small. However, as $n$ grows this method becomes very deficient and it stops finding an $x\neq 0$. The problem I stated is $\max ||x||_2$ s.t. $x\cdot A = 0$ and $\bar{x}\geq x\geq 0$. This is the way I have been able to find such an x, but I am not forced to use this command so any other commands or possibilities are kindly appreciated.
With all of this context, can you think of a way of finding $x$?