Partly solving an underdetermined system of equations Assume that $A=\{a_{ij}\}$ is an $M\times N$ matrix where $M<N$ and $Ax=b$ where $x$ is the vector of unknown variables and $b$ is a known binary vector. Assume $a_{ij}$ values are also binary. Clearly $Rank(A)\le M$, so the number of variables is larger than the number of equations. However, still some of the variables might be calculated (or maybe not, it depends on $A$). I am looking for a systematic algorithm to find all variables that can be calculated in the existing under-determined system.
 A: You can take the first $M$ variables and use Gaussian elimination for detrmining if the can be solved or not. I will give you one example. Imagine a matrix where $M=2$ and $N=4$
$$A=\left[\begin{array}{cccc}
a_{11}&a_{12}&a_{13}&a_{14}\\
a_{21}&a_{22}&a_{23}&a_{24}
\end{array}\right]$$
you start to perform Gaussian elimination over the first two columns (same as solving the first two variables $x_1$ and $x_2$). You can end up with two situations for the first row:
$$A=\left[\begin{array}{cccc}
a'_{11}&0&0&0\\
a'_{21}&a'_{22}&a'_{23}&a'_{24}
\end{array}\right]$$
which means that the first variable $x_1$ can be solved (you have decoupled the equation of $x_1$ from the rest). Or you can find 
$$A=\left[\begin{array}{cccc}
a'_{11}&0&a'_{13}&a'_{14}\\
a'_{21}&a'_{22}&a'_{23}&a'_{24}
\end{array}\right]$$
with $a'_{13}\ne0$ or $a'_{14}\ne0$, which means that the equation for $x_1$ cannot be decoupled from the other equations and it cannot be determined. (Same arguments can be given for $x_2$). After that, you can perform Gaussian elimination on the second set of variables, $x_3$ and $x_4$, and continue until you reach the end of the matrix.
Edit:
There is an special case that I have not considered: If the rank of the submatrix $\mbox{rank}(A_{MM})<M$. In that case you will obtain a line with zeros. It corresponds with the case $$A=\left[\begin{array}{cccc}
a'_{11}&0&a'_{13}&a'_{14}\\
0&0&a'_{23}&a'_{24}
\end{array}\right]$$
In that case, you have to demonstrate if you can eliminate $a'_{13},a'_{14}$ using $a'_{23},a'_{24}$ (Gaussian elimination in the next block, only using the equations with zeros in the first block).
Note that you can avoid this situation by choosing submatrices with a $\mbox{rank}(A_{MM})=M$, which are always possible to find.
A: You can achieve that by Gaussian elimination, putting the matrix in echelon form.
When you run out of equations, the remaining $n-m$ unknowns are free and you can move them to the  RHS, forming affine combinations $b_i-a_{i,m+1}x_{m+1}-a_{i,m+2}x_{m+2}-\cdots a_{in}x_n$.
Then you can perform the backsubstitution steps for the RHS vectors $\textbf b,\textbf a_{m},\textbf a_{m+1},\cdots\textbf a_{n}$. This allows you to express the general solution where all unknowns are expressed in terms of $n-m$ free parameters.
If you have enough with a single solution, just solve for $\textbf b$, assuming $x_m,x_{m+1},\cdots x_n=0$.
Notice that by using total pivoting, you can even handle degenerate systems: when there is no more pivot available, the remaining equations have just vanished (or are incompatible) and you can solve as above, with $n-r$ free parameters.
A: I want to propose a similar, possibly a little more systematic, solution:
You can bring $A$ in reduced row echelon form. Then, if (and only if) column $i$ contains a (row) pivot element and the pivot element is the only element in that row, $x_i$ can be determined uniquely.
Example:
$$ A = \begin{bmatrix} 1&-1&3&-1 \\ 0&1&0&4 \\ 2&0&6&3 \end{bmatrix}$$
In reduced echelon form, we get:
$$ A = \begin{bmatrix} 1&0&3&0 \\ 0&1&0&0 \\ 0&0&0&1 \end{bmatrix}$$
This means, we get a unqiue solution for $x_2$ and $x_4$.
