1
vote
Find which variables must be zero for non-negative solution to homogeneous linear equations
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. ...
1
vote
Find which variables must be zero for non-negative solution to homogeneous linear equations
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 ...
1
vote
Find which variables must be zero for non-negative solution to homogeneous linear equations
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$ ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
linear-programming × 4665optimization × 1837
linear-algebra × 869
convex-optimization × 570
integer-programming × 392
operations-research × 299
simplex × 255
duality-theorems × 230
convex-analysis × 182
mixed-integer-programming × 173
nonlinear-optimization × 168
matrices × 126
constraints × 125
algorithms × 122
polyhedra × 121
inequality × 108
discrete-optimization × 105
graph-theory × 95
combinatorics × 90
mathematical-modeling × 85
systems-of-equations × 76
polytopes × 75
simplex-method × 73
geometry × 70
binary-programming × 66