It's 2 raised to the power of size of null-space. The reason is that once you have a solution, adding any linear combination of vectors in null-space gives you a valid solution.

This problem comes out when counting number of solutions to "lights out" puzzle, example of solving it in Mathematica using NullSpace operation:

graph = GridGraph[{4, 4}]
n = Length@VertexList@graph;
target = Table[1, {n}];
mat = AdjacencyMatrix[graph] + IdentityMatrix[n];
result = LinearSolve[mat, target, Modulus -> 2];
Print["sample solution: ", result]
Print["number of solutions: ", 2^Length@NullSpace[mat, Modulus -> 2]]

It's 2 raised to the power of size of null-space. The reason is that once you have a solution, adding any linear combination of vectors in null-space gives you a valid solution.

This problem comes out when counting number of solutions to "lights out" puzzle, example of solving it in Mathematica using NullSpace operation:

graph = GridGraph[{4, 4}]
n = Length@VertexList@graph;
target = Table[1, {n}];
mat = AdjacencyMatrix[graph] + IdentityMatrix[n];
result = LinearSolve[mat, target, Modulus -> 2];
Print["sample solution: ", result]
Print["number of solutions: ", 2^Length@NullSpace[mat, Modulus -> 2]]