Let $A$ be an $n \times n$ matrix that is non-injective, specifically one where the entries are in $\mathbb{Z}_2$ or, equivalently, $GF(2)$. Let $b$ be an $n\times 1$ matrix that is in the image of $A$. Let $x$ be an $n\times 1$ matrix.
How would I go about finding the solutions for $Ax = b$, specifically the one where $x$ is the vector of the smallest magnitude? There may be multiple "smallest length vectors", but any of them would suffice. If I could find the set of solutions, that would also suffice.
Since we are in $GF(2)$, and since $b$ is in the image of $A$, I guarantee that there will exist at least one $x$ that is a valid solution and that there is a finite set of solutions.
Since $\mathbb{Z}_2$ is a field, solving $Ax=b$ works exactly the same as it does over $\mathbb{R}$. Basically you can adjoin $b$ to $A$: $[A:b]$ then find the RREF (use Gauss-Jordan elimination -- working with arithmetic mod 2). Once this is done you'll get a parameterized solution. From here you have a finite set to sort through.
Example: Let $A=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}$ and $\begin{bmatrix} 1 \\ 0 \\ 1 \\ 1 \end{bmatrix}$.
Then $[A:b] = \begin{bmatrix} 1 & 0 & 1 & 0 & : & 1 \\ 0 & 1 & 1 & 0 & : & 0 \\ 1 & 0 & 1 & 0 & : & 1 \\ 1 & 1 & 0 & 0 & : & 1 \end{bmatrix} \quad \sim \quad \begin{bmatrix} 1 & 0 & 1 & 0 & : & 1 \\ 0 & 1 & 1 & 0 & : & 0 \\ 0 & 0 & 0 & 0 & : & 0 \\ 0 & 0 & 0 & 0 & : & 0 \end{bmatrix}$ so the third and fourth variables are free. In particular, we have $x_1+x_3=1$, $x_2+x_3=0$. Let $x_3=s$ and $x_4=t$. Then $x_1=s+1$, $x_2=s$, $x_3=s$, and $x_4=t$.
$s,t$ can take on 2 different values: $0$ or $1$. This gives a total of 4 solutions:
$$\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}, \quad \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}, \quad \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix}, \quad \mbox{and} \quad \begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \end{bmatrix}$$
I guess the first one has minimal length. :)