Inverting a non-invertible matrix (Get all possible solutions) Currently I'm struggling with a problem.. I got a matrix which is in $GF2$. It has the size of $128 \times 128$. After constructing the matrix I need to invert it. The Problem is that the matrix can not be inverted right away, because it's rank is $120$ and therefore not invertible. Now I have been said that it is still somehow possible to invert it if I leave room for more solutions.

Let's say I got something like this: $Ax = y$. Now I calculated $A$ and want to invert it so that $A^{-1}y = x$. And i don't need a single solution for $x$, all possible solutions would be fine (Are there $2^8$ possible solutions?)

Does anyone know how to go from here? I actually know that this is possible but I don't know how to do it. Everything that points me in the right direction would be helpful.
Consider the example
$$
\begin{align}
%
  \mathbf{A} x &amp;= b \\
%
\left[
\begin{array}{ccc}
 1 &amp; 0 &amp; 0 \\
 0 &amp; 1 &amp; 0 \\
 0 &amp; 0 &amp; 0 \\
\end{array}
\right]
%
\left[
\begin{array}{ccc}
 x_{1} \\
 x_{2} \\
 x_{3}
\end{array}
\right]
%
&amp;=
%
\left[
\begin{array}{ccc}
 b_{1} \\
 b_{2} \\
 b_{3}
\end{array}
\right].
%
\end{align}
$$
There is no exact solution such that $\mathbf{A}x - b =0$ when $b_{3}\ne 0$. We turn to the method of least squares which will have the solution
$$
  x_{LS} = 
\left[
\begin{array}{ccc}
 b_{1} \\
 b_{2} \\
 0
\end{array}
\right]
%
  +
%
\alpha
\left[
\begin{array}{ccc}
 0 \\
 0 \\
 1
\end{array}
\right], \qquad
\alpha \in \mathbb{C}.
$$

The general least squares solution is 
$$
x_{LS} = \mathbf{A}^{\dagger} b + \left( \mathbf{I}_{n} - \mathbf{A}^{\dagger}\mathbf{A} \right) y, \quad y\in\mathbb{C}^{n}.
$$
If $Ax=y$, then $A(x+v)=y$ for all $v \in Null(A)$.