<s>[INST] Least squares with matrix in $GF(2)$? Here's an example of a problem I'm working on involving finding combination of bit vectors that yield a certain sum (in the $GF(2)$ sense):
$
\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\                                                                                      
0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ x_8 \\ x_9 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \end{pmatrix}$
An obvious answer is just the vector where $x_7$ is 1 with all other elements being zero.  However, running simple gaussian elimination on the above matrix quickly leads you to the non-regular matrix:
$\begin{pmatrix}
1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{pmatrix}$
Which, continuing to solve from there leads you to the (correct, but sub-optimal) solution:
$x^T = \begin{pmatrix}0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\end{pmatrix}$
Is there a good method for solvings systems of equations in $GF(2)$ s.t. the answer is minimal in the $L_1$ norm sense?
 [/INST] The norm you're talking about is the Hamming weight of an element and you want the element of minimum Hamming weight in your solution space.  As far as I know there does not exist a good general algorithm for computing it.
By computing the nullspace of that matrix and then a reduced basis of that nullspace, you can probably eyeball how to get from your non-optimal solution to the minimum weight solution with not too much trial and error.  I think that's the best procedure you can hope for save throwing a computer at it.
</s>