Find which variables must be zero for non-negative solution to homogeneous linear equations

Question

I am interested in non-negative solutions to the homogeneous system of equations $A \mathbf{x}=\mathbf{0}$ and find which variables $x_i$ must be zero. For example, if a row contains entries all with the same sign, like $2x_4+5x_7=0$ then we know $x_4=x_7=0$ is the only non-negative solution. But what is a systematic way to find all variables that must be zero? Say the matrix $A$ is already in reduced row echelon form, like this one

\begin{bmatrix}1&0&0&-1&0&0&0&1&0&0\\0&1&0&-1&0&0&0&0&1&0\\0 & 0 & 1&-1&0&0&0&0&0&1\\0&0&0&0&1&0&0&1&0&-1\\0&0&0&0&0&1&0&-1&1&0\\0 & 0 & 0&0&0&0&1&0&-1&1\end{bmatrix}

It took me a while to find that $x_5=x_6=x_7=0$, through lots of experimentation. But for an even bigger matrix, this is not feasible. Is there a simple yet systematic way to find the answer, perhaps analogous to achieving reduced row echelon form? Does this problem have a name?

I'm looking for a general algorithm/approach that does not assume anything about the entries of the matrix.

Answer 1

If you are interested In an algorithmic solution I suggest the use of linear optimization.

For example, say we have a system of equations: $$A\cdot x = 0$$ and we wish to check if $x_i$ always vanishes. First fix a vector $c_j = \delta_{i,j}$. Now, build the block matrix:

$$A' = \begin{pmatrix} A \\ -A \end{pmatrix}$$

From this construct the following linear optimization problem:

$$ \text{find a vector } x \text{ s.t.} \\ c^T \cdot x \text{ is maximal and} \\ A' \cdot x \leq 0 \\ x \geq 0 $$

Now, apply any solver to this problem (there are many with polynomial complexity). If the resulting vector has $x_i = 0$ then $x_i$ must always vanish.

proof of correctness

First, I'll show that this algorithm indeed gives a positive valued solution to $Ax = 0$. The condition $x \geq 0$ is directly enforced, so there is nothing to prove here. Indeed:

$$A' \cdot x \leq 0 \iff \\ \begin{pmatrix} A \\ -A \end{pmatrix} \cdot x \leq 0 \iff \\ \begin{pmatrix} A\cdot x \\ -A\cdot x \end{pmatrix} \leq 0 \iff \\ Ax \leq 0 \land -Ax \leq 0 \iff Ax = 0$$

And thus any output of the algorithm is a valid positive valued solution.

Now I will prove that this actually solves the problem. Notice we are optimizing $c^T \cdot x$ or in other words we are optimizing for $x_i$. Thus, the output of the function will be the solution with largest possible $x_i$. Therefor if we get $x_i = 0$ any other positive valued solution will have $0 \leq x_i \leq 0$. Of course, if we get $x_i > 0$ obviously $x_i$ doesn't always vanish.

Answer 2

A simple approach is to use linear programming (LP). For each $j$, the problem is to maximize $x_j$ subject to $Ax=0$ and $x \ge 0$. For your example matrix $A$, the optimal objective value is $0$ for $j\in\{5,6,7\}$ (which implies that $x_j=0$) and unbounded for all other $j$.

A sometimes useful shortcut is to first maximize $\sum_j x_j$. For any $j$ such that $x_j>0$ in the resulting optimal solution, you can then skip one solver call.

More generally, this LP approach finds the tightest possible upper bound for each $x_j$, and you can also minimize to find the tightest possible lower bound.

Answer 3

Some addition to @Alexey answer.

There are many good solvers for LP (linear programming) problems; and if you are only dealing with some thousands of variables, open source solvers will suffice. However you may want to understand the algorithm, or even implement it by yourself.

There are various algorithms to solve LP problems. One of the most used is the simplex algorithm. It dates back from 1947. Other algorithms (interior point methods notably) have been discovered since then, and some of them have a polynomial complexity.

The simplex algorithm has exponential complexity on worst case. But in practice the simplex is often faster than other algorithms, and it has been later shown that it has a polynomial smoothed complexity (Spielman, Daniel; Teng, Shang-Hua (2001), "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time").

The simplex algorithm is easier to understand than other LP algorithms. It works with the polyhedron of constraints by going from one vertex to an adjacent vertex that has a lower objective (if trying to minimize a linear objective). So it always maintains the maximum possible number of variables on their bounds. Most of your constraints ate that variables have to be positive, so this means the maximum possible number of variables at 0.

You may want to look at the video on simplex in the "Discrete Optimization" course from the University of Melbourne, on Coursera. Very well explained.

https://en.coursera.org/lecture/discrete-optimization/lp-3-the-simplex-algorithm-2EenQ

Note that in order to use the simplex algorithm you'll have to tweak your problem a little:

• LP problems are optimization problems: some linear objective function has to be optimized. As you are looking for null variables you may choose to minimize $\sum_i x_i$. This is also to avoid the algorithm to conclude that the best solution is unbounded, i.e. some variable tends to $+\infty$.
• Simplex algorithm requires initialization with a vertex of the polyhedron of constraints. Unfortunately, this is what you are looking for! Fortunately, the trick is to first find this point with a first simplex, called phase 1. This is explained in any text about simplex algorithm, e.g. Wikipedia:

https://en.m.wikipedia.org/wiki/Simplex_algorithm