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!

• In theory you could enumerate all basic feasible solutions and check. – Erwin Kalvelagen Jun 11 '18 at 20:04

Hint

Since $$A$$ is a $$m \times n$$ matrix, with $$m, 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.

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.

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.