Finding a minimal set of equations that determine a variable. I have a system of $m$ linear equations on $n$ variables, which I'm representing as $Ax=b$, with $A$ an $m\times n$ matrix representing the equations and $b$ an $\mathbb R^m$ vector representing the constants of the equations. I'm given that there exists a solution $s\in\mathbb R^n$ (i.e., $As=b$) and that $m<<n$.
My goal is the following:

*

*Find which variables are determined (i.e., for which there are no solutions with values different than the one in $s$).

*For each variable in 1., find a minimal subsystem of equations which determines that variable. By minimal, I mean the following: the subsystem determines the variable as in 1., and no proper subset of the subsystem does this. I want to find any such minimal subsystem: which one I pick is irrelevant to me.

Progress:
I've solved 1. by computing the nullspace of $A$, and looking for those variables for which none of the basis vectors of the null-space have a non-zero coefficient.
I've attempted to solve 2. by computing the pseudo-inverse of $A$ and looking at which coefficients in the row corresponding to the chosen variable are non-zero. This approach doesn't work, though, since the pseudo-inverse $P$ minimizes the Frobenius norm among all matrices $X$ such that $X\cdot b=s$. This norm is an $L_2$ norm, but what we really want is an $L_0$ norm, since we want to minimize the number of non-zero elements in the matrix. Of course, finding the matrix minimizing the $L_0$ norm is an NP problem, so that's not a valid approach for me.
Are there any other approaches I'm missing? Perhaps some heuristic methods? I'm struggling to find anything on this subject.
 A: Of course, if $s_0$ is any solution then $s$ is a solution iff $A(s-s_0)=0$, and we can pass to the question of which rows of $A$ imply that some coordinate $x_i$  of every $x$ with $Ax=0$ is zero.
Suppose $Ax=0$ implies $x_1=0$. Set $x_1=1$ in the equations given by $A$. The equations are now incompatible. This is still a linear system, in one less variable, given by some $Mv=c$. (If $A$ had columns $v_1, ..., v_n$ then $c=-v_1$ and $M$ has columns $v_2, ..., v_n$.) By Fredholm alternative, this means that some linear combination of the equations gives 0=1, i.e. there is a subset of rows of $M$ whose span is lower-dimensional than the span of the corresponding rows of $A$. We are looking for a minimal incompatible subsystem, i.e. a minimal such collection.
Start with any such collection. Suppose the corresponding rows of $M$ spanning a space $V$. Select from these rows a basis of $V$, and add more rows one by one, until the dimension spaned by corresponding rows of $A$ jumps. Then pick a subset that is a basis for the space spanned by these rows of A.  At that point, we have a minimal collection of equations implying $x_1=0$.
