Constrained system of linear equations I have a question that might or might not be trivial for experts from the linear programming world. 
We have a system of linear equations that we want to solve:
$A\cdot x=0$, with the constraint that all variables are non-negative: $x_i \geq 0 ~\forall i$.
The system is underdetermined, i.e. $A$ has more columns than rows, more variables than equations.
Question: 
How do we determine which $x_i$ can never be positive (i.e. are zero) in the solution space. That means, determine those $x_i$ for which
$ x_i = 0$ for any solution.
Thanks!
 A: Hint
Since $A$ is a $m \times n$ matrix, with $m<n$, a Singular Values Decomposition of it
will represent a first useful step. 
In particular you can determine the null-space of it, i.e. the set of vectors $v_1, v_2, \cdots, v_{n-m}$ (or more) for which
$$
{\bf A}\,{\bf v}_{\,k}  = {\bf 0}\quad  \Rightarrow \quad {\bf A}\,\sum\limits_k {\lambda _{\,k} } {\bf v}_{\,k}  = {\bf 0}
$$
and thereby reduce your problem to a $m \times m$ system.
A: If the problem is an actual numerical problem for which you have a matrix A, then you can set this problem up as a semidefinite program (see Convex Optimization by Boyd and Vandenberghe).  
Such a system can be solved by good convex solvers like cvx, or sedumi and yalmip in Matlab, or Pyopt in python.  In this case, since $I$ is the only inequality, this is a simple linear program.
In your case,
$$
\begin{align}
& \underset{x}{\text{minimize}}
& & 1^T x \\ 
& \text{subject to}
& & -I_{n,m}x  \le 0 \\
& & &  Ax = 0
\end{align}
$$
This should provide a minimally non-negative answer for $x$ based on the constraints.
A: If the $i^{th}$ column has at least one non-zero component that is of the same sign as every other component in the same row, then $x_i$ must be equal to $0$. This can be iterated, by setting to $0$ any $x_i$ that "passes" the test, removing the corresponding column from $A$, and repeating the test until it "evicts" no more columns.
But this is only a sufficient condition, not necessary (i.e. if it is true, then $x_i$ must be $0$; but $x_i$ could be $0$ for other reasons). Frankly, I do not know if there is a "simple" necessary and sufficient condition.
