I am trying to solve this problem:
Given a set of $m$ vectors in $\mathbb{R}^n$, where $m < n$, $$(a_i)_{1 \le i \le m}$$ for a fixed index $j$ can we compute a vector $u$ in polynomial time such that $u^Ta_i = 0$, $u \ge 0$ and $u_j = 1$?
I know that we can solve this problem with linear programming but to have an exact solution with polynomial time I don't know how.
It will be also good if I can model the problem with a graph problem. Can any one help me ?