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.
Best Answer
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.