Constrained system of linear equations

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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.