Finding "all solutions" of x in A.x = b in the finite field domain

Question

Matlab provides a way to find a particular solution to Ax=b in GF(2^m). Here is the link http://www.mathworks.in/help/comm/ref/gflineq.html But it gives only one solution. How can I find the rest of the solutions?

Eg: A=[1 0 2 0 0 1] in GF(4), b=[0] in GF(4). x=A\b gives [0 0 0 0 0 0]' as the solution. I also know [0 1 2 3 2 3]' to be one other solution. But I cannot get any other solution except all zero.How to find all solutions in Matlab?

Answer 1

In General,

The solutioin to the matrix equation Ax=b need not exist and even if it does, need not be unique. In your case, you know that multiple solutions exist. In such a situation, you have a "particular solution" which is basically, any x that solves Ax=b and now, to get multiple solutions, you can keep adding vectors from the Nullspace of A.

Proof:

Let x be a particular solution and y be in the Nullspace of A (any vector in Nullspace is OK). We know Ax=b. We also know Ay=0. Add them up, A(x+y)=b.

---

TL;DR Solution:

Find the Nullspace of the Matrix in GF and add any vector of the Nullspace to the particular solution to generate more solutions.

I have not used it but there seems to be a code on MATLAB Central which finds the Nullspace of a Matrix in GF.